3
$\begingroup$

The task should be very common, what are the best and easiest to implement algorithms to compute the volume of union/intersection of given bodies? Or union/intersection area for 2D figures.

I don't mean straightforward integration to get the volume, it shouldn't be very convenient. I was thinking about some kind of naive Monte Carlo (the ratio of hit to thrown points), but it has very poor convergence. Or maybe approximating bodies as unions of simpler ones, for which the intersections are known, though it's (a bit) complex.

  • 0
    You might get more answers by asking on http://scicomp.stackexchange.com/2012-01-12

2 Answers 2

3

I've ended up using the algorithm described in the article "Approximating the volume of unions and intersections of high-dimensional geometric objects" by Karl Bringmann and Tobias Friedrich. The idea is quite simple and easy to implement.

UPD It is the algorithm to compute a volume of unions that is quite simple and easy to implement. For intersections things are much more complicated.

3

I will consider only intersections, because that tends to be much easier, and intersections of convex bodies results in a convex body. The case of unions is much harder since convexity and topology are not preserved.

Since you indicated you only deal with simple shapes, then you should just implement some primitive operations like computing the intersecting area between two triangles, and between a triangle and a circle. I have implemented both here. There are LOTS of special cases.

Actually, instead of triangle-triangle, I just find areas between two convex polygons. This allows you to deal with intersections between any pair of shapes with piecewise linear edges (just triangulate it and sum up contributions), circles, and ellipses (which is a circle under an affine transformation).

In 3D, you would want to implement tetrahedron-tetrahedron intersection and tetrahedron-sphere intersection. The former is "simple" but there are lots of special cases. The latter is merely possible (I have thought about it, and it will be very hard to implement).