 # Overlapping circles - modelling living populations

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.

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. Elements 2-x of each row could point to another array
representing the other circles that this circle overlaps with - but this
seems fairly clumsy and was wondering if there is some better
mechanism . .

Thanks,

Phil.

···

--

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

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)
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.

···

--
Paul Lutus
http://www.arachnoid.com

Paul,

···

On Sat, 2006-09-09 at 17:50 +0900, Paul Lutus 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)
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.
--