Home

Awesome

concaveman

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

Build Status Coverage Status

<img width="570" alt="sample concave hull" src="https://cloud.githubusercontent.com/assets/25395/12975726/ada2ad10-d0c6-11e5-96c8-6e42c995e0e2.png">

Usage

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

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

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 through npm install --save @types/concaveman.

Dependencies

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