From: Paul Lutus <nospam@...>
Date: 2006-09-09T17:50:13+09:00
Subject: Re: Overlapping circles - modelling living populations

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.

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