concaveman
A very fast 2D concave hull algorithm in JavaScript (generates a general outline of a point set).
Usage
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 than1
, 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 ndimensional Datasets, 2012 by JinSeo Park and SeJong 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 depthfirst kNN Rtree search using a priority queue.
TypeScript
TypeScript type definitions
are available through npm install save @types/concaveman
.
Dependencies
 monotoneconvexhull2d for the convex hull algorithm
 rbush for point indexing
 tinyqueue as a priority queue
 pointinpolygon for point in polygon queries
 robustorientation for 3point 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 plugin mechanism for C (e.g. a MATLAB MEX file should be easy to prepare).