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?

Tisdale

This is a really interesting problem, I remember seeing this in high school geometry class, but never found a solution. If you can't find an answer here, try posting it at mathoverflow.net and let the mathematicians have a crack at it :P – Parik

how the heck would you ever encounter such problem in real programmer's life? – Denney

sometimes real programmers need real math – Mayfield

How about for working out the answer to this question - "We have sales reps living at these 4 locations, each of whom service an area with these 4 radii. How much of the country do we cover?" If you had a changing database of sales reps, this becomes a programming question! – Gentility

but radius in that situation is a guess - you're more interested in maximum transit time by a salesman to any point in your targeted selling zone. – Jeanene

Actually, this is the kind of problem real programmers like to think about. – Thomajan

@zvolkov: circuit boards are described with a language that plops squares and circles down and optionally drags them. "Calculate the copper area". (This can be needed to calculate etch times, know whether to add scavenging artwork, various things.) – Aho

@AndriyVolkov Programming is encoding solutions, and sometimes solutions need math. – Metagnathous

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

Twoedged

What happens when there is a hole in the center? – Aggiornamento

You'll need to subtract the center connected polygon for the hole from the total and add the circle slices for that polygon to the total. – Twoedged

nice but I guess this will need to a lot of implementation details to handle all the special cases ( circle inside other one, no intersection, holes , one point contact ... ) – Mayfield

The special cases are pretty easy. Circles inside others are discarded by not having any perimeter intersections. One point contact is in effect two intersections with zero distance. Disconnected shapes can be find via connected components algorithm over the graph where two circles are connected if distance of centers is less than sum of the radii. Holes are all polygons except the one with biggest area. Perimeter intersections are all intersections that aren't strictly inside any circle. – Twoedged

yes, but the borders of holes are also (small) arcs. I still think this needs a lot of code to work well. – Mayfield

this is a nice explanation but its got some major problems like someone who pointed out the holes, and furthermore N circles can have N^2 intersections, so it doesn't give a very efficient algorithm at all. – Splenic

@gmatt: It's a very efficient mathematical/geometrical algorithm. Not everything has to be programming related here; theory is just as acceptable. Keep in mind, also, that not every correct algorithm is an efficient one. – Tram

To reiterate: if there's a hole, do the same algorithm suggested by the Ants's picture, but inside-out! Each of its edges is an arc; draw radii from the each end of the arc to the center, and you'll have another polygon (sometimes a star shape). The area of the hole is the area of the star minus the area of the wedges. – Fornax

And if there are two holes? The clustering shown in this problem makes it amenable to a cute solution, but you can build regions of overlapping spheres which have large numbers of holes. – Squall

@Squall See my solution for how to handle the problem more rigorously, using the same idea as shown here. – Southey

The O(n^2) number of intersections can be reduced to an average case of O(n log n) by tiling 2-space and only worried about the tiles a new circle is in. Like a B-tree a tile may be split if the number of circles in the tile is too great. Tiling Algorithms in and of themselves can be optimized based problem specific limitations on the circle radii and the distances apart. In general, unless the number of circles grow into the 10-100s of thousands modern computers should be able to handle the algorithm without tiling. – Muskogean

Here is basic (O(n^2 log n) complexity) illustrated implementation: gist.github.com/versusvoid/a86d1e6ed0c64c6c80b0a908ac9f1865 – Mcintosh

@Mcintosh Could you explain how you deal with holes in your code? – Overscore

@J.Schmidt If you mean holes between circles like in Timothy Shields's picture they do not appear as part of any polygon and for every circle touching such hole area of "wedge" between two intersection will be computed – Mcintosh

@Mcintosh but at the polygon computing step, how do you for example avoid the "outer" polygon in Timothy Shields' picture instead of the correct polygons? From what I understand from your comments here and your code, you start at some vertex and visit adjacent intersections/centers in clockwise order? Would this not result in the outer polygon in the aforementioned picture? – Overscore

@Mcintosh I posted a seperate question with some more details if you're interested: #69900285 – Overscore

"You'll need to also account for any holes" is doing a lot of heavy lifting here. – Amari

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

Mulvey

This will work, but Monte-Carlo methods like this one, based simply on uniform sampling, generally don't have the best convergence rates. – Hymenopteran

Sorry, but even though I appreciate your effort and think your solution is "practically usable", I consider your approach to be very wrong. This is a problem than can and should be solved by means of math, not brute force. Wasting energy and cores on problems like this is wasteful and lavish. – Cheesecake

You're right, I'm ashamed of myself, but I've got a cluster with 12,000 cores, I can afford to be lavish. And I can't figure out how to make the elegant mathematical solution scale to that many processors. – Mulvey

There's nothing inherently wrong with a Monte-Carlo (or any randomized) approach, provided it gives the required degree of accuracy and does so in a reasonable amount of time. – Thomajan

@mafutrct, you're certainly right. However, it's easy to make little mistakes in the math. This solution provides a simple way to test correctness. – Squall

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

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

Southey

I think I can compute a set of the red/white dots fairly easily however my graph theory isn't too great: algorithmically, how do you get from a list of nodes + edges to a computed area? – Coy

The algorithm may be simplified by using a set of non overlapping triangles instead of polygons. The arcs (green areas) are areas contained in only one circle. Extend the size of a polygon as you add more circles. (in the end you can forget you are even talking about polygons). It makes boolean properties and the areas are easier to compute also. As a hollow red dot becomes a solid red dot, you simply add more triangles to your set, and you adjust the arc it gets "eaten away" by more and more intersecting circles. – Muskogean

How would one go about distinguishing the polygons and circle arcs from the set of blue and red/white dots? – Overscore

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

Mayfield

My guess is that this will converge more rapidly than the monte carlo inside/outside point algorithm too. – Normy

This does seem a lot easier to implement. Definitely the best brute force method suggested. Thanks! – Tisdale

brute force here is called squeeze theorem – Mayfield

That's the kind of algorithm you use in interval arithmetic. en.wikipedia.org/wiki/Interval_arithmetic – Zincography

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

_{(source: secretGeek.net)}

Anthraquinone

I think doing the kind of polygon division suggested by your image would probably be a very good approach. There are a lot of details to work out to code it up. How would it handle a chain of twenty circles, each of which overlaps only the last and next in the chain? Easy to figure out by hand, but what is your algorithm? – Chlorobenzene

Answer 6

If you want a discrete (as opposed to a continuous) answer, you could do something similar to a pixel painting algorithm.

Draw the circles on a grid, and then color each cell of the grid if it's mostly contained within a cirle (i.e., at least 50% of its area is inside one of the circles). Do this for the entire grid (where the grid spans all of the area covered by the circles), then count the number of colored cells in the grid.

Nasho

Answer 7

The pixel-painting approach (as suggested by @Loadmaster) is superior to the mathematical solution in a variety of ways:

1. Implementation is much simpler. The above problem can be solved in less than 100 lines of code, as this JSFiddle solution demonstrates (mostly because it’s conceptually much simpler, and has no edge cases or exceptions to deal with).
2. It adapts easily to more general problems. It works with any shape, regardless of morphology, as long as it’s renderable with 2D drawing libraries (i.e., “all of them!”) — circles, ellipses, splines, polygons, you name it. Heck, even bitmap images.
3. The complexity of the pixel-painting solution is ~O[n], as compared to ~O[n*n] for the mathematical solution. This means it will perform better as the number of shapes increases.
4. And speaking of performance, you’ll often get hardware acceleration for free, as most modern 2D libraries (like HTML5’s canvas, I believe) will offload rendering work to graphics accelerators.

The one downside to pixel-painting is the finite accuracy of the solution. But that is tunable by simply rendering to larger or smaller canvases as the situation demands. Note, too, that anti-aliasing in the 2D rendering code (often turned on by default) will yield better-than-pixel-level accuracy. So, for example, rendering a 100x100 figure into a canvas of the same dimensions should, I think, yield accuracy on the order of 1 / (100 x 100 x 255) = .000039% ... which is probably “good enough” for all but the most demanding problems.

<p>Area computation of arbitrary figures as done thru pixel-painting, in which a complex shape is drawn into an HTML5 canvas and the area determined by comparing the number of white pixels found in the resulting bitmap.  See javascript source for details.</p>

<canvas id="canvas" width="80" height="100"></canvas>

<p>Area = <span id="result"></span></p>

// Get HTML canvas element (and context) to draw into
var canvas = document.getElementById('canvas');
var ctx = canvas.getContext('2d');

// Lil' circle drawing utility
function circle(x,y,r) {
  ctx.beginPath();
  ctx.arc(x, y, r, 0, Math.PI*2);
  ctx.fill();
}

// Clear canvas (to black)
ctx.fillStyle = 'black';
ctx.fillRect(0, 0, canvas.width, canvas.height);

// Fill shape (in white)
ctx.fillStyle = 'white';
circle(40, 50, 40);
circle(40, 10, 10);
circle(25, 15, 12);
circle(35, 90, 10);

// Get bitmap data
var id = ctx.getImageData(0, 0, canvas.width, canvas.height);
var pixels = id.data; // Flat array of RGBA bytes

// Determine area by counting the white pixels
for (var i = 0, area = 0; i < pixels.length; i += 4) {
  area += pixels[i]; // Red channel (same as green and blue channels)
}

// Normalize by the max white value of 255
area /= 255;

// Output result
document.getElementById('result').innerHTML = area.toFixed(2);

Controller

This solution fails to account for doing mathematical computations with the areas of the circles. It misses the point of OPs question. Very often the rendering geometry is only half the battle when dealing with geometric shapes – Muskogean

Answer 8

Hmm, very interesting problem. My approach would probably be something along the lines of the following:

• Work out a way of working out what the areas of intersection between an arbitrary number of circles is, i.e. if I have 3 circles, I need to be able to work out what the intersection between those circles is. The "Monte-Carlo" method would be a good way of approximating this (http://local.wasp.uwa.edu.au/~pbourke/geometry/circlearea/).
• Eliminate any circles that are contained entirely in another larger circle (look at radius and the modulus of the distance between the centre of the two circles) I dont think is mandatory.
• Choose 2 circles (call them A and B) and work out the total area using this formula:

(this is true for any shape, be it circle or otherwise)

area(A∪B) = area(A) + area(B) - area(A∩B)

Where A ∪ B means A union B and A ∩ B means A intersect B (you can work this out from the first step.

• Now keep on adding circles and keep on working out the area added as a sum / subtraction of areas of circles and areas of intersections between circles. For example for 3 circles (call the extra circle C) we work out the area using this formula:

(This is the same as above where A has been replaced with A∪B)

area((A∪B)∪C) = area(A∪B) + area(C) - area((A∪B)∩C)

Where area(A∪B) we just worked out, and area((A∪B)∩C) can be found:

area((A∪B)nC) = area((A∩C)∪(B∩C)) = area(A∩C) + area(A∩B) - area((A∩C)∩(B∩C)) = area(A∩C) + area(A∩B) - area(A∩B∩C)

Where again you can find area(A∩B∩C) from above.

The tricky bit is the last step - the more circles get added the more complex it becomes. I believe there is an expansion for working out the area of an intersection with a finite union, or alternatively you may be able to recursively work it out.

Also with regard to using Monte-Carlo to approximate the area of itersection, I believe its possible to reduce the intersection of an arbitrary number of circles to the intersection of 4 of those circles, which can be calculated exactly (no idea how to do this however).

There is probably a better way of doing this btw - the complexity increases significantly (possibly exponentially, but I'm not sure) for each extra circle added.

Ceylon

Whats up with the formatting? Also sorry about the use of n and u for intersection and union, there is probably a better way... – Ceylon

added some unicode union (∪) and intersection (∩) signs. hopefully they work. – Polyphone

Answer 9

Here's an algorithm that should be easy to implement in practice, and could be adjusted to produce arbitrarily small error:

1. Approximate each circle by a regular polygon centered at the same point
2. Calculate the polygon which is the union of the approximated circles
3. Calculate the area of the merged polygon

Steps 2 and 3 can be carried out using standard, easy-to-find algorithms from computational geometry.

Obviously, the more sides you use for each approximating polygon, the closer to exact your answer would be. You could approximate using inscribed and circumscribed polygons to get bounds on the exact answer.

Chlorobenzene

Answer 10

I have been working on a problem of simulating overlapping star fields, attempting to estimate the true star counts from the actual disk areas in dense fields, where the larger bright stars can mask fainter ones. I too had hoped to be able to do this by rigorous formal analysis, but was unable to find an algorithm for the task. I solved it by generating the star fields on a blue background as green disks, whose diameter was determined by a probability algorithm. A simple routine can pair them to see if there's an overlap (turning the star pair yellow); then a pixel count of the colours generates the observed area to compare to the theoretical area. This then generates a probability curve for the true counts. Brute force maybe, but it seems to work OK.

_{(source: 2from.com)}

Aeschines

Answer 11

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.

Hirsh

Answer 12

This can be solved using Green's Theorem, with a complexity of n^2log(n). If you're not familiar with the Green's Theorem and want to know more, here is the video and notes from Khan Academy. But for the sake of our problem, I think my description will be enough.

If I put L and M such that

then the RHS is simply the area of the Region R and can be obtained by solving the closed integral or LHS and this is exactly what we're going to do.

So Integrating along the path in the anticlockwise gives us the Area of the region and integrating along the clockwise gives us negative of the Area. So

AreaOfUnion = (Integration along red arcs in anticlockwise direction + Integration along blue arcs in clockwise direction)

But the cool trick is if for each circle if we integrate the arcs which are not inside any other circle we get our required area i.e. we get integration in an anticlockwise direction along all red arcs and integration along all blue arcs along the clockwise direction. JOB DONE!!!

Even the cases when a circle doesn't intersect with any other is taken care of.

Here is the GitHub link to my C++ Code

Hanni

Answer 13

I found this link which may be useful. There does not seem to be a definitive answer though. Google answers. Another reference for three circles is Haruki's theorem. There is a paper there as well.

Lymphocyte

Answer 14

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.

Cater

Answer 15

I've got a way to get an approximate answer if you know that all your circles are going to be within a particular region, i.e. each point in circle is inside a box whose dimensions you know. This assumption would be valid, for example, if all the circles are in an image of known size. If you can make this assumption, divide the region which contains your image into 'pixels'. For each pixel, compute whether it is inside at least one of the circles. If it is, increment a running total by one. Once you are done, you know how many pixels are inside at least one circle, and you also know the area of each pixel, so you can calculate the total area of all the overlapping circles.

By increasing the 'resolution' of your region (the number of pixels), you can improve your approximation.

Additionally, if the size of the region containing your circles is bounded, and you keep the resolution (number of pixels) constant, the algorithm runs in O(n) time (n is the number of circles). This is because for each pixel, you have to check whether it is inside each one of your n circles, and the total number of pixels is bounded.

Merras