Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
You should be more specific. How are the bodies represented? As polyhedra? Parametrically as $(x,y,z) = f(u,v)$? In implicit form as $f(x,y,z) = 0$? Or something else? –  Rahul Jan 5 '12 at 10:20
    
@RahulNarain The objects are basic - spheres, cubes, cones etc. So the representation is whatever you want, the goal is just to have the simplest program. –  Yrogirg Jan 5 '12 at 10:31
1  
If you can implement a test that tells whether an arbitrary cube is entirely inside, entirely outside, or partially intersecting any one of your primitives, then you can just to put a grid around your geometry and count the filled boxes. (For direct control of accuracy, use an octree and recursively subdivide partially occupied cells.) –  Rahul Jan 5 '12 at 15:39
    
You might get more answers by asking on scicomp.stackexchange.com –  David Ketcheson Jan 12 '12 at 14:43
add comment

2 Answers

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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