MATLAB: Calculate volume of concave polyhedron from set of scattered 3D points

Question

I have 20 to 30 randomly generated 3D points as vertices from which a polyhedron is defined. I have tried using DelaunayTri(points) to enumerate the facets and use the determinant of the cross product to calculate and sum the tetrahedral volumes, but I'm not sure it works fine for polyhedra which are not convex.

Another possible approach would be to partition the concave polyhedron into convex ones (by detecting points which are inside the convex hull), but an algorithm for such disjoint partitioning eludes me.

Also, how would one plot such a concave hull?

Answer 1

With thanks to Mike Garrity from MATLAB Answers™

alphaShape is similar to convhull, but more general. It will create non-convex shapes.

Sample point cloud:

npts = 75;
pts = randn(npts,3);
scatter3(pts(:,1),pts(:,2),pts(:,3),'filled')

shp = alphaShape(pts);
h = plot(shp);

Alpha shape plot:

Volume of alpha shape:

volume(shp)

ans =
    27.3914

Another method to indicate other points inside the shape (in green):

testpts = randn(150,3);
inmask = inShape(shp,testpts);
h.FaceColor = [.75 .75 .75];
h.FaceAlpha = .25;
hold on
scatter3(testpts(inmask,1),testpts(inmask,2),testpts(inmask,3),'.','MarkerEdgeColor','green')
scatter3(testpts(~inmask,1),testpts(~inmask,2),testpts(~inmask,3),'.','MarkerEdgeColor','red')