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.
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.
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
.