Graphics Reference
In-Depth Information
Figure 6.5.
Surrounding test based on
normals.
These constraints on x and y are clearly the correct ones.
The Equations Test (Convex Q).
This test is really just a rewriting of the previous
test. We shall describe it in the two-dimensional case. Let
n
i
= (a
i
,b
i
) and c
i
=-
q
i
·
n
i
.
With this notation, the ith halfplane above is just the set
{
(
)
0
xy ax by c
,
++≥
.
i
i
i
It follows that
p
= (x,y) will belong to the polygon if and only if
ax by c
++
0
i
i
i
for all i. What is the difference between the normals and equations test? Not much.
Deciding which test to use basically depends on how data has been stored in a
program. Did one store
vectors n
i
or coefficients a
i
, b
i
, and c
i
?
The normals and equations tests can be generalized to a test for whether or not
a convex polyhedron
P
is contained in
Q
. One simply checks if all the vertices of
P
belong to
Q
. If they do, then
P
will be contained in
Q
, otherwise not.
The Barycentric Coordinate Test (Convex Q).
This test ([Bado90]) applies only to
polyghedron in the plane. We think of
Q
=
p
0
p
1
...
p
k
as a fan of triangles
p
0
p
i
p
i+1
and then check each triangle to see whether
p
belongs to it by computing its barycen-
tric coordinates with respect to the vertices. For example, in the case of the triangle
D =
p
0
p
1
p
2
, express
p
0
p
in the form
pp
=
a
pp
+
b
pp
.
0
0
1
0
2
The point
p
will belong to D if and only if a,b ≥ 0 and a + b £ 1. See Figure 6.6. If one
keeps track of the number of triangles that cover the point, then one can extend the
test to
nonconvex
polygons.
The Wedge Test (Convex Q).
This test ([PreS85]) also applies only to polygons in
the plane. One adds a central point
q
to the polygon
Q
=
p
0
p
1
...
p
k
, say the centroid.
