2
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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|. $$

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

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Alexander Shenkin May 20 '14 at 21:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.