Graphics Reference
In-Depth Information
2
1
-
1
(a)
(b)
(c)
(d)
Figure 7.20: (a) A nonsimple polygon whose regions have been labeled by Listing's rule,
(b) the interior defined by the positive winding number rule, (c) by the even-odd rule, and
(d) by the nonzero winding number rule.
7.10.2 Interiors of Nonsimple Polygons
Most of the polygons we'll encounter will be triangles, and therefore simple.
But occasionally we'll encounter nonsimple polygons in the plane, and there are
several alternatives (see Figure 7.20) for defining the interior of these. All first
compute the winding number of the polygon about the point P as before; in this
case, though, the winding number may be different from one or zero. The pos-
itive winding number rule says that points with positive winding numbers are
inside; the odd winding number rule says that those with odd winding numbers
are inside—the result is a checkerboardlike appearance for the inside and outside
regions; the nonzero winding number rule says that points with nonzero winding
numbers are inside. Each has its uses; drawing programs should probably allow
all three as alternatives.
7.10.3 The Signed Area of a Plane Polygon: Divide
and Conquer
If P 1 =( x 1 , y 1 ) and P 2 =( x 2 , y 2 ) are points in the xy -plane (see Figure 7.21), and
Q =( 0, 0 ) is the origin, then the signed area of the triangle QP 1 P 2 is given by
1
2 ( x 1 y 2
P 2 =
( x 2 , y 2 )
y 1 x 2 ) .
(7.122)
The signed area is positive if the vertices Q , P 1 , P 2 are in counterclockwise order
around the triangle, and negative if they're in clockwise order. (It will be easy to
prove this after you read Chapter 10, which discusses transformations in the plane:
You first verify that the formula doesn't change when the triangle is rotated, so you
can assume that P 1 lies on the positive x -axis, and therefore, P 1 =( x 1 ,0 ) with
x 1 >
P 1 =
( x 1 , y 1 )
Q
=
(0, 0)
0. The triangle is then clockwise if and only if P 2 =( x 2 , y 2 ) is in the y
>
0
Figure 7.21: The signed area of
the triangle QP 1 P 2 is positive if
thepathfromQtoP 1 to P 2 to
Q is counterclockwise, and nega-
tive if it's clockwise. In the exam-
ple
1
half-space, that is, y 2 >
0. But the area formula then gives the area as
2 x 1 y 2 >
0.
The clockwise case is similarly easy to verify.)
From this formula for the area of a triangle, we can write a formula for the
signed area of a triangle with vertices P 0 =( x 0 , y 0 ) , P 1 =( x 1 , y 1 ) , and P 2 =
( x 2 , y 2 ) : If we change to a coordinate system based at P 0 , the new coordinates of
P 1 and P 2 are ( x 1
shown,
the
signed
area
is
x 0 , y 1
y 0 ) and ( x 2
y 0 , y 2
y 0 ) . Applying the formula to
positive.
these coordinates gives
2
1
2 (( x 1 y 2
x 1 y 0 )) = 1
2
x 2 y 1 )+( x 2 y 0
x 0 y 2 )+( x 0 y 1
( x i y i + 1
x i + 1 y i ) ,
i = 0
(7.123)
where indices are considered modulo 3, so x 3 means x 0 and y 3 means y 0 .
 
 
 
 
Search WWH ::




Custom Search