Geographic Clipping

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.

Orthographic (90°)

Stereographic (170°)

Equirectangular (antemeridian)

Albers Equal-Area Conic (antemeridian)

Supported Clipping Regions

Currently, d3.geo supports two types of clipping region:

Spherical Polygon Challenges

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.

Clipping Self-Intersections

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.

Inside-Out

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:

  1. The polygon’s visible rings are anticlockwise. The visible rings denote holes, and we need another boundary to ensure they do not get filled. This case is detected by checking the polygon area sign.
  2. Similarly, the invisible rings are anticlockwise. Again, we check the sign of the polygon area. However, since the antipodal point at (±180°, 0°) is projected to ∞, this could cause rings that contain the antipodal point to be inverted. So we rotate longitudinally by 180° so that the antipodal point is the visible region.