4
$\begingroup$

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.

enter image description here

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

enter image description here

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.

enter image description here

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:

enter image description here

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

enter image description here

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.

$\endgroup$
3
  • $\begingroup$ You might find interesting G. Fejes Toth - Regular Figures-Macmillan (1964), Chapter VI, FIGURES IN THE EUCLIDEAN PLANE. If you know German (or Russian), then author have other interesting books also. $\endgroup$
    – zkutch
    Jul 27 at 7:55
  • $\begingroup$ I can answer the question of a) how to find the area of the union. But although you say that is your ultimate goal, the question here seems to be about b) finding intersections of circles. So is it a) or b) that you are interested in getting answered here? $\endgroup$
    – brainjam
    Jul 27 at 21:49
  • $\begingroup$ @brainjam : according to the method I set out to use, to find the area of the union I need the areas of all intersections between $2, 3, ..., n$ circles. And I know how to calculate it. What I can't do at the moment is test IF, given $m \ge 3$ circles, they have a non-empty intersection or not. As per the question I put at the end of my post: "how to find a condition (based on $d$'s and radii) that determines when there is a non-empty intersection between $m$ circles". So no, it's not your option b. As for a, if you'd like to suggest a different method, sure, might be interesting. Thanks $\endgroup$ Jul 28 at 7:01
1
$\begingroup$

If you are ok with $O(n^2)$ complexity, then I suggest the following:

  1. Find intersection points. (While you do it, remove circles that are completely inside some other circle)
  2. Find all internal intersection points (points that are inside some other circle).
  3. 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)
  4. Now red edges should form independent cycles.
  5. Calculate area: sum of the signed area of the cycles + area of circle segments with red bases.
  6. Add area for cases without polygons: single circles and pairs of circles.

enter image description here

$\endgroup$
1
  • $\begingroup$ Thank you for your suggestions. Unfortunately there are several points in your method that I would not know how to do, or that I do not understand. For the moment I will stick to my original plan (inclusion-exclusion as per linked post). $\endgroup$ Jul 28 at 6:58
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks! There is indeed an R package producing power diagram representations: rdocumentation.org/packages/transport/versions/0.12-2/topics/… . For me the main point is to find a method that does not require numerical integration (that's why I discarded the approach based on Green's theorem, described in the post I linked). I would like to implement something that potentially uses only 'exact' formulae. Why? Because numerical integration, while easiest to do, yields only approximate solutions to the original problem: puzzling.stackexchange.com/a/110825/37990 $\endgroup$ Jul 29 at 6:01
  • $\begingroup$ @user6376297 If you think this answer is helpful, consider upvoting. $\endgroup$
    – brainjam
    Jul 29 at 20:12
  • $\begingroup$ I did so. I upvoted both your answer and the other one. No idea why it went back to 0. I will try again. $\endgroup$ Jul 29 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.