Since Darrin Lemmer is stealing my Google juice with his posting of an email I sent to him :-), I’m going to post about that topic here.
Alpha shapes are this pretty cool geometric formalism that can help make sense out of point clouds. I came to them in investigating a nice way to render tri-dexel structures, but that’s a topic for some other time.
The simplest definition I’ve read is that alpha shapes are a generalization of convex hulls, in that they give a tunable parameter which, when set to infinity, produces a convex hull, but when set smaller produces a cell complex that more closely wraps the point set. At its best, subject to a couple of conditions that hold in useful cases, the wrapping is ‘perfect’. Anyway, I’ll let some others explain it, as I haven’t the patience right now, and I do have the links:
The idea behind alpha shapes is explained pretty well on this page, with a nice little Java applet that helps give you an intuitive understanding of it: alpha shape applet.
The implementation I used to play with this some is by Clarkson, at Bell Labs. Note that what this really implements should probably be called ‘alpha solids’. That’s alpha shapes with the interior simplexes removed. That’s generally what you want, but it’s something to be aware of as a difference from other implementations and from the uses of the term in the literature. You’ll probably want to use the ‘-A’ option when playing around to learn what it does; later you may want to use the ‘-aa’ option; in either case don’t forget to use ‘-mxxx’.
This is the alpha shapes page from one of the guys who first wrote up the idea, Ernst Mucke. There’s some (binary) code linked from there too, which is fun to play with but can’t be integrated into your own code without getting the source from them.
There used to be a page at http://www.alphashapes.org/ but I don’t know where it is now. It seems to come and go.
The CGAL library has an alpha shapes implementation that might be more suited to use within an application than the Clarkson code, although it doesn’t seem to do the alpha solids thing, and it has a separate commercial license (but free and OS for non-commercial use).
5 Comments