Common area of circles

[Gary Herron]

Gerard Flanagan wrote:
>
>>     On 2/4/2010 7:05 AM, 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.
>>
>>
>
> A brute force approach - create a grid of small squares and calculate 
> which squares are in all circles. I don't know whether it is any 
> better than monte-carlo: 

That's just what the monte-carlo method is -- except the full family of 
monte-carlo methods can be quite sophisticated, including being more 
general (pseudo or quasi random points instead of a regular grid) and 
can provide a theoretical basis for calculating the rate of convergence, 
and so on.

Gary Herron



> for two circles, delta=0.001 takes about a minute and delta=0.0001 is 
> still running after 30 minutes :-)
>
> 1.22
> 1.2281
> 1.22834799999
>
>
> ------------------------------------------------------------------
> import math
>
> class Circle:
>
>     def __init__(self, x, y, r=1):
>         self.x = float(x)
>         self.y = float(y)
>         self.r = float(r)
>
>     def contains(self, a, b):
>         return math.sqrt((self.x-a)**2 + (self.y-b)**2) <= self.r
>
> class Grid:
>
>     def __init__(self, circles):
>         self.X1 = min(c.x-c.r for c in circles)
>         self.Y1 = max(c.y+c.r for c in circles)
>         self.X2 = max(c.x+c.r for c in circles)
>         self.Y2 = min(c.y-c.r for c in circles)
>         self.circles = circles
>
>     def iter_boxes(self, delta):
>         X2 = self.X2
>         Y2 = self.Y2
>         a = self.X1
>         while a < X2:
>             a += delta
>             b = self.Y1
>             while b > Y2:
>                 b -= delta
>                 #print a, b
>                 yield a, b
>
>     def intersection(self, delta=0.1):
>         S = 0
>         s = delta**2 #box area
>         circles = self.circles
>         for a, b in self.iter_boxes(delta):
>             if all(c.contains(a, b) for c in circles):
>                 S += s
>         return S
>
>
> c = Circle(0, 1)
>
> assert c.contains(0, 1)
> assert c.contains(0, 1.5)
> assert c.contains(math.sqrt(2)/2, math.sqrt(2)/2)
> assert c.contains(0, 2)
> assert not c.contains(0, 2.01)
> assert not c.contains(0, 2.1)
> assert not c.contains(0, 3)
>
> circles = [
>         Circle(0, 0),
>         Circle(0, 1),
> ]
>
> g = Grid(circles)
>
> print '-'*30
> print g.intersection()
> print g.intersection(0.01)
> print g.intersection(0.001)
> print g.intersection(0.0001)
>
> ------------------------------------------------------------------
>