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