[Q] Neighbourhood on small toroidal grids

[Gary Polhill]

I'm wrestling a little with the definition of neighbourhood on a grid
with "wrap-around" -- with the effect that the grid can be seen as being
projected onto a ring doughnut. There is ambiguity in the definition of
toroidal grids (or how they are set up) that I would welcome your
thoughts on. Apologies if any of this seems trivial or obvious ....

There are two ways of looking at toroidal grids. In one way, the purpose
is to ensure that each cell has the same number of neighbours. In the
other, the grid is seen as repeating to infinity. The difference is that
when computing neighbourhood, the former way of looking at things might
have the attitude that the set of neighbours of any point, whilst having
the same number of elements, should never contain repeated cells.

Using Von Neumann neighbourhood for now (for the sake of simplicity), if
a cell can look a distance d in any direction to find their neighbours,
then in order to avoid repetition, the grid must be of size >2d by >2d.

For example, consider the 3 by 2 grid below (apologies if you're not
reading this in a fixed width font):

+-----+-----+-----+
|     |     |     |
|  A  |  B  |  C  |
|     |     |     |
+-----+-----+-----+
|     |     |     |
|  D  |  E  |  F  |
|     |     |     |
+-----+-----+-----+

Using a distance d = 1, the neighbours of A are B, C and D, with D
repeated since it is both above and below A if we are wrapping around.

If we use a toroidal grid because we want each cell to have the
same number of neighbours, then we could define things such that
a neighbour of a cell cannot be repeated -- so each cell would have
3 neighbours rather than 4 in the grid above.

If we just see the grid as repeating itself to infinity i.e.

    :::::::::
... ABCABCABC ...
... DEFDEFDEF ...
... ABCABCABC ...
... DEFDEFDEF ...
... ABCABCABC ...
... DEFDEFDEF ...
    :::::::::

then each cell will always have one repeated neighbour.

Further, we might define neighbourhood such that you cannot be a
neighbour of yourself. In the grid above, if d = 2, then the neighbours
of A are A, D, B, C, B, C, D, A just treating the grid as if it was
repeated to infinity, but since A cannot be a neighbour of themselves,
this would be B, C, D (repeated twice). Furthermore, not allowing cells
to be self-neighbours in toroidal grids would have the consequence that
in a 1 by 1 grid, the cell would have no neighbours.

I'm rather painfully aware that the above is not especially clear ...

Are there any conventions on calculating neighbourhood on a toroidal
grid, as regards seeing yourself as a neighbour, and possibly having
cells repeated as neighbours?

What sort of biases do you get as a result of not worrying about
repeated cells/self in your own neighbourhood?

Gary


-- 

Macaulay Land Use Research Institute, Craigiebuckler, Aberdeen. AB15 8QH
Tel: +44 (0) 1224 318611               Email: address@hidden


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