DailyJS

DailyJS

The JavaScript blog.


AuthorAndrey Geonya
Featured

libraries graphics

Generate Concave Hulls with Hull.js

Posted on .

This is a guest post written by Andrey Geonya.

Problem

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

Points

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:

Border

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.

Usage

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.