Re: Common area of circles

Discussion in 'Python' started by Chris Rebert, Feb 4, 2010.

  1. Chris Rebert

    Chris Rebert Guest

    On Thu, Feb 4, 2010 at 2:39 AM, Shashwat Anand <> 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
     
    Chris Rebert, Feb 4, 2010
    #1
    1. Advertising

  2. Chris Rebert

    Bearophile Guest

    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
     
    Bearophile, Feb 4, 2010
    #2
    1. Advertising

  3. Chris Rebert

    John Nagle Guest

    Chris Rebert wrote:
    > On Thu, Feb 4, 2010 at 2:39 AM, Shashwat Anand <> 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
     
    John Nagle, Feb 5, 2010
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jason Shohet
    Replies:
    3
    Views:
    372
    John Saunders
    Aug 28, 2003
  2. Gilgamesh
    Replies:
    0
    Views:
    460
    Gilgamesh
    Jan 6, 2006
  3. henryh
    Replies:
    1
    Views:
    924
    Roedy Green
    Sep 18, 2005
  4. Replies:
    0
    Views:
    1,098
  5. Douglas Douglas

    Identifying filled circles in a scanned image

    Douglas Douglas, Mar 31, 2006, in forum: Python
    Replies:
    3
    Views:
    297
    Paul McGuire
    Mar 31, 2006
Loading...

Share This Page