CODEWITHSUNDEEP
matlab
Saptarshi
Saptarshi

Reputation: 13

Area of Union of n circles(MATLAB code)

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

Upvotes: 1

Views: 2496

Answers (1)

ely
ely

Reputation: 77424

If your problem was just for pairs of circles, you'll use the known result about Circle-Circle intersection areas. The formula for the pairwise area between any two circles, based on a standard parameterization of all circles involved, is given there. But as n gets large, the formulas for these areas are not commonly known. There might be a clever way to use recursion to compute the formulas for the intersection of two circles (n=2), the intersection of two asymmetric lens shapes (n=3), the intersection of two instances of whatever shape is the intersection of two asymmetric lens shapes (n=4), and so on. If you can derive formulas for those areas, you can always use inclusion-exclusion to figure out the intersection. The key insight is that the intersection of n instances of the previous shape is really the intersection of n-1 instances of intersections-of-previous-shape. But like the commenter above has said, that question really belongs at Math Overflow.

Practical Aside

For anyone reading who is interested in a practical way to solve this problem, Monte Carlo integration is an excellent choice. All you need to do is compute a large rectangle that bounds all of the circles, and then draw points uniformly in that rectangle. For each circle, check if the point is inside or outside. If it is ever inside, then increment a counter and break out of doing any more checks. At the end, the proportion of that counter to the total points drawn, multiplied by the area of the rectangle, will give the area.

If we assume that for each n-wise intersection area, we need to do n different O(1) steps (assuming we get an analytical formula that we can just plug the radii and center data straight into, which might be optimistic), then this analytical method is still O(n^2).

Monte Carlo is worse, O(Mn) where M is the number of points we draw, if we make the pessimistic assumption that we have to check against all n circles for every point. For moderate n, while M won't need to be intractably large, it certainly won't be close to n. However, we get the added benefit that our function automatically generalizes to the case of mixed radii (for which the general solution is much harder). From a practitioner's point of view, the analytical solution here is not very useful unless the circles barely overlap and the bounding rectangle contains a large amount of empty space.

Upvotes: 1

Related Questions