computational geometry - Finding a Concave Hull

I have 3D clustered data:

Is there any other way to get the concave hull of 3D data points?

Answer

Here's a possible approach.

First use TetGen to tetrahedralize the data:

Needs["TetGenLink`"]

{pts, tetrahedra} = TetGenDelaunay[data3D];

Next define a function to compute the radius of the circumsphere of a tetrahedron (formula from Wikipedia)

csr[{aa_, bb_, cc_, dd_}] := 
 With[{a = aa - dd, b = bb - dd, c = cc - dd},
  Norm[a.a Cross[b, c] + b.b Cross[c, a] + c.c Cross[a, b]]/(2 Norm[a.Cross[b, c]])]

Now calculate the radius of each tetrahedron in your data, and define a function to pick out only those tetrahedra with radius below a given threshold:

radii = csr[pts[[#]]] & /@ tetrahedra;
alphashape[rmax_] := Pick[tetrahedra, radii, r_ /; r < rmax]

This function converts a tetrahedron into a list of 4 triangular faces:

faces[tetras_] := 
 Flatten[tetras /. {a_, b_, c_, d_} :> {{a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}}, 1]

We also need to remove internal polygons. Internal polygons appear twice, since they belong to two tetrahedra, so we simply need to prune the list of faces to those which only appear once in the list.

externalfaces[faces_] := Cases[Tally[Sort /@ faces], {face_, 1} :> face]

Now we can generate the graphics for a particular value of rmax

polys = externalfaces@faces@alphashape[2.0];

Graphics3D[GraphicsComplex[pts, Polygon@polys], Boxed -> False]

Here's an animation showing the effect of different values of rmax