Graphics Reference
In-Depth Information
(a)
(b)
Figure 12.17
(a) A simple polygon that only has two ears (ears shown in gray). (b) One
possible triangulation of the polygon.
V
6
V
4
V
4
V
4
V
5
V
5
V
1
V
1
V
1
V
3
V
3
V
2
V
0
V
0
V
0
(a)
(b)
(c)
Figure 12.18
The first steps of triangulation by ear cutting. (a) Identifying
V
2
as an ear. (b)
Identifying
V
3
as an ear after cutting
V
2
. (c) Identifying
V
4
as an ear after cutting
V
3
.
not an ear because
V
1
is not convex, in that the triangle (
V
0
,
V
1
,
V
2
) is clockwise. The
algorithm proceeds to
V
2
. Because
V
2
is convex and no polygon vertices lie in the
triangle (
V
1
,
V
2
,
V
3
),
V
2
is an ear and is clipped. Now a step back is taken, to revisit
V
1
because its ear-ness status might have changed. However,
V
1
is still concave, and
thus the algorithm proceeds to its successor vertex, which is now
V
3
. It is found to
be an ear and is cut, and thus the algorithm again revisits
V
1
.Yet again
V
1
is concave.
Next is vertex
V
4
, which is an ear.
V
1
is now revisited once more, this time found to
be an ear. After
V
1
is cut, what remains is a triangle and the algorithm stops.
Testing if a vertex is an ear may require testing all other vertices for containment
in the ear, and is therefore
O
(
n
). The outer loop may end up performing up to the
