Re: lattice representation

[Miles Parker]

Hi John,

This is a question that I've dealt with a little for our own agent tools (but 
not in the context of tables) while trying to optimize and abstact neighbor 
type searches. I'm definetly got to check out Paul's sugested book and I'm 
sorry I can't offer you any references; the following ideas are just out of my 
own tinkering. Sorry if some of it is trivial.

Your problem involves more than lattice structures, because the definition of 
'neighbor' can change even within a given structure e.g. a grid cell has four 
von Neumann neighbors, but eight Moore neighbors.Or, more practically, suppose 
you want all neighbors within n radius, or the first neighbor that meets some 
criteria. Then you need some way to rank neighborage :-) by distance, and the 
number of neighbors in each rank can be different, of course. And you can't 
just increment some relative coordinate counter, because, for instance, 
relative coordinates {+-5, 0}, {+-3, +-4} have the same distance.

Basically, you can provide some kind of list of relative translations that you 
can apply to your origin coordinate to get the indexes you want. These lists 
may be different sizes, of course. In my implementation, for performance, I've 
got hard coded lists of lists out to rank 134 (which is only radius 22.6!) that 
I generated in Mathematica; new lists would have to be calculated at run-time 
beyond this distance.(TBD!) 

Of course, you would need to use these in the context of some indexing scheme. 
If the structure was fixed, you could just generate (Y * WIDTH + X) sequential 
ids and provide some direct offset. So von Neumann neighbors would be,

{L(-WIDTH), L(- 1) , L(+ 1), L(+WIDTH)}, 

and Moore,

{L(- WIDTH-1),L(WIDTH), L(-WIDTH+1),L(-1) , L(+1), L(WIDTH - 1), L(WIDTH), 
L(WIDTH + 1)}

Of course, in this simple example you can just hard code it and skip the lists. 
(You would obviously have to handle bounds, or mod for periodic structures.) 

For my purposes, it makes a lot more sense to just use x, y offsets of course, 
because I have random access to the lattice structure,

{{{  0,  0}},
 {{  1,  0}, {  0,  1}, {  0, -1}, { -1,  0}},
 {{  1,  1}, {  1, -1}, { -1,  1}, { -1, -1}},
 {{  2,  0}, {  0,  2}, {  0, -2}, { -2,  0}},
 {{  2,  1}, {  2, -1}, {  1,  2}, {  1, -2}, { -1,  2}, { -1, -2}, { -2,  1}, 
{ -2, -1}},
 {{  2,  2}, {  2, -2}, { -2,  2}, { -2, -2}},
 {{  3,  0}, {  0,  3}, {  0, -3}, { -3,  0}},
 ...
}

I suppose for your purposes, it might make sense to do some encoding for X and 
Y such that they are not dependent on the width of your lattice, trivially, 
"002001" for {2,1}, or using any arbitrary offset for Y. This would allow you 
to do your querys on just one column.

So this isn't a hugely sophisticated solution, but it works. A nice benefit is 
that it allows 'pick nearest random neighbor that...' to be generalized. I 
haven't tried to apply this to more complex structures, but it should work for 
hex.

Hope this helps,

Miles



Miles T. Parker
Research Programmer
The Brookings Institution  1775 Mass. Ave. NW  Washington, DC  20036
mailto:address@hidden  voice 202.797.6136  fax 202.797.6319

>>> John Carnahan <address@hidden> 03/01 3:34 PM >>>

Does anyone know any good references on lattice/grid representation? My
question is how could I best represent a 2-dimensional lattice with
neighborhood information. I am most interested in storage and retrieval of
neighbors from a linear table (eg SQL). Storing coordinates and then doing
directional lookups (N,S,E,W ...) cannot be the best way. 

For example, let's say that I have a given list of values/cells indexed by
an ordered set of integers. Then for a 1-dimensional lattice all neighbors
of cell x are given by indices x+1 and x-1. For a 2-dimensional lattice
things aren't so simple because any cell x has several neighbors (eg
hex=6, rect=8). There should be some way to index a set of values for a
2-dimensional lattice such that the position (or index) of the neighbors
of a given cell are described by its index. 

There must be tons of material written on this especially in the CA and
GIS literature. I thought this might be the best forum in which to ask
although it is not specifically related SWARM. 

Thanks,

JohnC
UCLA



                  ==================================
   Swarm-Modelling is for discussion of Simulation and Modelling techniques
   esp. using Swarm.  For list administration needs (esp. [un]subscribing),
   please send a message to <address@hidden> with "help" in the
   body of the message.
                  ==================================


                  ==================================
   Swarm-Modelling is for discussion of Simulation and Modelling techniques
   esp. using Swarm.  For list administration needs (esp. [un]subscribing),
   please send a message to <address@hidden> with "help" in the
   body of the message.
                  ==================================