Common area of circles

[Shashwat Anand]

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 <nagle at animats.com> wrote:

> Chris Rebert wrote:
>
>> On Thu, Feb 4, 2010 at 2:39 AM, Shashwat Anand <anand.shashwat at 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20100205/871aca2e/attachment-0001.html>