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)
------------------------------------------------------------------
More information about the Python-list
mailing list