See also http://www.dylan-muir.com/articles/alpha_hulls/
Usage: [triHull, vbOutside, vbInside] = AlphaHull(mfPoints, fAlphaRadius , triDelaunay)
This function computes the alpha shape / alpha hulls of a set of points; both the external hull as well as interior voids. The Matlab parfor construct is used by the function, so that this code will run quickly on a machine running several instances of the Matlab parallel computing toolbox.
This algorithm is based on qhull and the delaunay tetrahedralisation of the set of points. It will return a hull triangulation, and ignore points connected only by a line.
'mfPoints' is an Nx3 matrix, where each row defines a point in 3-space. AlphaHull will find the hull of the set of points in 'mfPoints'.
'fAlphaRadius' is a scalar distance which defines the parameter alpha of the alpha hull. This distance is interpreted as the radius of a sphere that will "roll around" the surface, with the boundary of the sphere touching one to three of the points in 'mfPoints'. The triangles of the Delaunay tetrahedralisation where the spere can fit without intersecting any other points will form part of the alpha hull.
The optional parameter 'triDelaunay' can be used to provide the Delaunary tetrahedralisation of the set of points, if it is known in advance.
'triHull' will be a triangulation containing triangles that fall either on the alpha hull surface, or on the inside surface of an alpha void (a hole) within the point set. The boolean vectors 'vbOutside' and 'vbInside' define which rows of 'triHull' define "outside" and "inside" hulls. The surfaces returned by AlphaHull will be convex to the space parameter alpha.
'triHull' will be a Tx3 matrix, where each row ['p1' 'p2' 'p3'] defines a triangle on an alpha surface. The indices 'pn' refer to rows in 'mfPoints', and so define triangles including three of the original points.
* Caveats and room for improvement *
The method for labelling "inside" and "outside" triangles is not ideal. It works by deciding whether the normal of a triangle, in the direction away from the rest of the point cloud, points in the direction of the point set centroid. A better technique might be to iterate along the surface, labelling triangles consistently as you go. If you improve on this, I'd love to hear about it. |