A very fast **2D concave hull** algorithm in JavaScript (generates a general outline of a point set).

```
var points = [[10, 20], [30, 12.5], ...];
var polygon = concaveman(points);
```

Signature: `concaveman(points[, concavity = 2, lengthThreshold = 0])`

`points`

is an array of`[x, y]`

points.`concavity`

is a relative measure of concavity.`1`

results in a relatively detailed shape,`Infinity`

results in a convex hull. You can use values lower than`1`

, but they can produce pretty crazy shapes.`lengthThreshold`

: when a segment length is under this threshold, it stops being considered for further detalization. Higher values result in simpler shapes.

The algorithm is based on ideas from the paper A New Concave Hull Algorithm and Concaveness Measure for n-dimensional Datasets, 2012 by Jin-Seo Park and Se-Jong Oh.

This implementation dramatically improves performance over the one stated in the paper
(`O(rn)`

, where `r`

is a number of output points, to `O(n log n)`

)
by introducing a fast *k nearest points to a segment* algorithm,
a modification of a depth-first kNN R-tree search using a priority queue.

TypeScript type definitions
are available through `npm install --save @types/concaveman`

.

- monotone-convex-hull-2d for the convex hull algorithm
- rbush for point indexing
- tinyqueue as a priority queue
- point-in-polygon for point in polygon queries
- robust-orientation for 3-point orientation tests

In 2019, a C++ port has been created, allowing for efficient usage from C/C++, Python (via cffi) and other languages featuring an FFI and/or plug-in mechanism for C (e.g. a MATLAB MEX file should be easy to prepare).

Great Documentation0

Easy to Use0

Performant0

Highly Customizable0

Bleeding Edge0

Responsive Maintainers0

Poor Documentation0

Hard to Use0

Slow0

Buggy0

Abandoned0

Unwelcoming Community0

No reviews found

Be the first to rateNo alternatives found

No tutorials found

Add a tutorial