如何在python中找到2D列表的邻居？

Question

我有一个只有1和0的2D列表:

Boundaries = [
[0,0,0,0,0],
[0,1,1,1,0],
[0,1,1,1,1],
[0,1,1,1,0],
[0,0,1,0,0]]

我需要测试这个列表以检查是否有任何1被8个其他1包围(例如此列表中的中间1).如果有1被1作为邻居包围,那么它应该变为0,这样在运行程序之后,上面的列表将返回如下所示:

[
[0,0,0,0,0],
[0,1,1,1,0],
[0,1,0,1,1],
[0,1,1,1,0],
[0,0,1,0,0]]

我试图只使用一个参数(1和0的矩阵).出于某种原因,这是一个非常困难的事情.到目前为止,我的代码看起来像这样:

def tempBoundaries(matrixC):
    for i in matrixC:
        for j in i:
            if j == 1:
                try:
                    if matrixC[i-1]==1 or matrixC[i+1]==1:
                     .......

无论出于何种原因,这都是一次真正的斗争,我似乎无法弄清楚要做什么,任何提示或帮助将不胜感激!谢谢.

Answer 1

使用scipy你会做类似以下的事情

import numpy

boundaries = numpy.array([
                         [0,0,0,0,0],
                         [0,1,1,1,0],
                         [0,1,1,1,1],
                         [0,1,1,1,0],
                         [0,0,1,0,0]])

counts = scipy.signal.convolve2d(boundaries, numpy.ones((3,3)), mode='same')

# which gives you a matrix with counts of the number of 1s around each point
array([[ 1.,  2.,  3.,  2.,  1.],
       [ 2.,  4.,  6.,  5.,  3.],
       [ 3.,  6.,  9.,  7.,  4.],
       [ 2.,  5.,  7.,  6.,  3.],
       [ 1.,  3.,  4.,  3.,  1.]])

 # so then you just find the points where it's == 9
 counts == 9
 array([[False, False, False, False, False],
        [False, False, False, False, False],
        [False, False,  True, False, False],
        [False, False, False, False, False],
        [False, False, False, False, False]], dtype=bool)

 # so you can update those positions
 boundaries[counts == 9] = 0

所以整个操作很简单:

boundaries = numpy.array(Boundaries)
counts = scipy.signal.convolve2d(boundaries, numpy.ones((3,3)), mode='same')
boundaries[counts == 9] = 0

Answer 2

由于后来没有添加 numpy 要求，我觉得我应该添加一个纯 python 答案。

你可以翻转算法。这个答案的灵感来自计算机视觉特征提取中使用的霍夫变换 ( http://en.wikipedia.org/wiki/Hough_transform )。与其四处寻找职位，不如让职位为它们影响的事物投票。在您的情况下，每个带有 1 的位置都为自己及其所有邻居投票。

这是一种不同的方法，但它简化了触及数据边缘的逻辑。您可以忽略该方面，因为即使例如 (-1, 0) 被投票，它也不会获得足够的票数来考虑。

更新

更改为单元格不为自己投票。这使我们也可以在其他情况下使用它（通过搜索具有 8 票的单元格）。我已将其拆分为一个函数，该函数查找被 1 包围的所有单元格和一个执行翻转的操作（取决于您要搜索的内容）。

import collections
import itertools


def neighbours_of(i, j):
    """Positions of neighbours (includes out of bounds but excludes cell itself)."""
    neighbours = list(itertools.product(range(i-1, i+2), range(j-1, j+2)))
    neighbours.remove((i, j))
    return neighbours


def find_surrounded(grid):
    """List of x,y positions in grid where the cell is surrounded by 1s."""

    votes = collections.defaultdict(int)

    for i, x in enumerate(grid):
        for j, y in enumerate(x):
            # we don't get to vote if not ...
            if y == 0:
                continue

            # vote for everyone in the 3x3 square around us
            for a, b in neighbours_of(i, j):
                votes[(a, b)] += 1

    # now the things we want to change are those that got 8 votes
    surrounded_positions = [pos for pos, count in votes.items() if count == 8]

    return surrounded_positions

def change_when_cell_type_surrounded(grid, cell_type):
    """Update grid inline to flip bits of cells of cell_type that are surrounded."""

    # we'll flip to the opposite of what we're looking for
    change_to = 1 - cell_type

    surrounded = find_surrounded(grid)    

    for i, j in surrounded:
        if grid[i][j] == cell_type:
            grid[i][j] = change_to


grid = [[0,0,0,0,0],
        [0,1,1,1,0],
        [0,1,1,1,1],
        [0,1,1,1,0],
        [0,0,1,0,0]]

change_when_cell_type_surrounded(grid, 1)
change_when_cell_type_surrounded(grid, 0)