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.
How much accuracy do you need? How fast does the algorithm need to be? How many circles are typically involved? Is the intersection necessarily non-empty for the configurations of circles that you use? How much code are you prepared to write? How much mathematics do you want to use? Besides the Monte-Carlo and grid-based approaches already mentioned, I see a couple of other possibilities: (1) It should be entirely possible to do this analytically. The hard part would be identifying the intersection points that form the vertices of the intersection (and especially, doing this robustly in the face of numerical errors and triple intersections or near-triple intersections). Once you've got the vertices, it should be straightforward to compute the area: compute the area of the polygon given by the convex hull of the vertices, then add on the extra areas for the segments bounded by the (straight) sides of the polygon and the corresponding outer arcs. (2) For a numerical approach that might be slightly better than the 2d brute-force approaches described by others: make use of the fact that the intersection is convex. Pick a point P in the intersection (if it exists: finding such a point is an issue in itself). For each angle t, 0 <= t <= 2*pi, define f(t) to be the distance from P to the boundary of the region, in the direction of the angle t. We always have 0 <= f(t) <= 1, so f(t) can be quickly and accurately computed with a bisection search. Now find the definite integral of 0.5 * (f(t))**2, as t goes from 0 to 2*pi, using your favourite quadrature method (but avoid methods that would be very sensitive to continuity of derivatives: f(t) will be continuous, but f'(t) will not). Simpson's rule is probably good enough. Good luck! -- Mark -- http://mail.python.org/mailman/listinfo/python-list
