Concave Hull: Definition, Algorithms and Practical Solutions

Question

Convex Hull

A convex hull of a shape is defined as:

In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X (Wikipedia)

Wikipedia visualizes it nicely using a rubber band analogy (image below), and there are some good algorithms to compute it.

Concave Hull

A concave hull is visualized using the red line in the image below (the blue line visualizes the convex hull). Intuitively, it is a polygon which embraces all the points, but has less (minimal?) area compared to the convex hull. As a result, the polygon's line length is longer.

A concave hull may be the solution for some real-world problems (e.g. finding the reasonable boundary of a city).

I have failed to find a proper definition, algorithm and practical solution for the notion of a Concave Hull. The Grass Wiki has some descriptions and images, and there is a commercial solution in concavehull.com.

Any ideas, algorithms and links will be very much appreciated.

Adam

Answer 1

As scw points out, you want an implementation of α-shapes.

Alpha shapes can be considered a generalisation of the convex hull. They were first described in 1981 in:

Edelsbrunner, H.; Kirkpatrick, D.; Seidel, R.; , "On the shape of a set of points in the plane," Information Theory, IEEE Transactions on , vol.29, no.4, pp. 551- 559, Jul 1983

Open source implementations exist for the environments you are interested in:

PostGIS

If you are using the PostGIS stack, pgRouting's optional Driving Distance extension exposes an alpha shape implementation. I'm not sure if you can vary the alpha parameter, however.

Usage is below:

SELECT the_geom AS alpha_shape 
FROM 
  points_as_polygon(
    'SELECT id, ST_X(your_geom) AS x, ST_Y(your_geom) AS y FROM your_table');

Python

There are probably many python modules you could use. I have heard good things about CGAL, a C++ computational geometry library. Python wrappers exist for parts of CGAL, including exposing CGAL's alpha shape implementation to Python.

Be aware that parts of CGAL are licensed under the QPL, which means that if you distribute your program, linked to CGAL, you may need to release it under the QPL. It is fine to keep your code proprietary if you do not redistribute your program code or binaries.

Answer 2

Here is what you are looking for.

You can download and test the program: (in java, under GPL license)

The paper presenting the algorithm is there:

Duckham, M., Kulik, L., Worboys, M.F., Galton, A. (2008) Efficient generation of simple polygons for characterizing the shape of a set of points in the plane. Pattern Recognition v41, 3224-3236

Answer 3

This seems to be a specific application of alpha shapes, which are from my reading a more general form of this problem. R has the alphahull module, which has excellent documentation on computing alpha shapes. Also check this detailed background on alpha shapes. If you only want to compute convex/concave hulls, check out lasboundary, part of lastools, it scales well and can handle millions of input points.

Finally, this interesting application of alpha shapes by Flickr made the rounds a while ago, showing their utility for aggregating user generated point content:

Answer 4

There is an implementation of ST_ConcaveHull in PostGIS trunk. http://postgis.org/documentation/manual-svn/ST_ConcaveHull.html

/Nicklas

Answer 5

JTS (http://tsusiatsoftware.net/jts/main.html) provides a Convex Hull implementation. Martin Davies also mentioned having an Alpha Shape algorithm in the works so you might want to check the SVN repository to see if it is in yet if that's what you want.

Answer 6

About R implementation Alpha-Shapes, there's an article about "Converting Alpha-Shapes into SP Objects"

It's based on alphahull, sp and spgrass6 http://casoilresource.lawr.ucdavis.edu/drupal/node/919

Answer 7

Speaking about JTS, you can use Geoscript for manipulating JTS library. http://geoscriptblog.blogspot.com/2010/06/unwrapped-jts-with-python.html for an article about convex hull. GeoScript implementations are available in JavaScript, Python, Scala, and Groovy. The official website : http://geoscript.org

Answer 8

There is also script for ArcInfo 10.

Answer 9

I created a highly-efficient tool, called lasboundary, that computes a concave hull for LIDAR in LAS/LAZ/ASCII format and stores the result as a vector boundary polygon in ESRI Shapefile format or a geo-referenced KML file.

Here is an example run:

C:\lastools\bin>lasboundary -i SerpentMound.las -o SerpentMound_boundary.shp
reading 3265110 points and computing convex hull for 3265110 points
growing inward towards concave hull (with concavity = 50)
outputting the concave hull
concave hull has 1639 points

Some result pictures are here.