在网格中寻找相邻单元格的Pythonic和高效方式

我使用pyglet/openGL在Python中构建基于图块的应用程序，其中我需要找到给定单元格的所有相邻单元格。我正在笛卡尔网格的一个象限中工作。每个单元格都有一个x和y值，表示它在网格中的位置（x_coord和y_coord）。这些不是像素值，而是网格位置。我正在寻找一种有效的方式来获得邻近的细胞。马克斯也有，但由于电网的边界的八个可能的相邻单元有可能是一个简单但可能低效的方法尽可能少的3伪代码看起来是这样的：在网格中寻找相邻单元格的Pythonic和高效方式

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密集型方法？或者，我应该用这种方法滚动吗？

在此先感谢。

来源

2010-03-03 JeremyFromEarth

是不是形容词'pythonesque'？ :-) – Simon

如果你想保持这种做法，那么我至少会计算一下计算结果的结果。当它达到8时，跳出循环。另外，当你附加一个单元格时，只检查它是否等于8。 –

我不清楚在单元中是否有其他信息，而不仅仅是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中的每个单元格进行8次检查。

来源

2010-03-03 17:58:03

这种方法看起来是最快的，因为它不涉及迭代每个单元格。使用元组作为键是一个很好的选择。谢谢 – JeremyFromEarth

那么，这将不利于任何性能，但可以说

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-03 17:23:54 jcdyer

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

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

来源

2010-03-03 17:24:24

你的代码将会像你的网格一样慢，因为你正在迭代单元格以获得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-03 17:27:44 fortran

在一个网格中，邻接意味着如果我没有错误或偏高，则只需要一个坐标就可以到达另一个坐标。

if abs(c.x_coord -_coord +c.y_coord-y_coord) == 1 
    print "they are adjacent!"

来源

2017-02-27 04:25:37 user3783689

在网格中寻找相邻单元格的Pythonic和高效方式

回答

相关问题