How to calculate volume of non-convex polyhedron?

I need to calculate volumes of not-necessarily-convex polyhedrons defined by x,y,z coordinates. In reality, these are shapes of tree crowns. We have points on the perimeter of the crowns (usually around 8 - 15 points, taken in clockwise fashion), and one top and one bottom point.

I have seen this page: http://www.ecse.rpi.edu/~wrf/Research/Short_Notes/volume.html, (link via Archive.org) but I'm not sure if those algorithms are valid for non-convex polyhedrons.

Any suggestions would be greatly appreciated!

Thanks, Alex

There is a very clean and algorithmic way to do this. I will assume that the boundary of your polyhedron $P$ is a polyhedral surface. The first thing to do is to figure out orientation of the faces of $P$, i.e., correct cyclic ordering of their vertices. This has to be done in such a manner that if two faces meet along an edge, then this edge is assigned opposite orientations by the faces. For instance, if you have faces $ABCDE, DEFG$, sharing the edge $DE$, then you would have to reorient the face $DEFG$: Use the orientation $GFED$ instead. This is a purely combinatorial procedure which should not be too hard.

Next, I assume (for simplicity) that your polyhedron lies in the upper half-space $z>0$ (otherwise, replace $P$ by its translate). For each face $\Phi=[A_1A_2...,A_m]$ of $P$ consider its projection $\Phi'$ to the $xy$-plane and determine if the projection has the counter-clockwise cyclic ordering or not. If it does, mark $\Phi$ with $+$, if not, mark it with $-$. (Projection is done by simply recording $xy$-coordinates of the vertices of $\Phi$.) This part would be easy for a human, but there is also an algorithm for it which I can explain. Call this sign $sign(\Phi)$.

After this marking is done, for each face $\Phi$ of $P$ consider the convex solid $S_\Phi$ which lies directly underneath $P$ and above the $xy$-plane. Compute its volume, call it $v(\Phi)$: $$v(\Phi)=\int_{\Phi'} zdxdy$$ where $z=ax+ by+c$ is the linear equation which defines the face $\Phi$.

Lastly, $$vol(P)=\left|\sum_{\Phi} \operatorname{sign}(\Phi) v(\Phi)\right|$$ is the volume of your polyhedron $P$.

Edit. Here is a slightly more efficient solution assuming that each face $\Phi$ of $P$ is a triangle. First, you have to orient faces of $P$ as above. For each face $\Phi=ABC$ of $P$ define the determinant $$d(\Phi)=\det(A, B, C)$$ where vectors $A, B, C$ are columns of the 3-by-3 matrix whose determinant we are computing. Then $$vol(P)=\left|\sum_{\Phi} d(\Phi)/6\right|.$$

• The determinant formula in your edit is wrong: It misses a normalizing factor of 1/6. – A.Sh Sep 6 '16 at 15:08
• @A.Sh: Yes, of course, I added the missing factor. – Moishe Kohan Sep 6 '16 at 17:14

Since it seems that you want to solve the problem for a particular situation, rather than finding a general algorithm, perhaps you find acceptable to do the hard work yourself. Splitting a non-convex polyhedron in convex parts is much easier for a human than for a computer. Do it yourself, compute their volumes and add'em aup.

• Thanks ajotatxe. I need to do this for up to one thousand polyhedrons. Probably a bit much to split them up manually, unless no algorithm exists. – Alexander Shenkin May 20 '14 at 21:15