平面图中的小环查找

Question

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

这个问题是否已经有了好的解决方案？

---

我计划做的是一种类似于A*的解决方案：

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

有人看到问题了吗？这样做行得通吗？

- BCS

---

所以，您要找的是每个面的边界？ - user57368

这是一个有向图还是无向图？ - bdonlan

Answer 1

我最初的想法是使用类似于墙随行迷宫求解器的方法。基本上，跟随边缘，并且总是从顶点中选择右侧的边缘。通过这种方法遇到的任何循环都将成为面的边界。您需要跟踪您已经朝着哪个方向穿越了哪些边缘。一旦您在两个方向上横穿一条边，就已经确定了它所分离的面。一旦所有边缘都以两个方向穿过，您将根据它们的边界确定所有面。

- user57368

---

好的解决方案。我唯一能看到的真正技巧是确定“最右边”。然而，由于位置已知，因此您可以使用二维叉积的类比来测试所有可能的出口，以查看哪个与当前边形成最小（逆时针）角度。 - Naaff

@Naaff，获取所有出站角度，从您到达的边缘角度中减去它们，取模2*pi，取最小值。 - BCS

Answer 2

作为你所说的“交叉边”，通常被称为弦。因此，你的问题是找到所有无弦圈。 这篇论文看起来可能会有帮助。

- John Fouhy

---

听起来没问题，我不知道“cord”这个词在圈子外也适用。 - BCS

有没有办法知道我可以在哪里下载它？我的大学账户（拥有访问一切资源的权限）似乎甚至都无法访问。 - BCS

你能通过ScienceDirect获取到它吗？http://dx.doi.org/10.1016/j.jda.2007.01.005 我找不到任何免费的副本。或者你可以尝试给作者发电子邮件并请求一份副本。如果你礼貌得体，他们可能会很乐意给你发送。或者，你可以看看你的大学图书馆是否有这本期刊。 - John Fouhy

ScienceDirect正在要求我购买，但我现在不在图书馆。 - BCS

现在，你经常可以从作者的主页上获取论文。这里就是一个例子：http://math.sun.ac.za/~mwild/Marcel%20Wild%20-%20Home%20Page_files/HamCycles.pdf - Rafał Dowgird

Answer 3

一个简单的方法是直接枚举每个面。原理很简单：

- 我们为每条边维护“α-visited”和“β-visited”标志，并为每个这样的标志维护一对未访问边的双向链表。“α”和“β”的划分应该对应于沿着所讨论的边的线在平面上的一个分区；哪一侧是α，哪一侧是β是任意的。 - 对于每个顶点V：

- 对于每一对相邻的边E =（V_1，V），E' =（V_2，V）（即按角度排序，取相邻对以及第一个+最后一个）： - 确定E的哪一侧S（S = α或β）V_2位于。 - 使用E的S侧从V开始行走，如下所述： -

通过以下步骤来行走瓷砖：

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

我希望这很清楚；可能需要一些图表来解释...

- bdonlan

---

当你说“E' = 从V_next到E的相邻边，且在当前E的一侧”时：我相信可能有多条边E'满足这个条件——对吗？另外，当你说“如果V_next = V，我们找到了一个循环”，你是指“如果V_next = V_init，我们找到了一个循环”吗？ - j_random_hacker

其实，仔细想想，我认为这只是未知（谷歌）的答案以更加复杂的方式解释 - 这就是我在疲倦时回答问题的结果 :/ - bdonlan