maximum number of circles = 10**6<br>runtime <= 5 sec<br>center of circles , -1000<=x_i,y_i<=1000 (float) [for int it was easier]<br>intersection is there and the area will be non-zero (it can always be checked if intersection is taking place and if no, then area = 0.000000)<br>

This was a programming contest problem, so code will be short<br>Maths, I'm eager to use. I attempted this problem because I saw scope of maths in it. (I learnt python while doing ProjectEuler because C/C++ was cumbersome for PE IMHO). I tried monte-carlo, but the time-limit exceeds if i go for required accuracy. The same happens with grid approach. <br>

<br><br><div class="gmail_quote">On Fri, Feb 5, 2010 at 12:25 AM, Mark Dickinson <span dir="ltr"><<a href="mailto:dickinsm@gmail.com">dickinsm@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">

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