Alpha hulls (wikipedia) are a convenient method for extracting the boundary shape of a set of points. The technique allows you to specify a distance (alpha) over which the surface should be convex. Different spatial scales can be examined in this way. RIP Benoît.

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.

Installation

Download the Alpha Hulls archive and unpack it into a directory on your Matlab path.

Usage

[triHull, vbOutside, vbInside] = ...
AlphaHull(mfPoints, fAlphaRadius <, triDelaunay>)

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.