concaveman

concaveman

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

Usage

import concaveman from 'concaveman';

const points = [[10, 20], [30, 12.5], ...];
const 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.

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

• rbush for point indexing
• tinyqueue as a priority queue
• point-in-polygon for point in polygon queries
• robust-predicates 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).

Similar packages

Other packages similar to concaveman

hull.js

Hull.js is a JavaScript library for computing the convex hull of a set of 2D points. Unlike concaveman, which computes a concave hull, hull.js focuses on convex hulls, which are the smallest convex shape that can enclose all the points.

alpha-shape

Alpha-shape is a library for computing the alpha shape (a generalization of the convex hull) of a set of points. It provides more flexibility in defining the shape of the hull compared to concaveman, which strictly computes concave hulls.

d3-polygon

D3-polygon is part of the D3.js library and provides utilities for polygon geometry, including computing the convex hull of a set of points. While it is more general-purpose and part of a larger visualization library, it does not specifically focus on concave hulls like concaveman.