hull.js
v1.0.6 geometry concave-hull math alpha-shape algorithm
Hull.js is a JavaScript library that builds concave hull by the 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 default20
; - 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:
-
Hull.js takes your source points of the shape:
-
Builds convex hull:
-
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 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.6 — 12.04.2024
- Exclude "readme-imgs" folder from NPM package.
1.0.5 — 08.02.2024
- Minor fixes (readme, copyrights).
1.0.4 — 17.10.2023
- Remove unused travis file and update readme.
1.0.3 — 05.11.2022
- Fix issue with formatting when users pass less than 4 points as an input.
- Remove bower.json, as Bower itself is deprecated.
1.0.2 — 26.09.2021
- Clean up .gitignore.
- Add "debug" folder to .npmignore to reduce tarball size.
1.0.1 — 24.10.2020
- Introduce 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
- Fix missing "var" declaration.
0.2.9 — 28.07.2016
- Fix modification of the initial array.
- Add filtration of the duplicates.
0.2.8 — 01.04.2016
- Add edgeSkipList to increase performance of the highly accurate shapes (with the small
concavity
number) + refactoring.
0.2.7 — 01.05.2015
- Fix bower.json.
0.2.6 — 01.05.2015
- Fix 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.