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:

Hi alastaira,

Thanks for sharing. A have one question :

- Where did you find that Triangulate() function ? Did you write it on your own or is it available somewhere ?

Hi Xavier,

It’s a custom function I wrote. It needs a bit of tidying up, which is why I haven’t shared it yet. The logic is not actually too hard – I based my function on the approach described in this article: http://paulbourke.net/papers/triangulate/

Hello

Have you heard about concave hull algorithm by Adriano Moreira et Al? It computes concave hull of a set of points (I think better said “Non convex” hull of a set of points.)

I have implemented it and also I have made some modifications, like a parallelization and the way it selects the canditates to be part of final set.

A demo (some minor errors in the code) can be downloaded from my home page :

https://computacion.cs.cinvestav.mx/~achau/dist.rar

Bye 4 now

Asdrúbal López Chau

Hi Alastair,

I have been looking for pointers on this so am glad to have come across your blog post.

Can you please elaborate on how the circumradius relates to the alpha shape and alpha shape value in this sentence.

“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.”

Thanks,

Sanj.

Hi Alastair,

Thanks very much for your post, it gives me reasonable hope that there is a solution to calculating a “concave hull”.

I have been working on this issue for a while now and I must admit that it is a bit beyond me (high school maths clearly didn’t prepare me!!)

Is there a chance of your posting your functions/procedures that you have created, even with your posts I am really struggling to replicate this.

Thanks very much.

Greg

@greg – I’m including a section on concave hulls in a chapter of the next book I’m writing – I’ll ask the publisher if I can reprint it here (otherwise, I’m afraid you’ll have to buy the book!)

Pingback: The FME Evangelist » FME 2012 Use Case: The Concave Hull and the Alpha

Have you release the concave hull functions you wrote?

Hi Alastaira,

This paper is the origin of the alpha shapes idea as far as I know. http://dl.acm.org/citation.cfm?id=2270180