Array neighbourhoods

[Daniel Pryde]

Hi again.

One thing I forgot to include in my post the other day. I was wondering if
anyone knew of any fast algorithms for returning the surrounding neighbours
of an array element, or even the neighbours of a group of array elements.

I'm using a function which affects neighbourhoods of a value with a
diminishing effect (i.e. a gaussian distribution), so I need to be able to
get the neighbourhood (of size 1) of the first array entry, as well as the
neighbourhood of the returned neighbourhoods! Hope that all makes sense.

Daniel

_________________________________________________________________
Express yourself with cool new emoticons http://www.msn.co.uk/specials/myemo

 

[Paul McGuire]

Hi again.

One thing I forgot to include in my post the other day. I was wondering if
anyone knew of any fast algorithms for returning the surrounding neighbours
of an array element, or even the neighbours of a group of array elements.

Try this (requires Python 2.3, since it uses sets). Can't say how fast it
is, but it handles all cases I can think of (edge effects, disjoint cells,
etc.). Maybe start with this to get going, then make it faster if it needs
to be.


# matrixNeighbors.py
from sets import Set

def neighborhoodOf(cells, rows, cols):
ret = Set()
if type(cells) == tuple:
row,col = cells
for i in (-1,0,1):
for j in (-1,0,1):
ret.add( (row+i, col+j) )
# remove original cell
ret.remove( cells )

elif type(cells) == list:
for cell in cells:
for neighbor in neighborhoodOf(cell,rows,cols):
ret.add(neighbor)
# remove original cells
ret -= Set( cells )

# remove all entries in ret with negative values,
# or values greater than number of cols/rows
for x,y in ret.copy():
if x < 0 or y < 0 or x >= COLS or y >= ROWS:
ret.remove( (x,y) )

return list(ret)

# define matrix boundaries
ROWS = 4
COLS = 6

print neighborhoodOf( (0,0), ROWS, COLS )
print neighborhoodOf( (COLS-1,ROWS-1), ROWS, COLS )
print neighborhoodOf( (COLS,ROWS), ROWS, COLS )
print neighborhoodOf( [(0,0),(0,1)], ROWS, COLS )
print neighborhoodOf( neighborhoodOf( (1,1), ROWS, COLS), ROWS, COLS )
print neighborhoodOf( neighborhoodOf( (COLS-1,ROWS-1), ROWS, COLS), ROWS,
COLS )
print neighborhoodOf( neighborhoodOf( (COLS,ROWS), ROWS, COLS), ROWS, COLS )