Greiner–Hormann clipping algorithm: Difference between revisions

Revision as of 01:31, 8 April 2015

Revision as of 01:37, 8 April 2015

Line 34:

* In the third phase, the result is generated. The algorithm starts at an unprocessed intersection and picks the direction of traversal based on the entry/exit flag: for an entry intersection it traverses forward, and for an exit intersection it traverses in reverse. Vertices are added to the result until the next intersection is found; the algorithm then switches to the corresponding intersection vertex in the other polygon and picks the traversal direction again using the same rule. If the next intersection has already been processed, the algorithm finishes the current component of the output and moves to an unprocessed intersection. The output is complete when there are no more unprocessed intersections.

The algorithm is not restricted to polygons and can handle arbitrary [[planeparametric curve]]s as segments, as long as there is a suitable pairwise intersection procedure.

A major shortcoming of the original Greiner–Hormann algorithm is the fact that it cannot handle degeneracies, such as common edges or intersections exactly at a vertex. The original paper suggests perturbing the vertices to remove them. Several modifications to handle degeneracy have been proposed in the literature.<ref name="foster"/>