Graphics Reference
In-Depth Information
17.6.2 Theorem.
Every polygon can be triangulated. If the polygon has n vertices,
then each of its triangulations will have n - 2 triangles.
Proof.
Let
P
be a polygon in
R
2
with n ≥ 3 vertices. We prove that
P
can be trian-
gulated by induction on n. If n = 3, then we have a triangle and there is nothing to
do. Assume that n > 3 and that the theorem is true for all m, 3 £ m < n. By Lemma
17.6.1
P
has a diagonal. This diagonal will divide
P
into two polygons, each having
fewer than n vertices. These two polygons will have triangulations by the inductive
hypothesis and the union of these triangulations will define a triangulation of
P
.
Next, we show that any triangulation of
P
has n - 2 triangles. This is again proved
by induction on n. Pick any diagonal of
P
. Assume that it has vertices
u
and
v
and let
P
1
and
P
2
be the two polygons into which it divides
P
. Suppose that
P
i
has n
i
vertices.
Clearly,
nn n
1
+=+
2
2
since the only vertices that
P
1
and
P
2
have in common are
u
and
v
. By induction,
P
i
has n
i
- 2 triangles. Therefore,
P
has
(
)
+-
(
)
=+
(
)
-= +
(
)
-=-
n
-
2
n
2
n
n
4
n
2
4
n
2
1
2
1
2
triangles and we are done.
Theorem 17.6.2 leads to an O(n
2
) algorithm for a triangulation. Finding a diago-
nal with the argument in Lemma 17.6.1 takes O(n) steps because taking the left-most
vertex, checking if the segment between the two adjacent vertices is a diagonal, and
finding
u
¢ if not, takes at most O(n) steps. As we subdivide the polygon along the diag-
onal, the worst case is when one of the two polygons always ends up being a trian-
gle. Is this the best we can do? No, we can do better. We sketch the geometric idea
behind one improvement and refer the reader to [BKOS97] or [LeeP77] and [GJPT78]
for more details. We already pointed out that for convex polygons one needs only O(n)
steps. However, partitioning a polygon into convex pieces is itself a difficult problem
and so we need a weaker property than convexity.
Definition.
A polygon
P
is said to be
monotone with respect to line
L
if every line
L
¢ that is orthogonal to
L
intersects
P
in a connected interval. We say that
P
is
y-
monotone
if it is monotone with respect to the y-axis.
See Figure 17.10 for a polygon
P
that is y-monotone and one,
Q
, that is not. Our
first task will be to divide a polygon into y-monotone pieces. We begin by classifying
the vertices of the polygon.
Let
P
be a polygon defined by the vertex sequence
p
1
,
p
2
,...,
p
k
. To simplify the
notation define
p
0
=
p
k
and
p
k+1
=
p
1
. Assume that the vertices have been listed in a
counterclockwise order, that is, the polygon
P
lies to the “left” of an edge
p
i
p
i+1
. (The
normal
n
i
with the property that (
p
i
p
i+1
,
n
i
) induces the standard orientation points
into the polygon along the edge
p
i
p
i+1
.)
Definition.
Define the
interior angle
q
i
at a vertex
p
i
to be the signed angle between
the vectors
p
i
p
i+1
and
p
i
p
i-1
. A vertex
p
i
is called a
turn vertex
if it is one of the fol-
lowing type:
