Concave HullComputing the polygon that represents the area occupied by a set of points in the plane
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 nonconvex 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 nonconvex polygon.
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.
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).
The Concave Hull adjusts automatically to variations in the spatial density of the points. An implementation of this algorithm is available online here. It can also be integrated into an application through the API available here.
