Combined area of overlapping circles

Solution 1:

Find all circle intersections on the outer perimeter (e.g. 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.

circle overlap

Solution 2:

I'm sure there is a clever algorithm, but here's a dumb one to save having to look for it;

put a bounding box around the circles;
generate random points within the bounding box;
figure out whether the random point is inside one of the circles;
compute the area by some simple addition and division (proportion_of_points_inside*area_of_bounding_box).

Sure it's dumb, but:

you can get as accurate an answer as you want, just generate more points;
it will work for any shapes for which you can calculate the inside/outside distinction;
it will parallelise beautifully so you can use all your cores.

Solution 3:

Ants Aasma's answer gave the basic idea, but I wanted to make it a little more concrete. Take a look at the five circles below and the way they've been decomposed.

Example

The blue dots are circle centers.
The red dots are circle boundary intersections.
The red dots with white interior are circle boundary intersections that are not contained in any other circles.

Identifying these 3 types of dots is easy. Now construct a graph data structure where the nodes are the blue dots and the red dots with white interior. For every circle, put an edge between the circle middle (blue dot) and each of its intersections (red dots with white interior) on its boundary.

This decomposes the circle union into a set of polygons (shaded blue) and circular pie pieces (shaded green) that are pairwise disjoint and cover the original union (that is, a partition). Since each piece here is something that's easy to compute the area of, you can compute the area of the union by summing the pieces' areas.

Solution 4:

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 :

inside at least one circle, then mark the cell as full,
outside all circles, mark the cell as empty,
else mark the cell as partial.

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.

Solution 5:

I love the approach to the case of 2 intersecting circles -- here's how i'd use a slight variation of the same approach for the more complex example.

It might give better insight into generalising the algorithm for larger numbers of semi-overlapping circles.

The difference here is that i start by linking the centres (so there's a vertice between the centre of the circles, rather than between the places where the circles intersect) I think this lets it generalise better.

(in practice, maybe the monte-carlo method is worthwhile)

alt text
_{(source: secretGeek.net)}