首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >平面图中的小圈发现

问平面图中的小圈发现
EN

Stack Overflow用户
提问于 2009-05-08 03:13:29
回答 3查看 3.5K关注 0票数 9

我有一个几何的无向平面图,它是一个图,每个节点都有一个位置,没有两个边交叉,我想找到所有没有边交叉的循环。

对这个问题有什么好的解决办法吗?

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

  • 插入最小堆中的每个边作为路径
  • 用每个选项扩展最短路径
  • 剔除返回到非起始位置的路径(可能不需要)
  • 选择第三条使用ang的路径

有人看到这个有问题了吗?它还能用吗?

EN

回答 3

Stack Overflow用户

回答已采纳

发布于 2009-05-08 03:26:52

我的第一本能是使用一种类似于墙跟随迷宫求解器的方法。本质上,跟随边,总是从顶点取最右边的边。使用此方法所遇到的任何周期都将是脸的边界。你必须跟踪你走过哪个方向的边。一旦你在两个方向上穿过了一个边缘,你就能识别出它所分离的面孔。一旦所有的边缘都在两个方向上被跨越,你就可以通过它们的边界来识别所有的面孔。

票数 12
EN

Stack Overflow用户

发布于 2009-05-08 03:26:14

所谓的“交叉边”,通常称为和弦。因此,您的问题是找到所有的无绳周期。

本论文看起来可能会有帮助。

票数 5
EN

Stack Overflow用户

发布于 2009-05-08 03:45:46

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

  • 我们为每个边缘维护‘α访问’和‘β访问’标志,并为每个这样的标志维护一对双链接的未访问边缘列表。'α‘和'β’除法应该对应于与所述边对应的直线上的平面分区;哪一边是α,哪一边是β是任意的。
  • 对于每个顶点V:
    • 对于每对相邻的边E= (V_1,V),E'=(V_2,V) (即按角度排序,取相邻对,以及first+last):
    • 确定E (S=α或β) V_2位于哪一边。
    • 从V处开始,使用E的S面行走瓷砖,如下所述:

​

行走瓷砖是通过以下方式进行的:

  • 设V= V_init
  • 循环:
    • V_next =非V的E的顶点
    • E‘=从位于E的当前侧的V_next到E的相邻边
    • S‘=包含V的E’的边
    • 如果V_next = V,我们找到了一个循环;记录我们在途中经过的所有边缘,并在访问时标记这些边缘对。
    • 如果E‘=E(只有一条边),那么我们已经到了死胡同;中止这一步
    • 否则,设V= V_next,E= E',S= S‘并继续。

​

我希望这是有意义的,也许需要一些图表来解释.

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/838076

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档