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

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

Answer 2

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.
http://www.2from.com/images/simulated_star_field.gif

Answer 3

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.

Answer 4

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.

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)

alt text http://secretGeek.net/image/triangles_1667310.png

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.