Graphics Reference
In-Depth Information
Overall, this problem is very similar to that of the intersecting of a segment against
a box defined as the intersection of three slabs (as in Section 5.3.3). Because a box
is just a special case of a convex polyhedron, this code could also be used for the
segment-box test.
5.4
Additional Tests
This section describes a number of tests and computations that do not directly fit into
the classifications of the earlier sections but are still either commonly encountered or
illustrate a technique that can be applied to related problems.
5.4.1
Testing Point in Polygon
A large number of approaches exist for testing the containment of a point in a polygon.
An excellent survey of point-in-polygon methods is given in [Haines94]. An addi-
tional method, based on quadrant testing, is presented in [Weiler94]. An approach
based on a CSG representation of the polygon is described in [Walker99]. A good
survey is also given in [Huang97].
Most point-in-polygon tests required in real-time collision detection applications
can be limited to involve convex polygons only. Whereas the point containment
for concave
n
-gons may require
O
(
n
) time, the special structure of convex polygons
allows a fast point-containment test to be performed in
O
(log
n
) time, through an
interval-halving approach.
Assume a convex
n
-gon is given counterclockwise by the vertices
V
0
,
V
1
,
...
,
V
n
−
1
.
By testing whether the query point
P
is to the left or right of the directed line through
V
0
and
V
k
,
k
, half the polygon can be excluded from further tests. The
procedure is repeated, with the value of
k
adjusted accordingly until
P
either has been
found to lie outside the polygon (right of the directed line through
V
0
and
V
1
, or left
of the one through
V
0
and
V
n
−
1
) or between the directed lines through
V
0
and
V
k
and
through
V
0
and
V
k
+
1
. In the latter case,
P
is contained in the polygon if
P
also lies to
the left of the directed line through
V
k
and
V
k
+
1
.
As an example, consider the eight-sided convex polygon of Figure 5.28. Initially,
P
is tested against the directed line
A
through
V
0
and
V
4
, dividing the polygon in half
vertex-wise. Because
P
lies to the left of
A
, the right polygon half is discarded and
the left half is now processed in the same manner. Next,
P
is tested against the line
B
, followed by a test against
C
. At this point,
P
lies between the lines through two
consecutive vertices, and thus a final test is performed against the directed line
D
through these two vertices, here confirming that
P
indeed lies inside the polygon.
By using the predicate
TriangleIsCCW()
, which determines if the triangle speci-
fied by three points is defined counterclockwise, this test can be efficiently imple-
mented as follows.
=
n
/2
