calculating alpha shape (concave hull) in Java

Question

Using Java, I would like to calculate the alpha shape: given a set of 2D points, I want to find a list of polygons with minimal area that contain all the points. Here is some more information. A pure Java solution would be ideal. Code that I can port from other languages to Java would be fine. I'd rather not use a native wrapper. An explanation of the algorithm that I could implement with reasonable effort would also be fine.

What I really need are the triangles that make up the alpha shape polygons, so extra credit for that.

Answer 1

This page has a nice Java applet with GPL source that does what you want. There's also the full paper describing the algorithm further down.

It doesn't do the triangle tessellation part, but there are many available libraries for that once you have a polygon. If nothing else, openGl has an excellent tessellator you can use or pull from.