D3 version 3 includes much better support for clipping geographic features.
Here are a few test cases that I’ve been using to test polygon clipping. Line clipping is much simpler since you don’t need to rejoin the ends to make polygons.
Currently, d3.geo supports two types of clipping region:
Clipping polygons on a sphere is more difficult than on a 2D plane. One challenge is how to determine which side of a boundary should be the polygon’s inside. On an infinite 2D plane, we can assume that the side with a finite area is the inside. In the case of complex polygons, we can use the winding number to handle self-intersections and holes. This involves firing a ray from the query point to a point outside the polygon. We can always pick a point outside the polygon at ∞, e.g. by taking the maximum x- and y-coordinates and going a little further.
However, on a sphere, there is no analagous way to find a point outside the polygon, since a ray on the sphere will eventually arrive where it started. In other words, either side of the boundary has a finite area on a sphere, so you can no longer pick a side based on having a finite area.
Another way to resolve the ambiguity is to pick the side around which the boundary goes clockwise. The exterior polygon boundary should be specified in a clockwise order relative to a point on its inside. Similarly, holes should be anticlockwise.
Another difficulty is that we want to handle polygons that self-intersect. This can occur when using line simplification algorithms, such as Visvalingam–Whyatt.
Thankfully, there is a general clipping algorithm by Günther Greiner and Kai Hormann that handles self-intersecting polygons. The clipping algorithm in D3 is a modified form of this.
There are a few cases where we need to insert an additional, exterior boundary all the way around the clip boundary. These occur when the polygon doesn’t intersect with the clip edge at all: