Sunday, 20 January 2013

Alpha Shapes in Python

Alpha shapes include convex and concave hulls. Convex hull algorithms are ten a penny, so what we're really interested in here in the concave hull of an irregularly or otherwise non-convex shaped 2d point cloud, which by all accounts is more difficult.

The function is here:

The above is essentially the same wrapper as posted here, except a different way of reading in the data, and providing the option to specify a probe radius. It uses Ken Clarkson's C-code, instructions on how to compile are here

An example implementation:

The above data generation is translated from the example in a matlab alpha shape function . Then:

Which produces (points are blue dots, alpha shape is red line):
and on a larger data set (with radius=1, this is essentially the convex hull):
and a true concave hull:

No comments: