Graphics Reference
In-Depth Information
A
D
A
C
D
D
B
A
C
D
B
B
C
B
C
A
(a)
(b)
(c)
(d)
Figure 3.17
Different types of quads. (a) A convex quad. (b) A concave quad (dart). (c) A self-
intersecting quad (bowtie). (d) A degenerate quad. The dashed segments illustrate the two
diagonals of the quad. The quad is convex if and only if the diagonals transversely intersect.
and overlapping, the quad is degenerate (into a line), as illustrated in Figure 3.17d. To
avoid considering a quad with three collinear vertices convex, the segments should
only be considered intersecting if they overlap on their interior (and not on their
endpoints).
It can be shown that the intersection of the segments is equivalent to the points
A
and
C
lying on opposite sides of the line through
BD
, as well as to the points
B
and
D
lying on opposite sides of the line through
AC
. In turn, this test is equivalent to
the triangle
BDA
having opposite winding to
BDC
, as well as
ACD
having opposite
winding to
ACB
. The opposite winding can be detected by computing (using the cross
products) the normals of the triangles and examining the sign of the dot product
between the normals of the triangles to be compared. If the dot product is negative,
the normals point in opposing directions, and the triangles therefore wind in opposite
order. To summarize, the quad is therefore convex if
(
BD
×
BA
)
·
(
BD
×
BC
)
<
0 and
(
AC
×
AD
)
·
(
AC
×
AB
)
<
0.
A straightforward implementation results in the following code:
// Test if quadrilateral (a, b, c, d) is convex
int IsConvexQuad(Point a, Point b, Point c, Point d)
{
// Quad is nonconvex if Dot(Cross(bd, ba), Cross(bd, bc))
>=
0
Vector bda = Cross(d - b,a-b);
Vector bdc = Cross(d - b,c-b);
if (Dot(bda, bdc) >= 0.0f) return 0;
// Quad is now convex iff Dot(Cross(ac, ad), Cross(ac, ab))
<
0
