search

d3 / d3-polygon

Geometric operations for two-dimensional polygons.
https://d3js.org/d3-polygon
ISC License
97 stars 25 forks source link

Add concaveHull (in addition to convexHull) #21

Closed raphaelschaad closed 5 years ago

raphaelschaad commented 5 years ago

d3-polygon currently has d3.polygonHull(points) that returns the convex hull of the specified points. For some applications, it would be handy to calculate the concave hull of a set of points.

Either, the existing method could add a second parameter type (with currently supported values being convex and concave, or, the existing method could be renamed to d3.polygonHullConvex(points) and a new method d3.polygonHullConcave(points) could be added.

Fil commented 5 years ago

The concave hull is not as easy to define as the convex hull and comes in many flavors (alpha-shape, etc) — a very nice and ultra fast solution is given by @mourner in https://github.com/mapbox/concaveman

mourner commented 5 years ago

Also see https://observablehq.com/@mourner/adaptive-concave-hull for an alternative.

raphaelschaad commented 5 years ago

These are great, thanks. Would it make sense for d3-polygon to implement one of these (being aware there isn't a single solution as there is for convex hull)?

Fil commented 5 years ago

Since the approaches we know all have heavy dependencies, I don't think it would make sense to add any of them to this lightweight module.