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 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?2012-01-05
  • 0
    @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.2012-01-05
  • 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.)2012-01-05
  • 0
    You might get more answers by asking on http://scicomp.stackexchange.com/2012-01-12

2 Answers 2