Here is my approach:
# input circles, remove duplicates, store them
# check whether all circle intersect:
if no: print '0.0'
if yes:
# calculate intersection points of two circles.
# check if that point lies in rest all circles
if yes: store it as polygon-coordinates (hull)
calculate area of curve from the given two points
# calculate final area : net area of curve + area of polygon
Here is my final code :
It's still Buggy (the logic I believe is correct, The implementation is
Buggy I guess
<Code>
import math
def catch_point(x, y):
# checks for points which lie inside all the circles
# stores all such point in hull
kount = True
for i in range(n):
if (x - circle[i][0])**2 + (y - circle[i][1])**2 - 1.0 > 0:
kount = False
if kount == True:
hull.append((x, y))
def curve_area(x0, y0, x1, y1, x2, y2):
k = math.sqrt((x1 - x2)**2 + (y1 - y2)**2)
area_c = math.pi * (math.degrees(math.acos(1.0 - k*k/2.0))/360) #TODO
Verify
area_t = 0.5 * ( x0*(y1 - y2) - x1*(y0 - y2) + x2*(y0 - y1) )
if area_t < 0: area_t = -area_t
area = area_c - area_t
#print area
return area
def polygon_area(p):
# calculate area of the polygon given the co-ordinates
return 0.5 * abs(sum(x0*y1 - x1*y0 for ((x0, y0), (x1, y1)) in
segments(p)))
def segments(p):
return zip(p, p[1:] + [p[0]])
def intersect_circles(l):
# check whether all circle intersects or not
for i in l:
for j in l:
if (i[0] - j[0])**2 + (i[1] - j[1])**2 >= 4.0:
sol = 0.0
return sol
break
return 1.0
def intersect_coordinates(l):
sol = 0.0 # initialisation of final result
for i in range(n):
for j in range(n):
# find all intersecting co-ordinates for each circle
xa, xb = circle[i][0], circle[j][0]
ya, yb = circle[i][1], circle[j][1]
d = math.sqrt((xa - xb)**2 + (ya - yb)**2)
if d == 0: continue
x1 = 0.5*(xa + xb) + 0.5*(yb - ya)*math.sqrt(4 - d*d) / d
y1 = 0.5*(yb + ya) - 0.5*(xb - xa)*math.sqrt(4 - d*d) / d
catch_point(x1, y1) # first intersection point
x2 = 0.5*(xa + xb) - 0.5*(yb - ya)*math.sqrt(4 - d*d) / d
y2 = 0.5*(yb + ya) + 0.5*(xb - xa)*math.sqrt(4 - d*d) / d
catch_point(x2, y2) # second intersection point
sol += curve_area(circle[i][0], circle[i][1], hull[-1][0],
hull[-1][1], hull[-2][0], hull[-2][1])
# add up the value of curves
return sol
t = int(raw_input()) # total no. of test cases
for test in range(t):
n = int(raw_input()) # total no. of circles
circle = [] # a blank list which will contain center of
circles
hull = [] # a blank list which will consist of points on
convex polygon
for i in range(n):
x,y = [float(i) for i in raw_input().split()]
circle.append((x,y)) # storing the value
circle = list(set(circle)) # removing duplicates
n = len(circle) # calculating no. of non-duplicate circle
sol = intersect_circles(circle) #intersect_circles() check whether
all circle intersect
if sol == 0.0: # if sol == 0.0 means all circle do not
intersect
print "0.000000" # solution = 0.000000 in this case
elif n == 1: # if only 1 circle present, the solution is PI
print "%.6f" %(math.pi)
else:
sol = intersect_coordinates(circle) # for rest cases we need
to calculate intersection co-ordinates of circle
print "%.6f" %(sol + polygon_area(hull)) # final solution
</Code>
sample output :
4
2
0 0
1 0
1.228370
3
0 0
0 0
0 0
3.141593
3
0 0
0 1
10 12
0.000000
3
0 0
1 0
0 1
0.192972
Either there is a redundency or there is some issue with this line : sol +=
curve_area(circle[i][0], circle[i][1], hull[-1][0], hull[-1][1],
hull[-2][0], hull[-2][1])
Still trying to fix it.
~l0nwlf
On Fri, Feb 5, 2010 at 11:48 AM, John Nagle <na...@animats.com> wrote:
> Chris Rebert wrote:
>
>> On Thu, Feb 4, 2010 at 2:39 AM, Shashwat Anand <anand.shash...@gmail.com>
>> wrote:
>>
>>> Given 'n' circles and the co-ordinates of their center, and the radius of
>>> all being equal i.e. 'one', How can I take out the intersection of their
>>> area.
>>>
>>
>> How is this at all specific to Python?
>>
>> This also sounds suspiciously like homework, which you should know
>> this list is unlikely to give direct answers to, though you might be
>> able to get a few pointers or some general suggestions.
>>
>
> Good point.
>
> This is actually a problem in what's called "constructive geometry".
> Usually, this is a 3D problem, for which the term "constructive solid
> geometry", or CSG, is used. That's where to look for algorithms.
>
> Yes, there are efficient algorithms and near-exact solutions.
> The basic idea is that you find all the points at which circles
> intersect, sort those by one coordinate, and advance across that
> coordinate, from one value of interest to the next. Between any
> two values of interest you're dealing with areas bounded by arcs
> and lines, so the areas can be calculated analytically. It's a
> lot like a rasterized polygon fill algorithm.
>
> (I used to do stuff like this back when I did physics engines
> with efficient 3D collision detection.)
>
> John Nagle
> --
> http://mail.python.org/mailman/listinfo/python-list
>
--
http://mail.python.org/mailman/listinfo/python-list
