来自多边形邻居列表的多边形簇

Question

我已经实现了这个 algorithm 来为每个多边形生成一个相邻多边形列表。实施工作正常。

现在我打算生成一个多边形簇列表。每个集群包含共同的邻居：

我在尝试提出一种将共同邻居合并到集群中的算法时有点困惑。是否有任何标准算法可以这样做？

Answer 1

这通常使用 depth-first search or a breadth-first search。

对于 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

此算法完成后，每个多边形都将分配给一组连通分量。

Answer 2

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

MakeSet(p) 创建一个包含 p 的单例集。
Find(p) 其中 p 是宇宙的一个元素（这里是所有多边形的集合），returns 一个 "distinguished element (polygon)" 表示包含 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)]

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

具有按等级并集和折叠查找的联合查找算法本质上是恒定时间（阅读维基百科文章了解反阿克曼函数的理论细节），在实践中非常快，并且易于实现。所有的map操作也是常量时间

因此，该算法的运行速度（基本上）与多边形输入列表的总和成正比；尽可能快。

来自多边形邻居列表的多边形簇

Polygon clusters from List of polygon Neighbors

algorithm

3d

mesh

polygon