From: Philip Rhoades <phil@...>
Date: 2006-09-10T02:35:32+09:00
Subject: Re: Overlapping circles - modelling living populations

Paul,


On Sat, 2006-09-09 at 17:50 +0900, Paul Lutus wrote:
> Philip Rhoades wrote:
> 
> > People,
> > 
> > I have been thinking about how to use Ruby for modelling populations - I
> > want to use circles on a grid to represent the size of individual
> > populations and determine if there is dispersal between pairs of
> > populations by testing whether there is overlap with the two circles.
> 
> This is, strictly speaking, a math question. It is rather far removed from
> Ruby per se.
> 
> For two circles (position x,y and radius r) x1,y1,r1 and x2,y2,r2, if:
> 
> (x2-x1)^2+(y2-y1)^2 < (r2+r1)^2
> 
> Then the circles overlap. With a little more math, you can compute the area
> of the overlapping region.
> 
> > I need to keep track of:
> > 
> > - all the individual circles (populations) on a grid
> > 
> > - which other circles each circle overlaps with
> > 
> > And I need to:
> > 
> > - iterate through ALL the circles (for each generation of the
> > populations)
> > 
> > I thought of using a two dimensional array, each row representing a
> > circle.
> 
> At first glance, there's no need for a two-dimensional array. You have a set
> of circles and you want to find those that overlap. Simply create an
> algorithm that compares every circle with every other circle using the
> relation stated above. The fact that the problem exists in two-space
> doesn't mean the array needs two dimensions.
> 
> > Elements 2-x of each row could point to another array 
> > representing the other circles that this circle overlaps with -
> 
> This is indeed rather cumbersome. You could create a result array of circles
> containing the degree to which they overlap (you can establish the area of
> overlap), and you could update this list by repeating the algorithm after
> making changes to the positions and sizes of the original circles.
> 
> If you really need the specific degree of overlap of each circle with each
> of the other circles, then at that point you do need a two-dimensional
> array. If instead you only need the cumulative amount of overlap without
> having to identify the overlapping circles, then a single dimension will
> suffice.
> 
> Now to touch on Ruby. The first step would be to create a class containing
> the circle descriptions:
> 
> class PopCircle
>    attr_accessor :x,:y,:r
>    def initialize(x,y,r)
>       # read the class variables
>    end
> end
> 
> Then you would create a list of such class instances by reading a data file
> that describes the circles. Then, having created the list, you would
> compare all the circles to each other to find overlaps, and create some
> sort of result array showing the overlaps.
> 
> The difficult part will be deciding what the result means.


Thanks for that! - I know what I want to do with the population
simulation so this helps.

Regards,

Phil.
-- 
Philip Rhoades

Pricom Pty Limited  (ACN 003 252 275  ABN 91 003 252 275)
GPO Box 3411
Sydney NSW      2001
Australia
Mobile:  +61:(0)411-185-652
Fax:     +61:(0)2-8221-9599
E-mail:  phil@pricom.com.au