Common area of circles

[Xavier Ho]

It's an interesting problem. Never thought it was this difficult. I can't
account for all geometrical enumerations, but assuming all 4 circles
intersect, here's the solution for this particular senario. It's probably
not going to be useful to you since you're working on geometrical
approximations now, but it is precise to the exact value.

I don't have it worked out here, but it goes like this.

1. Find the area covered by all 4 circles, unioned. Method here:
http://stackoverflow.com/questions/1667310/combined-area-of-overlapping-circles

2: Follow this chart I made up:
http://xavierho.com/media/images/Misc/IntersectionOfFourCircles.png

And there you go. I'm sure there are way better, faster ways, and covers a
lot more senarios, but this is the best I can come up with, without counting
the rasterised pixels ratio =P.

I like Bearophile's solution. Have fun!

Cheers,
Xav

On Thu, Feb 4, 2010 at 10:27 PM, Shashwat Anand <anand.shashwat at gmail.com>wrote:

> 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
>>
>
>
> --
> 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/aef83d0e/attachment.html>