Common area of circles

[Shashwat Anand]

I needed 6 decimal places of accuracy, so first way of solution will not
work for my case. However, your second strategy seems promising. Working on
it. Thanks :D
~l0nwlf

On Thu, Feb 4, 2010 at 5:49 PM, Bearophile <bearophileHUGS at lycos.com> wrote:

> Shashwat Anand:
> > > 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.
>
> I can see two possible solutions, both approximate. In both solutions
> you first look if there are a pair of circles that don't intersect, in
> this case the intersect area is zero. You also remove all circles
> fully contained in another circle.
>
> The first strategy is easy to do, but it probably leads to a lower
> precision. Then you can sample randomly many times the rectangular
> area that surely contains all circles. You count how many of those
> random points are inside all circles. This gives you an approximate
> area of their intersection. Increasing the points numbers slowly
> increases the result precision.
>
> The second strategy is more complex. You convert your circles into
> polygons with a fixed number of vertices (like 50 or 100 or 1000 or
> more. This number is constant even if the circles don't have all the
> same radius). So you can turn this circle into a simple mesh of
> triangles (all vertices are on the circumference). Then you "subtract"
> the second polygonalized circle, this can create a hole and split
> triangles in pieces, and so on with successive circles. At the end you
> can compute the total area of the triangles left. This is doable, but
> you need time to do implement this. The advantage is that the
> numerical precision of the result is probably higher. If you implement
> this second solution you can implement the first one too, and use it
> as a test to avoid bugs. Visualizing the triangles with Pygame or
> MatPlotLib can be useful to look for bugs.
>
> Bye,
> bearophile
> --
> http://mail.python.org/mailman/listinfo/python-list
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20100204/cc8960b5/attachment-0001.html>