algorithm - 平面图中的小循环查找

Question

我有一个几何无向平面图，即每个节点都有一个位置并且没有两条边交叉的图，我想找到所有没有边交叉的循环。

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

---

我打算做的是一种A*类似的解决方案：

• 将最小堆中的每条边作为路径插入
• 使用每个选项扩展最短路径
• 剔除循环回到起点以外的路径（可能不需要）
• 剔除将是第三个使用给定边缘的路径

有没有人看到这个问题？它甚至会起作用吗？

Answer 1

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

Answer 2

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

这篇论文看起来可能会有所帮助。

Answer 3

一个简单的方法是简单地出去枚举每张脸。原理很简单：

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

走瓷砖由以下方式执行：

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

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