[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: lattice representation
From: |
Miles Parker |
Subject: |
Re: lattice representation |
Date: |
Mon, 01 Mar 1999 20:55:59 -0500 |
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.
==================================