Graphics Reference
In-Depth Information
Inputs:
A strictly y-monotone polygon
P
specified by two chains of vertices
starting at the top vertex with one chain listing the vertices along the
right side of the polygon and the other listing the ones on the left
Outputs:
A triangulation of
P
as an appropriately specified list of edges T
tagged vertex p
i
,
p
;
stack of tagged vertices
S;
integer
i;
Order the vertices of
P
by decreasing y-coordinate with vertices having the same
y-coordinate being ordered by increasing x-coordinate. Let
p
1
,
p
2
, ยบ ,
p
k
be the
vertices listed in that order tagged by whether they are on the right or left side of
P
.
Initialize S to empty; Add all edges of
P
to T;
Push (
p
1
,S); Push (
p
2
,S);
for
i:=3
to
k-1
do
if p
i
and Top (S) lie on different sides of the polygon
then
begin
while
|S| > 1
do
begin
p
:= Pop (S); Insert a diagonal from
p
i
to
p
into T;
end
Pop (S); Push (
p
i-1
,S); Push (
p
i
,S);
end
else
begin
p
:= Pop (S);
while
diagonal from
p
i
to Top (S) lies in
Pdo
begin
p
:= Pop (S); Insert a diagonal from
p
i
to
p
into T;
end
;
Push (
p
i
,S);
end
;
Insert into T a diagonal from
p
k
to all the vertices on S except the first and last;
Algorithm 17.6.1.
The triangulation algorithm for y-monotone polygons.
with angles close to p are often undesirable and a lot of work has been done to get
more nicely shaped triangles in the end. As one example, we mention the paper
[BeMR94] that describes a way to get a triangulation so that no angle in the triangles
is larger than p/2. It starts by first packing the polygon with disks.
Finally, the triangulation algorithm we described above also applies to polygons
with holes and, more generally, for arbitrary planar subdivisions. For polygons with
holes see also the trapezoidation algorithm in Section 14.4 and [ZalC99].
