Сопоставление смежных ячеек

Question

У меня есть матрица 570 x 800 с значениями id. Что я хотел бы сделать, если найти соседних соседей для каждого элемента. Максимальное количество соседей будет равно 8, если клетка не находится вдоль границы. В этом случае было бы три соседа. Я хочу добавить соседей в список. Я видел проводку для поиска соседей, когда каждая ячейка имеет координаты x и y, что было очень полезно, но как изменить код без координат. Иды входят как строка, которая прекрасна, потому что я использую ее как ключ в словаре. Любая помощь будет оценена по достоинству.

Answer 1

код без каких-либо координат? Вы имеете в виду, как это:

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 

Answer 2

Предполагая, что то, что вы пытаетесь сделать, это построить сетку с восемью связями на матрице и что позиция элемента в матрице определяет координату x и y, вы можете использовать что-то вроде это:

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 

Answer 3

Позвольте мне дать альтернативный ответ с numpy, который представляет собой библиотеку вы можете рассмотреть, если вы делаете что-нибудь немного более сверхмощный с вашими данными. Преимуществом этого метода является расширяемость к числу ближайших соседей с параметром k. Установка:

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] 

Теперь вы можете получить доступ к ближайшим соседям A[Xidx+dx, Yidx+dy] где dx и dy являются зачетами для x и y координат.

Пример

Давайте возьмем случайную матрицу:

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

который для меня выглядит следующим образом:

[[ 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]] 

Теперь мы можем просмотреть ближайших соседей

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] 

Давать:

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

Как уже упоминалось, за счет изменения k вы можете легко получить следующие ближайших соседей, а на следующий ближайшие соседи, и т.д ... Кроме того, способность индексировать массив более высокого порядка (скажем, тензор ранга 3), теперь можно добавить дополнительную переменную Zidx аналогичным образом.

Предостережения

Это хорошо работает, когда вы идете в крайний правый и нижней части вашей матрицы - вы получите меньшие списки (как указано вы хотите). Однако, индексирование (и Python) также, обертывается вокруг, поэтому индекс -1 даст вам последний элемент. Таким образом, запрос на офсет в 0,0 по-прежнему даст вам восемь записей, обернувшись вокруг. Другие ответы здесь показывают хороший способ проверить это.

Если вы хотите захватить что-то на левом краю (и вы действительно не хотите использовать оператор if), вы можете изменить индекс как таковой (убедитесь, что вы удалите центральный элемент, как указано выше):

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