Volume of 3D polyhedron

Given a set of 3D coordinates, how can one find the volume of the polyhedron that is not necessarily convex?

[Matt J]

What do the 3D coordinates represent? The vertices? I think you would need more information than that. It takes more than the vertices to specify the shape of a non-convex polyhedron.

[Roger Stafford]

Yes, besides the vertices, you need to specify how these are grouped in the various faces of the polyhedron. Once you have that, then the volume can readily be calculated regardless of whether it is convex or not.

[slaiyer]

I only have a point cloud to begin with. Visualizing it mentally, the most "organic" approach I can think of is wrapping a convex hull over it, and the collapsing the nearest triangular facet (from delaunayTriangulation) towards each inner point.

Which begs the question - is there a 3D analogue of the INPOLYGON function for identifying such points?

[Matt J]

Which begs the question - is there a 3D analogue of the INPOLYGON function for identifying such points?

For analyzing whether a point is inside a convex polyhedron, you could use,

http://www.mathworks.com/matlabcentral/fileexchange/10226-inhull

or

http://www.mathworks.com/matlabcentral/fileexchange/30892-representing-polyhedral-convex-hulls-by-vertices-or--in-equalities

For the nonconvex case, there also appear to be several offerings on the File Exchange ( Browse ), but I haven't used any of them.

[Iila]

Yes, besides the vertices, you need to specify how these are grouped in the various faces of the polyhedron. Once you have that, then the volume can readily be calculated regardless of whether it is convex or not.

Roger Stafford, I have a group of faces ready. I just need to find the volume enclosed by the set of faces I have defined. How can I get the readily calculated volume then? Thanks.

[Matt J]

This might help

https://en.wikipedia.org/wiki/Polyhedron#Volume

[Iila]

Thank you. But it doesn't. My polyhedra are concave. I also want to calculate the self intersecting volume, if any.

Answer 1

[Mike Garrity]

One option you might look at is alphaShape. It's similar to convhull, but more general. It will create non-convex shapes.

You use it like this. First I need a simple cloud of points.

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

Then I create my alphaShape, and plot it.

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

But the reason this might be useful for you, is that it has a method that will return the volume of the shape:

volume(shp)

ans =

    27.3914

And another method which will tell you whether other points are inside the shape.

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

[slaiyer]

This seems to be exactly what I was looking for back then. Thanks a lot for your input; cheers!