Common area of circles

[Dave Angel]

Shashwat Anand wrote:
> I want to calculate areas.
> like for two circles (0, 0) and (0, 1) : the output is '1.228370'
>
> similarly my aim is to take 'n' co-ordinates, all of radius '1' and
> calculate the area common to all.
> The best I got was monte-carlo methods which is inefficient. Is there any
> other approach possible.
>
>   
>
You start with a list of circles, each having center (a,b), and radius 
(r).  As you stated the problem, r is always 1, but I'll keep the 
algorithm general.

This is untested, and probably contains typos, at least.

I would do it with successively smaller squares.  A square can be 
described using center coordinates (x,y) , and length (s) of a side.  
Each square can have three states:  not included, partially included, 
and fully included. 

You build a list of squares, starting with one, the bounding square for 
the first circle.

For each square in the list, you go through all the circles (each with 
center a,b, and radius r), and for each circle decide if the square is 
entirely within the circle, or partially.  If it's fully included in all 
of them, you add its area to the the accumulator, and drop it from your 
list.   if it's not included at all in one of them, you just drop it 
from the list.  (Note, be careful about modifying a list you're 
iterating through -- make a copy)

After a pass through the list,  the accumulator is a lower-bound for the 
area, and the accumulator plus the areas of all the squares is an upper 
bound.   If these are close enough together, you terminate.

Otherwise you take the remaining squares in the list, split each into 
four pieces, and end up with a list 4 times as long.  And repeat the 
loop, checking each square against each circle.


The only remaining question is how you decide for a given circle and a 
given square which of the three states it's in.  And it turns out you 
can be pretty approximate in this, and it'll still converge.  So you can 
take a distance between (a,b) and (x,y), and compare it to r-s/2  and to 
r+(s*0.707106781187).  If it's greater than r+s*0.707106781187, no 
intersection.  If it's less than r-s/2, then the square's entirely inside.

Note that I used  0.707106781187 above, but you'd actually use sqr(0.5) 
to whatever precision you needed.  And if it's convenient to round it, 
round it upwards;  again it won't affect the result.  I doubt if it 
would matter in Python code, but you could even do the whole thing in 
integers (avoiding the sqrt for distance calc), if you were careful 
about the bounding formulas.  That's premature optimization, however.

HTH,
DaveA