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 <dicki...@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 >
-- http://mail.python.org/mailman/listinfo/python-list