Hull Save

Hull.js is a JavaScript library that builds concave hull by a 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.

NPM package

This library is hosted on GitHub Packages. To install it using NPM, you should have an .npmrc file next to your package.json with the following content:

@andriiheonia:registry=https://npm.pkg.github.com
//npm.pkg.github.com/:_authToken=YOUR_GITHUB_TOKEN

And include hull library as a dependency to your package.json:

"@andriiheonia/hull": "^1.0.8"

For more details see GitHub instruction.

If for some reason you don't want to use GitHub Packages, you can use GitHub URL as a dependency, e.g.:

"@andriiheonia/hull": "andriiheonia/hull"

Development

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

TypeScript

You can find TypeScript type definitions in src folder.

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