Intersection of n circles I am trying to devise a general method (ultimately an R script) to calculate the area of the union of $n$ circles, similarly to this post, except that I am not constraining the radius to be equal for all circles.

Same as the above post, I am opting for the inclusion-exclusion approach with the formula in this answer, which means I need to calculate the areas of the intersections of all possible sets of 2, 3, ..., n circles that do overlap.
So the first problem I had to tackle was: when do $m \le n$ circles have a non-empty intersection?
I started by looking at the case with $m = 2$.
Apparently, if $d$ is the distance between the centres of the two circles, and $R_1, R_2$ their radii, their perimeters have two distinct intersection points (i.e. there is a non-empty overlapping region that does not degenerate to a whole circle) only if $|R_1 - R_2| < d < R_1+R_2$ (this would be case 3 below):

Then I set out to calculate the area of the two circular segments that form the intersection.
They are already available in some websites, but I wanted to delve into this myself, to understand the machinery of it.
And indeed, in doing that I found a complication that does not seem to be addressed by most websites.

The most common case is 1 above, where the sum of the areas of the circular segments (which by convention is always calculated as the 'smaller' cut-off of the circle) is indeed equal to the intersection of the two circles.
However, as $d$ decreases, at some point the chord becomes equal to the diameter of the smaller circle (case 2). The general formula still holds, and it simply gives half the area of the whole small circle.
For $d$ below that, however, the formula based on the chord length fails: one would need to take the 'larger' part of the smaller circle that is cut off by the chord (so basically its total area minus the 'conventional' circular segment). This is case 3.
I found that this happens when $d < \sqrt {|R_1^2-R_2^2|}$.
My own formulae, based on $d$ rather than on the chord length, still work, because the area of the triangle that must be subtracted from the area of the circular sector to obtain the one of the circular segment becomes negative, so it is in fact summed. Still I thought it was important to find this out.
To tackle cases with $m > 2$, my main questions/doubts at the moment are:

*

*how to find a condition (based on $d$'s and radii) that determines when there is a non-empty intersection between $m$ circles

*whether the above issue with a smaller circle being 'more inside' another circle than 'outside' would affect those cases, too, or not

So I am trying to find what condition differentiates case 1 from 2 below:

And of course the same for $m = 4, 5, ..., n$.
Intuitively I am guessing that the circles' centres will need to be 'closer together' the larger $m$ gets, for a non-empty intersection between all $m$ circles to exist.
But at the moment I would not know how to approach it.
Any ideas/advice?
Thanks!

EDIT clarification

I can calculate the positions of points $A, B, C$ in the above picture.
What I don't know is how to test if these points enclose an area that belongs to the intersection of the 3 circles (case 1) or not (case 2).
It might be obvious or very easy, but I just have not figured it out, yet, so I would appreciate any advice on the matter.
E.g. I can see that in case 1 each point $P$ in $A, B, C$, is 'inside' the 3rd circle (i.e. $P$ is at a distance $d < R$ from the centre of the circle that did not generate $P$). But I don't know if this is a generally valid test, and I don't immediately see how it would extend to $m > 3$ and to cases where the radii are all different.
 A: If you are ok with $O(n^2)$ complexity, then I suggest the following:

*

*Find intersection points. (While you do it, remove circles that are completely inside some other circle)

*Find all internal intersection points (points that are inside some other circle).

*For each circle, traverse the polygon made of the intersection points anti-clockwise. Mark directed edge red unless it's adjacent to an internal point or belongs to another circle. (If a circle has only internal intersection points, remove it completely)

*Now red edges should form independent cycles.

*Calculate area: sum of the signed area of the cycles + area of circle segments with red bases.

*Add area for cases without polygons: single circles and pairs of circles.


A: This answer is about a general strategy for finding the area of a union of disks, rather than addressing your specific question.
In my experience, the most robust approach to the problem is based on power diagrams.  From the present version of the article:

The power diagram may be used as part of an efficient algorithm for
computing the volume of a union of spheres. Intersecting each sphere
with its power diagram cell gives its contribution to the total union,
from which the volume may be computed in time proportional to the
complexity of the power diagram.

Since your objective is to implement a solution in R a good place to start would be to find an existing power diagram implementation.
Power diagrams are generalizations of Voronoi diagrams, and both can be computed by finding 3D convex hulls.  You can find much more detail and theory by searching for "power diagram", "regular triangulation" and "union of balls".
Here's a power diagram demo I wrote once upon a time.  You can drag the circles around (and change their size using the shift key) to see how the power diagram changes as the circles change.  It may be useful to get a sense of the problem, whether you pursue power diagrams or some other solution.  The power diagram algorithm there  was adapted from existing Delaunay triangulation code.
Other approaches to this problem likely involve a lot of bookkeeping and special cases.  The nice thing about the power diagram approach is that there's no extra bookkeeping burden.  Just find the area of each circle within its convex cell, add them up, and you're done.  Note that circles can have no associated cells, or be completely outside their cell, so these circles would have no contribution to the total area.
