lyjpeppers / hull Goto Github PK

Hull.js is a JavaScript library that builds concave hull by the set of points.

This library was born in free independent Ukraine. Today not only Ukraine, but the entire international rule-based order is under attack, and you can help to defend it by supporting the Armed Forces of Ukraine via well trusted https://savelife.in.ua/en/ foundation. For other options to help, explore https://ukraine.ua/.

See live examples here.

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

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

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`

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 install     # install dependencies
npm test        # build dist file and run tests
npm run watch   # watch ./src dir and rebuild dist file

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

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

• 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;
• Угол между двумя векторами;
• Когда не нужна тригонометрия.

• Fix issue with formatting when users pass less than 4 points as an input.
• Remove bower.json, as Bower itself is deprecated.

• Clean up .gitignore.
• Add "debug" folder to .npmignore to reduce tarball size.

Introduce fix that avoids hitting stack size limit on large arrays.

• Change language level to ES6.
• Performance improvements.

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

Fix missing "var" declaration.

• Fix modification of the initial array.
• Add filtration of the duplicates.

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

Fix bower.json.

Fix bower.json.

Bower support.

Minor fixes (copyrights).

Minor fixes (readme, package.json).

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

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

Second version with better performance inspired by this article.

First version based on Delaunay triangulation.