Overlap Volume between two polyhedra

Dear all,

I was wondering if there is any algorithm or code to calculate the overlap volume between two convex polyhedra. Thank you in advance.

If an approximation is sufficient, and if you have a function to determine if a point is inside each polyhedron, I could imagine a Monte Carlo algorithm:

  • put the two polyhedra in a box,
  • draw a random point in the box,
  • is it in the polyhedron 1?
  • is it in the polyhedron 2?
  • if it is in both, increment a counter,
  • start again.

The ratio of common random points to the total should lead to the volume of the intersection. Just an approximation and not very fast, but not needing too much geometrical knowledge (although you need the inside() functions).

The pseudo code in this old paper might work if you already have an algorithm for computing the volume of an arbitrary polyhedra.

https://www.sciencedirect.com/science/article/pii/0304397578900518

You might also look at the Graphics Gems software (which will probably be C but its straightforward to translate into Fortran) to see if there is more recent work.

You might also be able to use a 3d clipping algorithm like Sutherland-Hodgman to cut out the resulting volume.