CODEWITHSUNDEEP
python
Linda
Linda

Reputation: 307

Listing adjacent cells

I have a 570 x 800 matrix with id values. What I would like to do if find the adjacent neighbors for each item. The max number of neighbors would be 8 unless the cell is along a boundary. In that case, there would be three neighbors. I want to append the neighbors to a list. I saw the posting for finding neighbors when each cell has x and y coordinates which was very helpful, but how would modify the code with no coordinates. The ids come in as a string which is fine because I use it as a key in a dictionary. Any help would be appreciated.

Upvotes: 3

Views: 2833

Answers (3)

Andrew Walker
Andrew Walker

Reputation: 42480

Assuming that what you're trying to do is construct an eight-connected grid on the matrix, and that the position of item in the the matrix defines an x- and y- co-ordinate, you can use something like this:

def eight_connected_neighbours( xmax, ymax, x, y ):
    """The x- and y- components for a single cell in an eight connected grid

    Parameters
    ----------
    xmax : int
        The width of the grid

    ymax: int
        The height of the grid

    x : int
        The x- position of cell to find neighbours of

    y : int 
        The y- position of cell to find neighbours of

    Returns
    -------
    results : list of tuple
        A list of (x, y) indices for the neighbours    
    """
    results = []
    for dx in [-1,0,1]:
        for dy in [-1,0,1]:
            newx = x+dx
            newy = y+dy
            if (dx == 0 and dy == 0):
                continue
            if (newx>=0 and newx<xmax and newy >=0 and newy<ymax):
                results.append( (newx, newy) )
    return results

Upvotes: 5

Hooked
Hooked

Reputation: 88168

Let me give an alternate answer with numpy, which is a library you might want to consider if you're doing anything a bit more heavy duty with your data. The advantage with this method is the extensibility to the number of nearest neighbors with the parameter k. The setup:

from numpy import *

k = 1

# Create the nearest neighbors
Xidx, Yidx = mgrid[-k:k+1,-k:k+1]

# Remove the center (0,0) index
center = (Xidx==0) & (Yidx==0)
Xidx = Xidx[~center]
Yidx = Yidx[~center]

Now you can access the nearest neighbors with A[Xidx+dx, Yidx+dy] where dx and dy are the offsets for the x and y coordinates.

Example

Let's take a random matrix:

A = random.random((5,5))
print A

which for me looks like:

[[ 0.90779297  0.91195651  0.32751438  0.44830373  0.2528675 ]
 [ 0.02542108  0.52542962  0.28203009  0.35606998  0.88076027]
 [ 0.08955781  0.98903843  0.86881875  0.21246095  0.92005691]
 [ 0.57253561  0.08830487  0.06418296  0.59632344  0.53604546]
 [ 0.7646322   0.50869651  0.00229266  0.26363367  0.64899637]]

Now we can view the nearest neighbors with

dx, dy = 2,1

print "Cell value A[%i,%i] = %f " % (dx, dy, A[dx,dy])
print "k=%i nearest neighbors: "%k, A[Xidx+dx, Yidx+dy]

Giving:

Cell value A[2,1] = 0.989038 
k=1 nearest neighbors:  [ 0.02542108  0.52542962  0.28203009  0.08955781  0.86881875 0.57253561  0.08830487  0.06418296]

Bonus

As mentioned, by changing k you can easily get the next nearest neighbors, and next-next neighbors, etc... In addition, the ability to index a higher order array (say a tensor of rank 3) is now possible by adding an additional variable Zidx in a similar way.

Caveats

This works nicely when you go to the rightmost and bottom of your matrix - you'll get smaller lists (as you specified you wanted). However, numpy indexing (and Python) as well, wraps around, so an index of -1 will give you the last element. Thus asking for the offset at 0,0 will still give you eight entries by wrapping around. The other answers here show a good way to check for this.

If you want to grab something on the left side edge (and you really don't want to use an if statement), you might change the index as such (making sure to remove the center element as above):

# Create the nearest neighbors (ON THE LEFT EDGE)
Xidx_left, Yidx_left = mgrid[0:k+1,-k:k+1]

Upvotes: 2

pillmuncher
pillmuncher

Reputation: 10162

code with no coordinates? Do you mean like this:

XMAX = 800
YMAX = 570

NEIGHBOURS = [(-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1)]

matrix = range(XMAX * YMAX)

def all_neighbours(m):
    for i in xrange(len(m)):
        ns = []
        y, x = divmod(i, XMAX)
        for u, v in NEIGHBOURS:
            ux = u + x
            vy = v + y
            if 0 <= ux < XMAX and 0 <= vy < YMAX:
                ns.append(ux + vy * YMAX)
        yield i, ns

if __name__ == '__main__':

    for field, neighbours in all_neighbours(matrix):
        print field, neighbours

Upvotes: 0

Related Questions