Graphics Reference
In-Depth Information
Figure 3.21.
Greiner-Hormann polygon clipping.
vertex
=
record
float
x, y;
vertex pointer
next, prev;
boolean
intersect;
boolean
entry;
vertex pointer
neighbor;
float
alpha;
vertex pointer
nextPoly;
end
;
Data 3.3.6.1.
The Greiner-Hormann vertex structure.
in
both
polygons' vertex lists. If there are no intersections, then either one polygon is
contained in the other or they are disjoint. These cases are checked for easily and we
then exit the algorithm in this case with our answer.
Phase 2.
We traverse each polygon's new vertex lists marking any intersection points
as either entry or exit points. This is done by checking whether the first vertex of each
polygon lies inside the other polygon or not using the winding number. The rest of
the tagging as entry or exit points is then easy.
Phase 3.
This stage actually creates the intersection polygons. We start at an inter-
section point of the subject polygon and then move along its point list either forward
or backward depending on its entry-exit flag. If we are at an entry point, then we move
forward, otherwise, backward. When we get to another intersection point, we move
over to the other polygon's list.
The data structure used for vertices is shown in Data 3.3.6.1. In the case of an
intersection point, if the
entry
field is false, then the point is an exit point. At an inter-
section vertex in one of the polygon's vertex lists the field
neighbor
points to the cor-
responding vertex in the other polygon's vertex list. The field
alpha
for an intersection
point specifies the position of the intersection relative to the two endpoints of the edge
