Python，规则网格上的邻居

让我们假设我有一组2D坐标，它们表示2D规则网格的单元格的中心。我想为网格中的每个单元找到每个方向上最近的两个邻居。Python，规则网格上的邻居

的问题是相当简单的，如果一个分配给每个小区和指数定义如下：

idx_cell = IDX + N * IDY

其中N是细胞在网格的总数，IDX = x/dx和idy = y/dx，其中x和y是单元格的x坐标和y坐标，dx是其大小。

例如，idx_cell = 5的单元格的相邻单元格是idx_cell等于4,6（对于x轴）和5 + N，5-N（对于y轴）的单元格。

我遇到的问题是，对于大型（N> 1e6）数据集，我的算法实现非常慢。

例如，为了获得x轴的邻居我做

[x[(idx_cell==idx_cell[i]-1)|(idx_cell==idx_cell[i]+1)] for i in cells]

你认为有实现这个算法最快的方法？

来源

2013-03-28 Brian

我认为你可以通过使用NumPy花式索引加速它。你能发布更多的代码来创建'idx，idy，cells，idx_cells，x'。 – HYRY 2013-03-28 10:56:16

您也许可以使用scipy的cKDTree。 http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.cKDTree.html – Daniel 2013-03-28 13:33:15

谢谢我已经尝试过使用KDTree，但是对于我的数据集来说它相当慢，而且对于一个网格。不幸的是我不能发布更多的代码，因为我的数据集很大。 – Brian 2013-03-28 13:35:45

你基本上是重新创建多维数组的索引方案。编码相对容易，但您可以在这里使用两个函数unravel_index和ravel_multi_index。

如果您的网格是M行和N列，得到idx和单个项目的idy你可以这样做：

>>> M, N = 12, 10 
>>> np.unravel_index(4, dims=(M, N)) 
(0, 4)

这也适用，如果，而不是一个单一的指标，你提供了一个数组索引：

>>> np.unravel_index([15, 28, 32, 97], dims=(M, N)) 
(array([1, 2, 3, 9], dtype=int64), array([5, 8, 2, 7], dtype=int64))

所以，如果cells有几个小区的索引你想找到邻居：

>>> cells = np.array([15, 28, 32, 44, 87])

你可以得到他们的邻居为：

>>> idy, idx = np.unravel_index(cells, dims=(M, N)) 
>>> neigh_idx = np.vstack((idx-1, idx+1, idx, idx)) 
>>> neigh_idy = np.vstack((idy, idy, idy-1, idy+1)) 
>>> np.ravel_multi_index((neigh_idy, neigh_idx), dims=(M,N)) 
array([[14, 27, 31, 43, 86], 
     [16, 29, 33, 45, 88], 
     [ 5, 18, 22, 34, 77], 
     [25, 38, 42, 54, 97]], dtype=int64)

或者，如果你喜欢它这样：

>>> np.ravel_multi_index((neigh_idy, neigh_idx), dims=(M,N)).T 
array([[14, 16, 5, 25], 
     [27, 29, 18, 38], 
     [31, 33, 22, 42], 
     [43, 45, 34, 54], 
     [86, 88, 77, 97]], dtype=int64)

要不要去这样的最美好的事情是，ravel_multi_index有mode关键字参数您可以使用它来处理网格边缘的物品，请参阅文档。

来源

2013-03-28 17:15:04 Jaime

Python，规则网格上的邻居

回答

相关问题