## concaveman

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

### Usage

`var points = 10 20 30 125 ...;var polygon = ;`

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.

### Algorithm

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

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

.

### Dependencies

- 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

### C++ Port

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).