Greiner–Hormann clipping algorithm


The Greiner-Hormann algorithm is used in computer graphics for polygon clipping. It performs better than the Vatti clipping algorithm, but cannot handle degeneracies. It can process both self-intersecting and non-convex polygons. It can be trivially generalized to compute other Boolean operations on polygons, such as union and difference.
The algorithm is based on the definition of the "inside" of a polygon based on the winding number. It considers regions with odd winding number to be inside the polygon; this is known as the even–odd rule. It takes two lists of polygons as input.
In its original form, the algorithm is divided into three phases:
The algorithm is not restricted to polygons and can handle arbitrary parametric curves 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.