A very fast 2D concave hull algorithm in JavaScript
Clone or download
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
test move some files Feb 11, 2016
viz add a viz script Feb 19, 2016
.gitignore add bundle to gitignore Sep 26, 2016
.npmignore move some files Feb 11, 2016
.travis.yml add tests Feb 11, 2016
LICENSE add license title Jul 16, 2016
README.md Update link for typescript definitions (#11) Nov 7, 2018
index.js upgrade rbush & other deps Sep 26, 2016
package.json 1.1.1 Sep 26, 2016

README.md

concaveman

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

Build Status Coverage Status

sample concave hull

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