多边形邻居列表中的多边形簇。

Question

我已经实现了这一点 算法 来为每个多边形生成相邻多边形的列表。这个实现工作得很好。

现在我打算生成一个多边形簇的列表。每个簇都包含共同的邻域。

我有点迷惑了，要想出一种算法来把共同的邻域合并到聚类中。有没有什么标准算法可以做到这一点？

Answer 1

这是一个经典的不相干集合 联合寻找 问题。union-find算法及其相关数据结构支持三种操作。

• MakeSet(p) 制造一个包含p的单子集。
• Find(p)其中p是宇宙中的一个元素（这里是你的所有多边形的集合），返回一个 "区分元素（多边形）"，代表包含p的整个集合，例如，Find(MakeSet(p))=p。
• Union(p,q)将包含p和q的集合替换为这两个集合的联合，这样之后，Find(p)== Find(q)。如果p和q已经在同一个集合中，这就是一个无操作。

现在执行下面的算法。

for each polygon p
  MakeSet(p)
for each polygon p
  for each polygon q that's a neighbor of p
    Union(p, q)
Let m be a map from polygons to lists of polygons, intitially empty
for each polygon p
  append p to map[Find(p)] 

现在地图中的值（多边形列表）就是你的答案。

Union-Find算法与按秩结合和折叠查找基本上是恒定时间的（请阅读维基百科的文章，了解反阿克曼函数的理论细节），在实践中速度非常快，而且容易实现。 所有的映射操作也都是恒时的。

因此，这个算法的运行速度（基本上）与输入的多边形列表的总和成正比；大约是越快越好。

Answer 2

一般来说，这是用一个 深度优先搜索 或 广度优先搜索.

在BFS的情况下，你可以做如下的事情。

Create an empty queue, and assign all polygons to group -1. Set the current group to 0
While there are any polygons in group -1:
    Randomly grab a polygon which is in group -1 and add it to the queue
    While the queue is not empty:
        Grab the first polygon in the queue and assign it to the current group
        Find all of that polygon's neighbors
            For all of the neighbors, if they are in group -1, add them to the queue
        Remove the selected polygon from the queue
    Increment the current group

当这个算法完成后 每个多边形都会被分配到一个由连接的组件组成的群组中去