Graphics Reference
In-Depth Information
Figure 17.10.
Y-monotonicity of polygons.
Figure 17.11.
Vertex types of a polygon.
start vertex
:
Its two adjacent vertices lie below it and the interior angle is less
than p.
end vertex
:
Its two adjacent vertices lie above it and the interior angle is less
than p.
split vertex
:
Its two adjacent vertices lie below it and the interior angle is larger
than p.
merge vertex
:
Its two adjacent vertices lie above it and the interior angle is larger
than p.
If a vertex is not a turn vertex it is called a
regular vertex
. Here a vertex
p
= (p
x
,p
y
) is
below
another vertex
q
= (q
x
,q
y
) if p
y
< q
y
or p
y
= q
y
and p
x
> q
x
. The vertex
p
is
above
q
if p
y
> q
y
or p
y
= q
y
and p
x
< q
x
.
See Figure 17.11. Note that if the adjacent vertices of a vertex lie either above or
below it, then the interior angle cannot equal p. Now it is the split and merge vertices
that we want to eliminate because a polygon will be y-monotone if it has no such ver-
tices. To partition a polygon into y-monotone pieces we proceed as follows. We start
at a highest vertex and sweep a line downwards. When we hit a split vertex
p
i
, then
we want to choose a diagonal that goes up from
p
i
and split the polygon with it. This
will give us two polygons and we then work on them one at a time. If we hit a merge
vertex, then we choose a diagonal that goes down. Figure 17.12 shows what would
have happened to the polygon in Figure 17.11. Polygon
P
in Figure 17.12(a) would
split into polygons
P
1
and
P
2
shown in Figure 17.12(b) and finally polygon
P
2
would
split into polygons
P
3
and
P
4
shown in Figure 17.12(c). By choosing suitable data
