Graphics Reference
In-Depth Information
0
1
2
3
Figure 5.29
Shooting rays from four different query points. An odd number of boundary
crossings indicates that the query point is inside the polygon.
This point containment test is similar in structure to the one presented in
[Preparata85], where a point interior to the
n
-gon fills the role played here by the
vertex
V
0
.
Another
O
(
n
) test that works for concave polygons is based on shooting a ray
from the point along some direction (commonly the positive
x
axis) and counting
the number of times it crosses the polygon boundary. If the ray crosses the boundary
once, the point must be inside the polygon. If it crosses twice, the point must be
outside, with the ray first entering and then exiting the polygon. In general, the point
will be inside the polygon for an odd number of crossings and outside for an even
number of crossings. This test, commonly referred to as the
crossings test
, is illustrated
in Figure 5.29.
Some care must be exercised to properly handle cases where the ray passes through
a polygon vertex or coincides with an edge of the polygon. If not dealt with correctly,
multiple crossings could be detected in these cases, giving an incorrect crossings
count. In practice, this problem can be dealt with effectively by arranging the tests
performed so as to treat vertices on the ray as lying infinitesimally above the ray.
Several variations on the crossings test are presented in [Haines94].
5.4.2
Testing Point in Triangle
The case of testing whether a point is contained in a triangle comes up frequently
enough that it is worth studying separately from point-in-polygon tests. Two effec-
tive solutions to the point-in-triangle problem have already been presented: one
