Re: [Repast-developer] Figurate Numbers, Neighborhoods and Distances.

[Mark R. D. <mdi...@la...>]

Thomas Howe wrote:
> Those both seem fine.  Keep in mind, though, that those only describe how to do range queries.  

> Distance queries are a bit different.  A distance query in a Moore neighborhood can be done fairly easily using one of the many graphics line drawing algorithms.  This will be more difficult (I think, but I'm not quite sure) to determine in the VonNeumannTopology.  So we should figure out how to caluculate those distances.
> 

But, this is what I'm really talking about. I think its important not to 
confuse continuous and descrete spatial concepts here. Both "range" and 
"distance" in a discrete space are bound to a concept of "spatial 
structure" which we currently define in the neighborhood rule. The rules 
define which positions are "equidistant" to a particular position.

So in all the below cases the x's are all the same distance from "c" 
(1), and the o's are all the same distance from "c" (2).

A Moore space

o o o o o
o x x x o
o x c x o
o x x x o
o o o o o

A vn space

     o
   o x o
o x c x o
   o x o
     o

A hex space

   o o o
  o x x o
o x c x o
  o x x o
   o o o

The euclidean or lineBresenham definition of distance is a mapping of a 
"discrete grid" onto a "continuous space" and represents a space with 
completely different "spatial structure" than the above spaces. The 
space this describes is the one defined below.

http://mathworld.wolfram.com/Disk.html
http://mathworld.wolfram.com/ClosedDisk.html

The Hex space is the only "above" discrete space that most closely 
matches the "disk" criteria, still the mapping of its distance function 
onto the discrete grid would not be euclidean in nature due to the 
staggering of the rows of the 2D storage grid. Its distance function 
represents the following grid patterns for even and odd rows.

o o o             o o o
o x x o         o x x o
o x c x o     o x c x o
o x x o         o x x o
o o o             o o o

I think the Bresenham and Euclidean concepts of space attempt to map 
descrete coordinates conceptually to continuous space, they are useful 
and I suspect very important in terms of mapping between the two, both 
for visualization and for cartographic style "projection". I also 
suspect that the different "above" descrete cases would "project" quite 
differently (if at all!) onto a continuous realm and such functions are 
of the same nature as your Bresenham function for Moore neighborhoods. 
But I'm still not convinced that the particular Bresenham function is an 
accurate "projection" onto the continuous realm for a "Moore structured" 
space. I have an idea of what the accurate projections would be in such 
cases, but don't have a set of equations that will define it yet.


> One particularly nice thing about those references, though is that it gives us a reference to use to name our topology lib (perhaps).  See:
> 
> http://mathworld.wolfram.com/Neighborhood.html
> 

What are you thinking of for a name?

Cheers,
-Mark