Velocity Reviews > Re: Common area of circles

Re: Common area of circles

Chris Rebert
Guest
Posts: n/a

 02-04-2010
On Thu, Feb 4, 2010 at 2:39 AM, Shashwat Anand <(E-Mail Removed)> 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.

Cheers,
Chris
--
Back to toiling away on CSE 105 HW#3
http://blog.rebertia.com

Bearophile
Guest
Posts: n/a

 02-04-2010
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

John Nagle
Guest
Posts: n/a

 02-05-2010
Chris Rebert wrote:
> On Thu, Feb 4, 2010 at 2:39 AM, Shashwat Anand <(E-Mail Removed)> 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