hull.js

Hull.js - JavaScript library that builds concave hull by set of points.

Examples

See live examples here.

Usage

var points = [ [236, 126], [234, 115], [238, 109], [247, 102], ... ];
hull(points, 50); // returns points of the hull (in clockwise order)

Params

• 1st param - array of coordinates in format: [[x1, y1], [x2, y2], ..., [xn, yn]];
• 2nd param - concavity. 1 - thin shape. Infinity - convex hull. By default 20;
• 3rd param - points format. For example: ['.lng', '.lat'] if you have {lng: x, lat: y} points. By default you can use [x, y] points.

How it works

Let's see step by step what happens when you call hull() function:

1. Hull.js takes your source points of the shape:
   
2. Builds convex hull:
   
3. After that, the edges flex inward (according to the `concavity` param). For example:
   `concavity = 80`
   `concavity = 40`
   `concavity = 20`

Limitations

This library relies on ES6. The ES6 features used are:

• new Set(null), Set#add, Set#has
• let, const
• Math.trunc (if available)

You may use polyfills for Set and compile with babel to continue to support old browsers.

Development

npm install             # install dependencies
npm test                # build dist file and run tests
npm run-script watch    # watch ./src dir and rebuild dist file

Contribute

If you want to get involved with Hull.js development, just use github flow and feel free to contribute!

To-do

• think about holes;
• think about automatic concavity adjustment based on density.

Related papers

• Implementation of a fast and efficient concave hull algorithm;
• Computational Geometry: Convex Hulls;
• Andrew's monotone chain convex hull algorithm;
• Line Segment Intersection Algorithm;
• Game Math: "Cross Product" of 2D Vectors;
• Угол между двумя векторами;
• Когда не нужна тригонометрия.

Changelog

1.0.1 — 24.10.2020

Introduced fix that avoids hitting stack size limit on large arrays

1.0.0 — 28.06.2019

Change language level to ES6. Performance improvements.

0.2.11 — 05.05.2019

Return the first point as the last point when fewer than 4 unique points are provided.

0.2.10 — 04.09.2016

Fixed missing "var" declaration

0.2.9 — 28.07.2016

Fixed modification of the initial array, added filtration of the duplicates

0.2.8 — 01.04.2016

Added edgeSkipList to increase performance of the highly accurate shapes (with the small concavity number) + refactoring.

0.2.7 — 01.05.2015

Fixed bower.json

0.2.6 — 01.05.2015

Fixed bower.json

0.2.5 — 01.05.2015

Bower support

0.2.4 — 23.03.2015

Minor fixes (copyrights)

0.2.3 — 04.02.2015

Minor fixes (readme, package.json)

0.2.2 — 04.02.2015

Configurable point formats, now you can use points like {x: 10, y: 10} and {lat: 52, lng: 82}.

0.2.1 — 21.10.2014

Some minor updates (doc, package.json, etc.).

0.2.0 — 20.10.2014

Second version with better performance inspired by this article.

0.1.0 — 06.09.2014

First version based on Delaunay triangulation.