Common area of circles

[John Nagle]

Chris Rebert wrote:
> On Thu, Feb 4, 2010 at 2:39 AM, Shashwat Anand <anand.shashwat at gmail.com> wrote:
>> Given 'n' circles and the co-ordinates of their center, and the radius of
>> all being equal i.e. 'one', How can I take out the intersection of their
>> area.
> 
> How is this at all specific to Python?
> 
> This also sounds suspiciously like homework, which you should know
> this list is unlikely to give direct answers to, though you might be
> able to get a few pointers or some general suggestions.

     Good point.

     This is actually a problem in what's called "constructive geometry".
Usually, this is a 3D problem, for which the term "constructive solid
geometry", or CSG, is used.  That's where to look for algorithms.

     Yes, there are efficient algorithms and near-exact solutions.
The basic idea is that you find all the points at which circles
intersect, sort those by one coordinate, and advance across that
coordinate, from one value of interest to the next.  Between any
two values of interest you're dealing with areas bounded by arcs
and lines, so the areas can be calculated analytically.  It's a
lot like a rasterized polygon fill algorithm.

     (I used to do stuff like this back when I did physics engines
with efficient 3D collision detection.)

				John Nagle