d3-polygon

d3-polygon copied to clipboard

Is it worth having some sort of polygon clipping functionality?

Note: d3-voronoi implements its own clipping of infinite cells. And d3-geo-projection will need to have an equivalent of d3.geo.clipExtent.

I think it is worth it, and I am very surprised to see it gone. polygon clipping is a nasty enough problem that I don't want to have to solve it in my application.

You can clip to an axis-aligned rectangle using d3.geoIdentity: https://bl.ocks.org/mbostock/5b2a1d47ae020b9533c24129ada97ff0

You can save the result using d3.geoProject or geoproject: https://bl.ocks.org/mbostock/ffbe45ba1dfc5ebd56b7f4cfdac9b71a

Lastly, here is a trival port of Sutherland–Hodgman clipping from v3: https://bl.ocks.org/mbostock/ece50c027bdf8cc20003a17d93e4f60e

Given that Sutherland–Hodgman is limited to convex clip polygons, it doesn’t seem that much more useful than projection.clipExtent. I’d rather see someone contribute a more general clipping algorithm like Weiler–Atherton, Vatti or Greiner–Hormann.

thanks, mike! guess we'll just add polygonClip to d3.jetpack in the meantime :)

These look promising:

• https://github.com/w8r/GreinerHormann
• https://github.com/w8r/martinez

I'm testing the martinez script here https://observablehq.com/@fil/hello-martinez-polygon-clipping and it's quite fast, but seems to be lacking robustness (as evidenced by impressive bleeding in certain cases).

(GreinerHormann is much slower and I wasn't really able to make it work.)

Polygon clipping is a notoriously hard problem to do robustly! I attempted it several times through the years and failed miserably. Perhaps some day we'll get there.

I've been playing with @voidqk Sean Connelly's polybooljs recently. It appears to be much more robust than all the others I've tried so far (but still breaks sometimes in my tests, for no clear reason yet). The explainer written by the author is amazing: https://sean.cm/a/polygon-clipping-pt2

There's a bit of work to do to make it faster, see https://github.com/voidqk/polybooljs/issues/23 for a first step.

Reminds me of when I ran the tests for d3-scale and saw there were a whopping 1,549 tests.

This feels like a problem that can be solved by just adding more and more tests over years.

Here’s how to use d3.geoProject and d3.geoClipRectangle given any GeoJSON object (such as a Polygon):

function clipToRectangle(object, [x0, y0, x1, y1]) {
  return d3.geoProject(object, {
    stream: d3.geoClipRectangle(x0, y0, x1, y1)
  });
}

I think it would be great to have d3.clipPolygon (and a d3.clipConvex test), and document other possibilities (such as https://github.com/voidqk/polybooljs).

I was surprised by the fact that the clipPolygon(clip, subject) mutates subject—it's the only change I made for https://observablehq.com/d/6dbb5b1eb3642147

How did I miss https://github.com/mfogel/polygon-clipping ? A fast and apparently quite robust implementation of Martinez-Rueda-Feito. It is a drop-in replacement for https://github.com/w8r/martinez, and works so much better!

(Contrast https://observablehq.com/@fil/hello-polygon-clipping with https://observablehq.com/@fil/hello-martinez-polygon-clipping)

d3-polygon represents polygons not as GeoJSON objects but rather as arrays of points, where each point is an array of two numbers. Polygon clipping can result in multipolygons. How do you deal with that without changing the way polygons are represented?