Graphics Reference
In-Depth Information
does both clipping
and
filling. Because Section 14.4 will describe a special case of the
trapezoid form of the Vatti algorithm for use with trimmed surfaces, we postpone any
further details on how to deal with trapezoids to there.
Finally, we can also use the Vatti algorithm for other operations than just inter-
section. All we have to do is replace the classification rules. For example, if we want
to output the union of two polygons, use the rules
(1) (LC » LS)
or
(LS » LC) Æ LI
(2) (RC » RS)
or
(RS » RC) Æ RI
(3) (LS » RC)
or
(LC » RS) Æ MN
(4) (RS » LC)
or
(RC » LS) Æ MX
Local minima of the subject polygon that lie outside the clip polygon and local minima
of the clip polygon that lie outside the subject polygon should be treated as con-
tributing local minima.
For the difference of two polygons (subject polygon minus clip polygon) use the rules
(1) (RC - LS)
or
(LS - RC) Æ LI
(2) (RS - LC)
or
(LC - RS) Æ RI
(3) (RS - RC)
or
(LC - LS) Æ MN
(4) (RC - RS)
or
(LS - LC) Æ MX
Local minima of the subject polygon that lie outside the clip polygon should be treated
as contributing local minima.
3.3.6
Greiner-Hormann Polygon Clipping
The last polygon-clipping algorithm we consider is the Greiner-Hormann algorithm
([GreH98]). It is very much like Weiler's algorithm but simpler. Like the Weiler and
Vatti algorithm it handles any sort of polygons including self-intersecting ones. Fur-
thermore, it, like Vatti's algorithm, can be modified to return the difference and union
of polygons, not just their intersections.
Suppose that we want to clip the subject polygon
S
against the clip polygon
C
.
What we shall do is find the part of the boundary of
S
in
C
, the part of the boundary
of
C
in
S
, and then combine these two parts. See Figure 3.21. Since we allow self-
intersecting polygons, one needs to be clear about when a point is considered to be
inside a polygon. Greiner-Hormann use the winding number w(
p
,g) of a point
p
with
respect to a parameterized curve g. They define a point
p
to be in a polygon
P
if the
winding number of the point with respect to the boundary curve of
P
is odd. (The
oddness or evenness of the winding number with respect to a curve is independent of
how the curve is parameterized.)
Polygons are represented by doubly-linked lists of vertices. The algorithm pro-
ceeds in three phases. One will find it helpful to compare the steps with those of the
Weiler algorithm as one reads.
Phase 1.
We compare each edge of the subject polygon with each edge of the clip
polygon, looking for intersections. If we find one, we insert it in the appropriate place
