Clipping - Computer Graphics and Geometric Modeling - page 107

vertex pointer current;

while more unprocessed subject intersection points do
begin
current := pointer to first remaining unprocessed subject intersection point;
NewPolygon (P);
NewVertex (current);
repeat
if currentÆentry
then
repeat
current := currentÆnext;
NewVertex (current);
until currentÆintersect

else

repeat
current := currentÆprev;
NewVertex (current);
until currentÆintersect
current := currentÆneighbor;
until Closed (P);
end ;

Algorithm 3.3.6.1. Algorithm for Greiner-Hormann's Phase 3.

containing this intersection point. Because the intersection polygon may consist of
several polygons, these polygons are linked with this field. The first vertex of each
intersection polygon list has its nextPoly field point to the first vertex of the next inter-
section polygon.
The basic steps for Phase 3 are shown in Algorithm 3.3.6.1. The procedure
NewPolygon starts a new polygon P and NewVertex creates a new vertex for this
polygon and adds it to the end of its vertex list. Figure 3.22 shows the data structure
that is created for a simple example.
The algorithm uses an efficient edge intersection algorithm and handles degener-
ate cases of intersections by perturbing vertices slightly.
The advantage of the Greiner-Horman algorithm is that it is relatively simple and
the authors claim their algorithm can be more than twice as fast as the Vatti algo-
rithm. The reason for this is that Vatti's algorithm also checks for self-intersections
which is not done here. Of course, if one knows that a polygon does not have self-
intersections, then the extra work could be avoided in Vatti's algorithm also. The
disadvantage of the algorithm is that one does not get any trapezoids but simply
the boundary curve of the intersection. In conclusion, the Greiner-Horman algorithm
is a good one if all one wants is boundaries of polygons because it is simple and yet
fast.