平面图中的小环查找

Question

我有一个几何无向 平面图, ，这是一个图，其中每个节点都有一个位置并且没有 2 个边交叉，我想找到没有边交叉的所有循环。

对于这个问题有什么好的解决方案吗？

---

我打算做的是 A* 像解决方案：

• 将最小堆中的每条边插入为路径
• 每个选项都延长最短路径
• 剔除循环回到起始位置以外的路径（可能不需要）
• 剔除第三个使用 ang 给定边缘的路径

有人看到这有问题吗？它还能起作用吗？

Answer 1

我的第一直觉是使用类似于 墙追随 迷宫求解器。本质上，遵循边，并始终从顶点取出最右边的边。使用此方法遇到的任何循环都将是面的边界。您必须跟踪您在哪个方向上遍历过哪些边缘。一旦您在两个方向上穿过一条边，您就可以识别出它所分隔的面。一旦所有边都在两个方向上遍历完毕，您就可以通过边界识别所有面。

Answer 2

正如您所说，“交叉边缘”通常被称为 弦. 。因此，你的问题是找到所有无弦循环。

这张纸 看起来可能有帮助。

Answer 3

执行此操作的一个简单方法是简单地枚举每张脸。原理很简单：

• 我们为每个边维护“α-访问”和“β-访问”标志，并为每个此类标志维护一对未访问边的双向链表。“α”和“β”划分应对应于与所讨论的边缘对应的线上的平面划分；哪一边是α，哪一边是β是任意的。
• 对于每个顶点 V：
  • 对于每对相邻的边 E = (V_1, V), E'=(V_2, V) （即按角度排序，取相邻对，以及第一个+最后一个）：
  • 确定V_2位于E（S=α或β）的哪一侧S。
  • 从 V 开始，使用 E 的 S 边沿着图块行走，如下所述：

行走瓷砖的执行方式是：

• 令 V = V_init
• 环形：
  • V_next = E 中非 V 的顶点
  • E' = 从 V_next 到 E 的当前侧的相邻边
  • S' = E' 包含 V 的一侧
  • 如果V_next = V，我们就找到了一个循环；记录我们途中经过的所有边，并将这些边对标记为已访问。
  • 如果 E' = E（只有一条边），那么我们就进入了死胡同；中止这次步行
  • 否则，令 V = V_next、E = E'、S = S' 并继续。

我希望这是有道理的；也许需要一些图表来解释......