Alpha Shapes and Concave Hulls

One question that gets raised relatively frequently over at the MSDN Spatial forums is how to create a concave hull around a set of points. The answer given is normally the same – while SQL Server provides the STConvexHull() method to determine the convex hull of a geometry, there is no inbuilt nor easy way to determine the concave hull.

One reason for this is that, unlike the convex hull, there isn’t a single concave hull for a given set of points. Consider the following diagram – the orange dotted line clearly represents the convex hull of the set of points, but which of the three yellow lines would you expect to represent the concave hull? (or, would you expect yet a further different possible polygon hull?)

Anyway, considering that this is a relatively common requirement, I thought I’d set about looking at the methods available to determine concave hulls, and came across the concept of alpha shapes.

I’ve yet to find a really good definition of exactly what an alpha shape is, or who first created the concept, but from researching various sources, I can tell you that alpha shapes are created from algorithms that use a single parameter (α)  to create a geometric object representing the broad “shape” of a set of points. As α approaches 0, the alpha shape approaches the original point set. As α increases towards infinity, the alpha shape approaches the convex hull of that set of points. Using an appropriate value of alpha between these limits creates a shape that is not necessarily convex, and may contain one or more holes, but broadly resembles the “shape” implied by the distribution of the set of points.

To start with, I created a MultiPoint set of test data, in which the underlying distribution of points resembled a recognisable shape. When viewed in SQL Server Management Studio (with a buffer of 0.025, to be able to actually see each individual point), it looks like this:

Using SQL Server’s built-in functions, the closest approximation you can get of generalising the overall distribution of this set of points is creating a convex hull using STConvexHull(), which gives you the following (not very accurate) representation:

To create an alpha shape, you first triangulate all the points in the original geometry, so that, rather than having a set of points, you now have a set of tessellating, non-overlapping triangular polygons. The Delauney triangulation of my original MultiPoint looks something a bit like this:

This may look quite chaotic, but triangles are the basis of creating an alpha shape. Once you’ve triangulated the underlying set of points, you define an alpha shape by simply creating a union of all those triangles whose circumradius is less than the stated alpha value.

I wrapped the triangulation and the unioning process into a UDF to try it out with different alpha values. Choosing a small alpha value (in this example, 0.1) will lead to a degenerate geometry consisting of many unconnected islands, as follows:

Choosing too large an alpha value means that the result will instead approach the convex hull of the geometry – effectively joining too much of the point set together. Here’s what my dataset looks like with an alpha value of 1:

By adjusting the value, you can get the most aesthetically, or functionally pleasing outcome you require. For my dataset, an alpha value of 0.24 creates a MultiPolygon that resembles the broad underlying shape of the original pointset, as follows: