12

我正在使用 pyglet/openGL 在 Python 中构建一个基于磁贴的应用程序，其中我需要找到给定单元格的所有相邻单元格。我在笛卡尔网格的一个象限中工作。每个单元格都有一个 x 和 y 值，表示它在网格中的位置（ x_coord 和 y_coord ）。这些不是像素值，而是网格位置。我正在寻找一种有效的方法来获取相邻的单元格。最多有 8 个可能的相邻单元格，但由于网格的边界，可能只有 3 个。一个简单但可能效率低下的方法的伪代码如下所示：

def get_adjacent_cells( self, cell ):
     result = []
     x_coord = cell.x_coord
     y_coord = cell.y_coord
     for c in grid.cells:
          if c.x_coord == x_coord and c.y_coord == y_coord: # right
               result.append( c )
          if c.x_coord == x_coord - 1 and c.y_coord == y_coord + 1: # lower right
               result.append( c )
          if c.x_coord == x_coord - 1 and c.y_coord == y_coord: # below
               result.append( c )
          if c.x_coord == x_coord - 1 and c.y_coord == y_coord - 1: lower left
               result.append( c )
          if c.x_coord == x_coord and c.y_coord == y_coord - 1: right
               result.append( c )
          // -- similar conditional for remaining cells

这可能工作得很好，尽管此代码可能需要运行每一帧并且在更大的网格中它可能会影响性能。关于更精简和更少 CPU 密集型方法的任何想法？或者，我应该采用这种方法吗？

提前致谢。

4

6 回答 6

11

我不清楚单元格中是否还有其他信息，而不仅仅是 x 和 y 坐标。无论如何，我认为需要改变数据结构以使其更快。

我假设单元格中有额外的信息，并grid.cells作为一个字典，键是坐标的元组。grid.cells如果单元格中只有坐标信息，则可以将类似的事情作为一组来完成。

def get_adjacent_cells( self, x_coord, y_coord ):
    result = {}
    for x,y in [(x_coord+i,y_coord+j) for i in (-1,0,1) for j in (-1,0,1) if i != 0 or j != 0]:
        if (x,y) in grid.cells:
            result[(x,y)] = grid.cells[(x,y)]

根据您要对数据执行的操作，您可能不想将结果设为字典，但希望您能理解。这应该比您的代码快得多，因为您的代码对grid.cells.

于 2010-03-03T17:58:03.757 回答
9

您的代码将与您的网格一样慢，因为您遍历单元格只是为了获得其中的 8 个（您已经知道它们的坐标）。

如果您可以通过他们的索引进行随机访问，我建议如下：

adjacency = [(i,j) for i in (-1,0,1) for j in (-1,0,1) if not (i == j == 0)] #the adjacency matrix

def get_adjacent_cells( self, cell ):
     x_coord = cell.x_coord
     y_coord = cell.y_coord
     for dx, dy in adjacency:
          if 0 <= (x_coord + dx) < max_x and 0 <= y_coord + dy < max_y: #boundaries check
#yielding is usually faster than constructing a list and returning it if you're just using it once
              yield grid[x_coord + dx, y_coord + dy]

max_x并且max_y应该是网格的大小，并且grid.__getitem__应该接受带有坐标的元组并返回该位置的单元格。

于 2010-03-03T17:27:44.443 回答
2

好吧，这对性能没有任何帮助，但是您可以通过说来避免代码重复

if abs(c.x_coord - x_coord) == 1 or abs(c.y_coord - y_coord) == 1:
    result.append(c)

为了影响性能，你的网格单元应该知道他们的邻居是谁，或者通过一个属性，比如c.neighbors，或者通过一个隐式结构，比如一个列表，所以你可以通过坐标访问。

grid = [[a,b,c],
        [d,e,f],
        [g,h,i]]

然后，您可以使用列表索引检查邻居关系。

于 2010-03-03T17:23:54.017 回答
1

如果 grid.cells 被实现为一个集合，这可能是查找邻居的最有效方法（尽管第一个 if 语句中有一个错误 - 您需要测试与 x_coord + 1 而不是 x_coord 的相等性）。

但是，将 grid.cells 实现为列表列表将允许您按行号和列号引用单个单元格。它还允许您测量行和列的总数。然后 get_adjacent_cells 可以通过首先检查哪些边缘与当前单元格接壤，然后在所有其他方向查找邻居并将它们附加到结果列表中来工作。

于 2010-03-03T17:24:24.810 回答
1

在网格中，邻接意味着如果我没有弄错或高，您只需要一个坐标的一个步骤即可到达另一个坐标。

 if abs(c.x_coord-x_coord+c.y_coord-y_coord) == 1:
     print("They are adjacent!")
于 2017-02-27T04:25:37.877 回答
0

这适用于 numpy 数组

def get_adjacent_cells(arr, selected_idxs):
    """
    >>> arr = np.ones((3,))
    >>> get_adjacent_cells(arr, {(1,)})
    {(0,), (1,), (2,)}
    >>> arr = np.ones((3,2))
    >>> get_adjacent_cells(arr, {(1,1)})
    {(0, 1), (1, 0), (1, 1), (2, 1)}
    >>> arr = np.ones((3,2,3))
    >>> {(0, 1, 0), (1, 0, 0), (1, 1, 0), (1, 1, 1), (2, 1, 0)}
    >>> arr = np.ones((3,2,3))
    >>> get_adjacent_cells(arr, {(1,1,0), (0,1,0)})
    {(0, 0, 0), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 1, 0), (1, 1, 1), (2, 1, 0)}
    """
    w = np.asarray(list(selected_idxs))
    new_idxs = []
    for col in range(w.shape[1]):
        w_ = w.copy()
        w_[:,col] += 1
        new_idxs.extend(list(w_))
        w_ = w.copy()
        w_[:,col] -= 1
        new_idxs.extend(list(w_))

    new_idxs = np.array(new_idxs)

    # remove out of bounds coordinates
    for col, dim_size in enumerate(arr.shape):
        new_idxs = new_idxs[(new_idxs[:, col] >= 0) & (new_idxs[:, col] < dim_size)]

    return selected_idxs.union(map(tuple, new_idxs))
于 2019-04-03T01:59:05.000 回答