mbostock/d3 — pull request #706 by jasondavies (2012-07-09 12:53:17+00:00)
Title: Fix d3.geo.circle clipping.

This uses a new algorithm, based on Weiler-Atherton. The difference is
that we only need to clip against a single line (the circle), so this
simplifies things somewhat. Rough summary:

1. For each ring in each polygon, intersect with the circle and generate
an array of segments. This same routine is used on its own for
LineString and MultiLineString features.
2. Since we're dealing with closed polygons, we check the first and last
segment to see if they should be merged into one.
3. Create a circular linked list containing the intersection points, in
clockwise order of their position on the circle. For each start
point, include a reference to the end point.
4. Finally, traverse the linked list, starting with an entering
intersection point, inserting the segment and then following the
reference to the end point. Then, interpolate along the circle edge
to the next (clockwise) point, which should always be an entering
point, and repeat until the start point is reached. The resulting
ring is added as a polygon.
5. Continue with step 3 until all entering points have been visited.

To do: assign holes to their correct polygons, perhaps using winding
numbers. At the moment holes are essentially added as separate polygons,
which works for drawing since they're in anticlockwise order.

Fixes #691.