在Python中高效地按位置分组坐标点列表

Question

给定一个在二维网格上的X,Y坐标点列表，最有效的算法是什么来创建相邻坐标点的分组列表？

举个例子，假设有一组点组成了两个不相邻的3x3的方块，在一个15x15的网格上，这个算法的结果将会是两个点的组，分别对应这两个方块。

我想你可以使用洪水填充算法，但这似乎有点过于复杂，而且对于一个比如1024大小的大二维数组来说，效率也不是很好。

Answer 1

你提到的“相邻的”坐标点是什么意思还不太清楚。你给出的两个不相邻的3x3方块的例子，说明你可能是在寻找一种叫做连通组件标记的东西。

有很多方法可以提取连通组件。下面是一些可以参考的实现。

1. cclabel
2. OpenCV
3. bwconncomp

不过，我自己也实现过这种“斑点”检测器，如果你想学习的话，其实写起来并不难。如果你只是想要一个现成的解决方案，那我建议使用像OpenCV这样的成熟库，直接用它的Python接口就可以了。

另外，你提到“效率”。要注意，这些算法有单遍和双遍两种版本。单遍算法顾名思义，通常更高效，因为它只需要对数据进行一次处理。如果你的网格非常大，这种方法可能会很有用。

Answer 2

从根本上说，这是一种图像处理操作。如果你使用像 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 3

你可以把所有的坐标点进行哈希处理（比如在Python中用字典结构），然后对于每个坐标点，哈希它周围的邻居点，这样就能找到相邻的点并把它们“合并”在一起。此外，对于每个点，你可以用字典结构来记录它所属的连通分量的指针，并且为每个连通分量维护一个包含该分量所有点的列表。

接下来，当你哈希一个点的邻居并找到匹配时，就可以把这两个点所属的连通分量合并在一起，并更新所有新合并点的组指针。你可以证明，只需要对所有点的邻居进行一次哈希处理，就能找到所有的连通分量。而且，如果在合并两个连通分量时，更新较小的那个连通分量的指针，那么处理的时间就会和点的数量成线性关系。