Common area of circles

[Shashwat Anand]

maximum number of circles = 10**6
runtime <= 5 sec
center of circles , -1000<=xi,yi<=1000 (float) [for int it was easier]
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)
This was a programming contest problem, so code will be short
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.


On Fri, Feb 5, 2010 at 12:25 AM, Mark Dickinson <dickinsm at gmail.com> 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.
>
> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20100205/d3b66d38/attachment-0001.html>