I am trying to calculate the area of union of n circles in a plane when it is known that all circles are of equal radii and their centers are also known(of all n circles). I was trying to follow the set theory approach(inclusion-exclusion principle), where we know the formula for union of n sets. I was just using an operator Ar() which gives the area,i.e. Ar(A) gives me the area of A. I first tried to find out which circle is intersecting with which other circle(s) with the help of D<2R(D=dist between the centers of the two circles), then I was trying to calculate the area of intersection between them pairwise and hence find the area of union. But I am getting stuck for n>4. Can anyone provide a soln to this(soln by the set theory approach is necessary). Thanks in advance
2 Answers
For the inclusion-exclusion approach, you need to be able to calculate for each set $S$ of circles the area $A_S$ of their intersection. Consider a set of circles, all of radius $1$, whose intersection is nonempty. The intersection will be a convex region bounded by $k$ arcs (where $k$ might be less than the number of circles); ignoring trivial cases, I'll suppose $k\ge 2$. Let $P_i = (x_i, y_i), i=0 \ldots k$, be the endpoints of the arcs, taken counterclockwise, with (for convenience) $P_0 = P_k$. Note that the area of the "cap" cut off from a circle of radius $1$ by a chord of length $L$ is $f(L) = \arcsin(L/2) - L \sqrt{4 - L^2}/4$, while the area of the polygon with vertices $P_i$ is $\sum_{i=1}^k (x_{i-1} - x_i)(y_{i-1}+y_i)/2$. So the total area of the intersection is $$A_S = \sum_{i=1}^k \left( f\left(\sqrt{(x_i - x_{i-1})^2 + (y_i - y_{i-1})^2}\right) + \frac{(x_{i-1} - x_i)(y_{i-1}+y_i)}2 \right)$$
-
$\begingroup$ Thank you for your answer. However I couldn't get the last part where you have mentioned the formula for $A_{s}$. Can you pl elaborate on that bit? Thanks in advance.wouldn't the area of intersection be the $Area of Polygon$ $+$ $\sum_{i=1}^k(Area of cap)_{i}$ $\endgroup$ Commented Jan 6, 2012 at 9:40
-
$\begingroup$ Yes, that's what I wrote: the area of the polygon is the sum of $(x_{i-1}-x_i)(y_{i-1}+y_i)/2$, and the aum of the areas of the caps is the sum of $f(\sqrt{(x_i-x_{i-1})^2+(y_i-y_{i-1})^2})$ $\endgroup$ Commented Jan 6, 2012 at 17:28
-
$\begingroup$ Oh,ok...thanks a lot for your help $\endgroup$ Commented Jan 7, 2012 at 6:32
-
$\begingroup$ Mr. Israel, can you please tell me how you arrived at this formula? I cannot derive this formula from the given data. Thanks in advance $\endgroup$ Commented Jan 9, 2012 at 4:13
-
$\begingroup$ @RobertIsrael Thank you for the answer! Can you refer to a scientific source of this approach? $\endgroup$– PeterDCommented Apr 13, 2022 at 18:39
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. The general equation of Green's Theorem is $$\oint_{C} (Ldx + Mdy) = \iint_{R}(\frac{\partial M}{\partial x} - \frac{\partial L}{\partial y})dxdy$$
If I put L and M such that $$\frac{\partial M}{\partial x} - \frac{\partial L}{\partial y} = 1$$
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
