Teleranek

Today’s 200th aniversary of Goerge Boole‘s birth, so this is a post about polygon clipping – boolean operations on polygons.
Most popular (and quite simple and fast) algorithm for this task is Greiner-Hormann. Unfortunately, as wikipedia says, it has 1 big drawback – cannot handle shapes with common edges. So XOR boolean operation won’t work. And we won’t be able to clip following “rectangles” (AND operation in this example):

[[]]→[[]]

Original Greiner-Hormann consists of 3 phases:

1. Compute intersections and add them to polygon
2. Marking intersections as “entering” or “exiting”
3. Final traversal and generating new polygons

The improved algorithm involves just adding additional phase of algorithm, just after the 1st one:
1.5 disabling “bad” intersections

Of course all intersections shouldn’t double themselves, so before adding intersections to polygon you should remove duplicate intersections. Doubling intersections are esp. possible when computing bezier intersections using traditional bezier clipping or computing intersections via approximation of bezier curves with polygons – the approximation leads to finding too many intersections for almost collinear curves.

Disabling bad intersections should mark intersections as “bad” and then they should be ignored in further steps of an algorithm.

The following pseudocode explains disabling bad intersections algorithm:

1. Do this for each intersection of current polygon in intersections:
   compute 2 boolean properties in current intersection: previousInside and nextInside. These properties determine whether the edge that is before the intersection point and the edge that is after the intersection point lies inside the second polygon (not current). In practice, we will be checking whether the point in the middle of the next and previous edge is inside second polygon, using some PIP-check algorithm, for example winding or odd-even algorithm.Important remark: if previous or next edge is collinear with corresponding edge in the second polygon, we mark it always as inside, or always as outside. (we could also mark it as “collinear” and then during second phase use some advanced heuristic how to treat collinear edges, but I won’t cover that method in this article, maybe later…).
2. Now traverse polygon. If we meet an intersection, and when intersection.nextInside == intersection.prevInside then disable this intersection

Remark: To apply this algorithm to curves, we can treat each curve segment as polygon segment. We just have to change the collinearity check to support curves, and the PIP check algorithm should be changed accordingly (e.g. check insideness through bezier subdivision).

As you can see, this simple change repairs Greiner-Hormann and there’s no need for perturbing vertices, as suggested in the original paper and on Wikipedia. Perturbing could generate random results in some cases.