Graphics Reference
In-Depth Information
(a)
(b)
(c)
(d)
(e)
Figure 3.18
Some inputs likely to be problematic for a convexity test. (a) A line segment.
(b) A quad with two vertices coincident. (c) A pentagram. (d) A quadrilateral with two extra
vertices collinear with the top edge. (e) Thousands of cocircular points.
Vector acd = Cross(c - a,d-a);
Vector acb = Cross(c - a,b-a);
return Dot(acd, acb) < 0.0f;
}
Testing two line segments in the plane for intersection is discussed in more detail
in Section 5.1.9.1.
For general
n
-gons, not just quads, a straightforward solution is to, for each poly-
gon edge, test to see if all other vertices lie (strictly) on the same side of that edge. If the
test is true for all edges, the polygon is convex, and otherwise it is concave. A separate
check for coincident vertices is required to make the test robust. However, although
easy to implement, this test is expensive for large polygons, with an
O
(
n
2
) complexity
in the number of vertices. Polygons involved in collision detection systems are rarely
so large that the
O
(
n
2
) complexity becomes a problem. It is easy to come up with
tests that are faster. However, many of them correctly classify only a subset of convex
polygons and incorrectly classify some nonconvex polygons (Figure 3.18). For exam-
ple, a strictly convex polygon has interior angles that are all less than 180 degrees.
However, although this test is a necessary criterion for convexity it is not a sufficient
one. Testing the interior angles alone would thus incorrectly conclude that a penta-
gram is a convex polygon (Figure 3.18c). This test only works if the polygon is known,
a priori, not to be self-intersecting.
Another basis for a convexity test is that there are only two changes in direction
along any given axis when moving from vertex to vertex of a convex polygon, account-
ing for wraparound from the first to the last vertex. To detect the zigzag case illustrated
in Figure 3.18d, a test for change of direction would have to be performed for two
different directions, such as along both the
x
axis and the
y
axis. Although seemingly
robust, this test fails (for example) when all vertices of an originally convex polygon
have been projected onto a single line. It turns out that applying both of these two
alternative tests at the same time makes for a rather robust combined test, with the
two approaches “covering” for each other (so to speak). An implementation of the
combined test is described in [Schorn94].
