4

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?

Slaiyer
  • 444
  • 8
  • 22

1 Answers1

2

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')

Sample point cloud

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

Alpha shape plot:

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')

Points inside shape in green

Slaiyer
  • 444
  • 8
  • 22
  • Are you aware of any method to compute this for n-dimensional data? – Dr. No Apr 18 '17 at 00:35
  • 1
    @JohnD I'm afraid I'm not, but if `convhulln` doesn't suffice, [this excerpt](https://books.google.co.in/books?id=7XUSn0IKQEgC&pg=PA571&lpg=PA571) might have something you could use. Good luck, and please feel free to leave an update here should your efforts succeed. – Slaiyer Apr 18 '17 at 07:20