平面图中的小循环查找

我的第一直觉是使用类似于 wall following 迷宫求解器。基本上,跟随边,总是从顶点中取出最右边的边。使用此方法遇到的任何循环都将是面的边界。你必须跟踪你在哪个方向穿过的边。一旦你在两个方向穿过一条边,你就可以识别出它分开的面。一旦所有边在两个方向上都被遍历,就可以通过它们的边界来识别所有面。

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

This paper 看起来可能会有帮助。

要做到这一点,一个简单的方法就是简单地去列举每一张脸。原理很简单:

• 我们为每个边缘维护“访问”和“访问”标志,并为每个此类标志维护一对未访问边缘的双重链接列表。“_”和“_”划分应对应于与所述边缘对应的直线上的平面划分;哪一侧为_?,哪一侧为_?是任意的。
• 对于每个顶点V:
  • 对于每个相邻的边对e=(v_1,v),e'=(v_2,v)(即,按角度排序,取相邻的边对,以及第一个+最后一个边对):
  • 确定E(S=_?或_2)V_2的S侧。
  • 从V开始,使用E的S侧行走瓷砖,如下所述:

在瓷砖上行走的方式是:

• 设v= vth-nIT
• 循环:
  • v_next=e的顶点,不是v
  • e’=e的当前边上的v_next到e的相邻边。
  • s'=e'中包含v的边
  • 如果v_next=v,我们找到了一个循环;记录我们在路上经过的所有边,并将这些边对标记为已访问。
  • 如果e’=e(只有一条边),那么我们就走到了尽头;中止这次步行。
  • 否则,让v=v_next,e=e',s=s'继续。

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