# Calculating the concave hull of a point data set (Python and R)

Following the calculation of a convex hull as described a few weeks ago, I’ve worked up a way to approximate a “concave” hull. This can be useful for point clouds of complicated geometries. Whereas the convex hull is a well defined concept, concave hulls are less so, verging on the subjective. That’s why I keep using “ “ around “concave hull”.

So, considering this potential subjectiveness, the method here actually calculates the hull from an applied kernel density function. The first thing to do is to calculate your kernel density function for a point cloud, which I’ve facilitated in R (albeit after reading this):

Python is then used to acquire contours from the density surface created above in R. This is all simplified from the main program to get to the point (I have integrated numerous checks through developing plots etc. The full program is available on github but the info below should suffice…) Firstly, you’ll need the following imports:

Everything is then called by the following driver script:

This driver function calls the following functions. The first simply pulls in the density data created in R into variables:

The x,y,z data is then gridded and logged:

The logged density grid is then smoothed using a gaussian filter and the extent of the grid is acquired:

The smoothed density grid is then contoured - the “level” variable is user set and must be specific to YOUR data and YOUR area/density contour of interest. It would be wise to actually view this plot and maybe cycle a number of density contour levels to know exactly what hull you are mapping:

Such a plot could look like this: Equally, you WOULDN’T want it to look like this: Now you have a contour that you have hopefully checked! The next thing to do is to get the vertices of the contour line - these form the xy coordinates of your “concave” mask:

You can now save and export these lists. You now have the coordinates of your concave hull boundary.

Written on December 12, 2014