# Common area of circles

Gerard Flanagan grflanagan at gmail.com
Thu Feb 4 17:29:25 CET 2010

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

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

```