Fast Alpha Hulls (alpha shapes in 3d; parfor enabled)

version 1.8.0.0 (3.23 KB) by Dylan Muir
Compute the alpha hulls (exterior and interior) of a set of points.

2.1K Downloads

Updated 29 Aug 2017

View License

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 ma­trix, where each row de­fines a point in 3-space. AlphaHull will find the hull of the set of points in 'mfPoints'.

'fAlphaRadius' is a scalar dis­tance which de­fines the pa­ra­me­ter alpha of the alpha hull. This dis­tance is in­ter­preted as the ra­dius of a sphere that will "roll around" the sur­face, with the bound­ary of the sphere touch­ing one to three of the points in 'mfPoints'. The tri­an­gles of the De­lau­nay tetra­he­dral­i­sa­tion where the spere can fit with­out in­ter­sect­ing any other points will form part of the alpha hull.

The op­tional pa­ra­me­ter 'triDelaunay' can be used to pro­vide the De­lau­nary tetra­he­dral­i­sa­tion of the set of points, if it is known in ad­vance.

'triHull' will be a tri­an­gu­la­tion con­tain­ing tri­an­gles that fall ei­ther on the alpha hull sur­face, or on the in­side sur­face of an alpha void (a hole) within the point set. The boolean vec­tors 'vbOutside' and 'vbInside' de­fine which rows of 'triHull' de­fine "out­side" and "in­side" hulls. The sur­faces re­turned by AlphaHull will be con­vex to the space pa­ra­me­ter alpha.

'triHull' will be a Tx3 ma­trix, where each row ['p1' 'p2' 'p3'] de­fines a tri­an­gle on an alpha sur­face. The in­dices 'pn' refer to rows in 'mfPoints', and so de­fine tri­an­gles in­clud­ing three of the orig­i­nal points.

* Caveats and room for improvement *
The method for la­belling "in­side" and "out­side" tri­an­gles is not ideal. It works by de­cid­ing whether the nor­mal of a tri­an­gle, in the di­rec­tion away from the rest of the point cloud, points in the di­rec­tion of the point set cen­troid. A bet­ter tech­nique might be to it­er­ate along the sur­face, la­belling tri­an­gles con­sis­tently as you go. If you im­prove on this, I'd love to hear about it.

Cite As

Dylan Muir (2022). Fast Alpha Hulls (alpha shapes in 3d; parfor enabled) (https://www.mathworks.com/matlabcentral/fileexchange/32725-fast-alpha-hulls-alpha-shapes-in-3d-parfor-enabled), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2008b
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!