geo

geo copied to clipboard

As noted in #541, there is an interest in making the concave hull algorithm converge with the implementation in concaveman. Since, the current implementation diverges by avoiding the use of a linked list and preferring use of RTree over an implementation closer to Concaveman's, it would probably be necessary to re-write the algorithm.

Note that, in the meanwhile, https://github.com/georust/geo/pull/635 (k nearest neighbors concave hull) has been merged.

The backstory on this issue, as I remember it...

Our first concave hull algorithm was introduced in https://github.com/georust/geo/pull/480

It was based on https://github.com/mapbox/concaveman, which, I believe, is widely used and often faster than the knn approach.

However, our implementation's behavior diverges from the mapbox reference implementation in some cases.

I'm going to rename the issue to clarify what I understand this issue to be about.