Common area of circles

[Gerard Flanagan]

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

------------------------------------------------------------------