Common area of circles
Gary Herron
gherron at islandtraining.com
Thu Feb 4 17:46:27 CET 2010
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)
>
> ------------------------------------------------------------------
>
More information about the Python-list
mailing list