Generate Concave Hulls with Hull.js

2014-10-28 00:00:00 +0000 by Alex R. Young
This is a guest post written by Andrey Geonya.


Imagine that you have a set of points that form a shape like this:


The points may represent restaurants on a map, pixels after image analysis, etc.

What do you do if you need to display a border around this shape? For example:


The way to solve this is to create a polygon that fits around all of the points. So, in this article we'll see how to solve this problem with the hull.js library.


Hull.js is very simple and consists of just one function that generates concave hull:

var srcPointset = [[168, 180], [168, 178], [168, 179], ...];
var distPointset = hull(srcPointset, 10);

The first argument is the source point set, and the second is the concavity of the hull.

To understand how the second argument works you need to look at how hull.js works. First of all, hull builds a convex hull:

Simple polygon

After that, the edges recursively flex inward while the shape contains edges with lengths less than the concavity argument:

Simple polygon

The second argument can the tuned to optimise the concavity of the resulting shape: Infinity is the least accurate, and 1 is a perfect match.

Enjoy! And feel free to ask questions and suggest improvements.