Graphics Reference
In-Depth Information
LML = ( (B
1
, B
2
) , (B
3
, B
4
) )
where the bounds B
i
are defined by
B
1
= (
p
0
p
8
,
p
8
p
7
,
p
7
p
6
) ,
B
2
= (
p
0
p
1
,
p
1
p
2
) ,
B
3
= (
p
4
p
5
,
p
5
p
6
) , and
B
4
= (
p
4
p
3
,
p
3
p
2
) .
(b)
(a)
Figure 3.18.
Polygon bounds.
of left-right bounds and is sorted in ascending order by the y-coordinate of the cor-
responding local minimum. It does not matter if initial horizontal edges are put into
a left or right bound. Figure 3.18(b) shows the LML for the polygon in Figure 3.18(a).
The algorithm for constructing the LML is a relatively straightforward programming
exercise and will not be described here. It can be done with a single pass of the clip
and subject polygons.
The bounds on the LML were specified to have the property that their edges are
either
all
left edges or
all
right edges. However, it is convenient to have a more general
notion of a left or right bound. Therefore, from now on, a
left
or
right bound
will
denote any connected sequence of edges only whose
first
edge is required to be a left
or right edge, respectively. We still assume that a bound starts at a local minimum
and ends at a local maximum. For example, we shall allow the polygon in Figure
3.18(a) to be described by one left bound with vertices
p
0
,
p
8
,
p
7
,
p
6
,
p
5
,
p
4
,
p
3
,
p
2
and
one right bound with vertices
p
0
,
p
1
,
p
2
.
The clipped or
output
polygons we are after will be built in stages from sequences
of “partial” polygons, each of which is a “V-shaped” list of vertices with the vertices
on the left side coming from a left bound and those on the right side coming from a
right bound with the two bounds having one vertex in common, namely, the one at
the bottom of the “V”, which is at a local minimum. Let us use the notation P[
p
0
p
1
...
p
n
] to denote the partial polygon with vertices
p
0
,
p
1
,...,
p
n
, where
p
0
is the first
point and
p
n
, the last. The points
p
0
and
p
n
are the top of the partial left and right
bound, respectively. Some vertex
p
m
will be the vertex at a local minimum that con-
nects the two bounds but, since it will not be used for anything, there is no need to
indicate this index m in the notation. For example, one way to represent the polygon
in Figure 3.18(a) would be as P[
p
6
p
7
p
8
p
0
p
1
p
2
p
3
p
4
p
5
p
6
] (with m being 3 in this case).
Notice how the edges in the left and right bounds are
not
always to the right or left
of the interior of the polygon here. In the case of a “completed” polygon,
p
0
and
p
n
will be the same vertex at a local maximum, but at all the other intermediate stages
in the construction of a polygon the vertices
p
0
and
p
n
may
not
be equal. However,
p
0
and
p
n
will always correspond to top vertices of the current left and right partial
bounds, respectively. For example, P[
p
7
p
8
p
0
p
1
] (with m equal to 2) is a legitimate
expression describing partial left and right bounds for the polygon in Figure 3.18(a).
