Combined area of overlapping circles

Question

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?

Answer 1

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.

Answer 2

Depending on what problem you are trying to solve it could be sufficient to get an upper and lower bound. An upper bound is easy, just the sum of all the circles. For a lower bound you can pick a single radius such that none of the circles overlap. To better that find the largest radius (up to the actual radius) for each circle so that it doesn't overlap. It should also be pretty trivial to remove any completely overlapped circles (All such circles satisfy |P_a - P_b| <= r_a) where P_a is the center of circle A, P_b is the center of circle B, and r_a is the radius of A) and this betters both the upper and lower bound. You could also get a better Upper bound if you use your pair formula on arbitrary pairs instead of just the sum of all the circles. There might be a good way to pick the "best" pairs (the pairs that result in the minimal total area.

Given an upper and lower bound you might be able to better tune a Monte-carlo approach, but nothing specific comes to mind. Another option (again depending on your application) is to rasterize the circles and count pixels. It is basically the Monte-carlo approach with a fixed distribution.

Answer 3

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.

Answer 4

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.

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

Answer 5

There are efficient solutions to this problem using what are known as power diagrams. This is really heavy math though and not something that I would want to tackle offhand. For an "easy" solution, look up line-sweep algorithms. The basic principle here is that that you divide the figure up into strips, where calculating the area in each strip is relatively easy.

So, on the figure containing all of the circles with nothing rubbed out, draw a horizontal line at each position which is either the top of a circle, the bottom of a circle or the intersection of 2 circles. Notice that inside these strips, all of the areas you need to calculate look the same: a "trapezium" with two sides replaced by circular segments. So if you can work out how to calculate such a shape, you just do it for all the individual shapes and add them together. The complexity of this naive approach is O(N^3), where N is the number of circles in the figure. With some clever data structure use, you could improve this line-sweep method to O(N^2 * log(N)), but unless you really need to, it's probably not worth the trouble.

Answer 6

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.