Combined area of overlapping circles
I recently came across a problem where I had four circles (midpoints and radius) and had to calculate the area of the union of these circles.
Example image:
For two circles it's quite easy,
I can just calculate the fraction of the each circles area that is not within the triangles and then calculate the area of the triangles.
But is there a clever algorithm I can use when there is more than two circles?
Find all circle intersections on the outer perimeter (eg B,D,F,H on the following diagram). Connect them together with the centres of the corresponding circles to form a polygon. The area of the union of the circles is the area of the polygon + the area of the circle slices defined by consecutive intersection points and the circle center in between them. You'll need to also account for any holes.
I'm sure there is a clever algorithm, but here's a dumb one to save having to look for it;
Sure it's dumb, but:
For a different solution from the previous one you could produce an estimation with an arbitrary precision using a quadtree.
This also works for any shape union if you can tell if a square is inside or outside or intersects the shape.
Each cell has one of the states : empty , full , partial
The algorithm consists in "drawing" the circles in the quadtree starting with a low resolution ( 4 cells for instance marked as empty). Each cell is either :
When it's done, you can compute an estimation of the area : the full cells give the lower bound, the empty cells give the higher bound, the partial cells give the max area error.
If the error is too big for you, you refine the partial cells until you get the right precision.
I think this will be easier to implement than the geometric method which may require to handle a lot of special cases.
链接地址: http://www.djcxy.com/p/84976.html上一篇: 将N个不同半径的圆圈放置在一个较大的圆圈内,不要重叠
下一篇: 重叠圆圈的组合区域