I’ve heard a number of people praise the Greiner-Hormann algorithm for clipping arbitrary polygons. They say it has a certain conceptual simplicity and elegance.
@jasondavies is utilizing Greiner-Hormann for D3’s polygon clipping operations (2D and spherical). He recently gave a demo of boolean operations on polygons based on as-of-yet unreleased work here.
His earlier clipping demos can be found here and here.
@w8r has a nice, clean implementation of the algorithm for 2D clipping operations with no dependencies. He provides an adapter for clipping polygon regions defined on leaflet maps.
Overview of the algorithm
The following is an extract from Greiner and Hormann’s paper, Efficient Clipping of Arbitrary Polygons, describing how the clipping algorithm works at a high level.
The process of clipping an arbitrary polygon against another arbitrary polygon can be reduced to finding those portions of the boundary of each polygon that lie inside the other polygon. These partial boundaries can then be connected to form the final clipped polygon.
To clarify this, consider the example in Figure 4: the task is to clip the polygon with the dotted lines (referred to as the subject polygon S) against the polygon with the broken lines (referred to as the clip polygon C). We start by determining which parts of the subject polygon boundary lie inside the clip polygon (Figure 5). We can find the parts by considering the following analogous situation: imagine pushing a chalk cart along the subject polygon boundary. We start at some vertex of the polygon, and open the distribution hatch at the start if the vertex lies inside the clip polygon. We then push the cart along the subject polygon toggling the position of the hatch (open/closed) whenever we cross an edge of the clip polygon. We stop when we reach our starting vertex. Then the parts of the subject polygon that lie inside the clip polygon will be marked with chalk.
We use the same technique, but this time running our chalk cart along the clip polygon in order to discover those parts of the clip polygon that lie inside the subject polygon (Figure 6).
Once we have found all the parts of the polygon edges that lie inside the other polygon, we merge the parts to obtain the clipped polygon (Figure 7).
The process of merging is easy, considering the fact that each part of the subject polygon that will be in the outcome is bounded by two intersection points of subject and clip polygon. These vertices are also the beginning or end of one of the clip polygon’s relevant parts. Therefore, if you keep track of the intersection points and the parts they come from, connecting the supporting parts in the correct order is easy (shown in Section 5).
Set-theoretic difference and the union of the two polygons can also be calculated by making the following modification to the algorithm. To determine S \ C , one first marks the parts of the subject polygon that are exterior to the clip polygon. These will be merged with the relevant parts of the clip polygon (the procedure is illustrated in the left part of Figure 8). Determination of the union is sketched in the middle of Figure 8 and the right part of Figure 8 shows how the difference C \ S can be obtained.
The authors note the decisive step in the algorithm:
The algorithm first needs to determine all the intersections between the two input polygons (a “clipper” and “clippee”). Merging these intersection points into the data structure is the decisive step.