NOTE: This repository has been deprecated and archived. It is read-only and no longer maintained.

Hull.js is a 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

Expand

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`

NPM package

Since version 1.0.7 this library is not hosted on npmjs.com. You can still use GitHub URL as a dependency to fetch the latest version, but keep in mind that the library has also been archived on GitHub and there are no plans to maintain it. Publishing this library to the public NPM registry under a different name and encouraging other users using unmaintained package is not recommended.

Development

npm install     # install dependencies
npm run test    # run tests and build file for debugging in browser
npm run watch   # watch ./src dir and automatically rebuild file for debugging

TypeScript

You can install third-party TypeScript definitions via npm install --save @types/hull.js.

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

Expand

1.0.12 - 21.12.2024

• Some cleanup before archiving.

1.0.11 - 11.12.2024

• Minor fixes in package.json.

1.0.10 - 07.11.2024

• Fix vulnerability issue.

1.0.9 - 29.10.2024

• Update NPM dependencies to address vulnerability issues.

1.0.8 - 31.05.2024

• Deprecate library on npmjs registry.

1.0.7 - 03.05.2024

Squash previous tiny releases into one bigger commit with the following minor changes:

• Fix issue with formatting when users pass less than 4 points as an input.
• Remove bower and travis files as they are 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

• 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

• Minor changes: return the first point as the last point when fewer than 4 unique points are provided.

0.2.10 — 04.09.2016

• Minor changes: 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) + some refactoring.

0.2.7 — 01.05.2015

• Minor changes: fix bower.json.

0.2.6 — 01.05.2015

• Minor changes: fix bower.json.

0.2.5 — 01.05.2015

• Minor changes: Bower support.

0.2.4 — 23.03.2015

• Minor changes: copyrights.

0.2.3 — 04.02.2015

• Minor changes: readme, package.json.

0.2.2 — 04.02.2015

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

0.2.1 — 21.10.2014

• Minor changes: 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.