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?)

image

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:

image

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:

image

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:

image

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:

image

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:

image

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:

image

About these ads
This entry was posted in Spatial, SQL Server and tagged , . Bookmark the permalink.

9 Responses to Alpha Shapes and Concave Hulls

  1. Xavier says:

    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 ?

  2. 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

  3. Sanjay says:

    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.

  4. Greg says:

    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

    • alastaira says:

      @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!)

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

  6. David says:

    Have you release the concave hull functions you wrote?

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s