Common area of circles
anand.shashwat at gmail.com
Thu Feb 4 20:19:59 CET 2010
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!
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Python-list