Concave Hull

Computing the polygon that represents the area occupied by a set of points in the plane

Click to enlarge


The Concave Hull was developed within the LOCAL Project in response to a specific project requirement.

The Concave Hull is a tool that can be used to compute the envelope of a set of points in the plane, by generating convex or non-convex polygons that represent the area occupied by the given points (e.g. picture on the right).

 

For certain applications, the convex hull does not represent well the boundaries of a given set of points. The picture above shows one such example. In this case, where the points could represent trees in a forest, the region defined by the convex hull does not represent the region occupied by the trees.

With the Concave Hull algorithm, the region occupied by the trees can be calculated and represented by a non-convex polygon.


Convex Hull

Concave Hull

 

By adjusting one single parameter of the algorithm (k), the user can choose the level of smoothness of the computed polygon. The following two pictures illustrate this functionality.


k=4

k=10

 

The following pictures illustrate how the developed algorithm calculates the concave hull of a given set of points (left), and how a "buffer" can be added to that polygon (right).

Click to enlarge          Click to enlarge

 

The Concave Hull adjusts automatically to variations in the spatial density of the points.

Click to enlarge       Click to enlarge

An implementation of this algorithm is available online here. It can also be integrated into an application through the API available here.

back to Results