Common area of circles

[Mark Dickinson]

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