在Python中按位置有效地对坐标点列表进行分组

Question

给定2D网格上的X，Y坐标点列表，创建相邻坐标点组列表的最有效算法是什么？

例如，给定组成网格（15x15）上两个不相邻的正方形（3x3）的点的列表，此算法的结果将是对应于两个正方形的两组点。

我想你可以做一个洪水填充算法，但是这似乎过大了，对于一个大的2D数组，比如说1024个大小，不是很有效。

Answer 1

从根本上说，这是一个图像处理操作。如果您使用像scikit-image（又名skimage）这样的图像处理库，那会很容易。处理真正庞大的数据最终会变慢，但 1024x1024 算不了什么。

In [1]: import numpy as np
In [2]: import skimage.morphology
In [3]: x = [0,1,2,0,1,2,0,1,2,-3,-2,-1,-3,-2,-1,-3,-2,-1]
In [4]: y = [0,0,0,1,1,1,2,2,2,-3,-3,-3,-2,-2,-2,-1,-1,-1]
In [5]: dense = np.zeros((9,9), dtype=bool)
In [6]: dense[y,x] = True

In [7]: print(dense)
[[ True  True  True False False False False False False]
 [ True  True  True False False False False False False]
 [ True  True  True False False False False False False]
 [False False False False False False False False False]
 [False False False False False False False False False]
 [False False False False False False False False False]
 [False False False False False False  True  True  True]
 [False False False False False False  True  True  True]
 [False False False False False False  True  True  True]]

In [8]: labeled = skimage.morphology.label(dense)
In [9]: print(labeled)
[[1 1 1 0 0 0 0 0 0]
 [1 1 1 0 0 0 0 0 0]
 [1 1 1 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 2 2 2]
 [0 0 0 0 0 0 2 2 2]
 [0 0 0 0 0 0 2 2 2]]

In [10]: coords_yx = { i: (labeled == i).nonzero() for i in range(1,labeled.max()+1) }
In [11]: coords_yx
Out[11]:
{1: (array([0, 0, 0, 1, 1, 1, 2, 2, 2]), array([0, 1, 2, 0, 1, 2, 0, 1, 2])),
 2: (array([6, 6, 6, 7, 7, 7, 8, 8, 8]), array([6, 7, 8, 6, 7, 8, 6, 7, 8]))}

Answer 2

您可以对所有坐标点进行散列（例如，使用python中的字典结构），然后对于每个坐标点，散列该点的相邻邻居以找到相邻的点对并“合并”它们。此外，对于每个点，您可以维护一个指向该点所属的连接组件的指针（使用字典结构），并且对于每个连接的组件，您可以维护属于该组件的点列表。

然后，当您散列一个点的邻居并找到匹配项时，您可以合并这些点所属的两个连通分量集，并更新联合集中所有新点的组指针。您可以证明，您只需要对所有点的所有邻居进行一次散列，这将找到所有连通分量，此外，如果在合并两个连通分量集时更新两个连通分量集中较小的一个的指针，那么运行时间将与点数成线性关系。