我有一个几何的无向平面图,它是一个图,每个节点都有一个位置,没有两个边交叉,我想找到所有没有边交叉的循环。
对这个问题有什么好的解决办法吗?
我打算做的是一种类似于A*的解决方案:
有人看到这个有问题了吗?它还能用吗?
发布于 2009-05-08 03:26:52
我的第一本能是使用一种类似于墙跟随迷宫求解器的方法。本质上,跟随边,总是从顶点取最右边的边。使用此方法所遇到的任何周期都将是脸的边界。你必须跟踪你走过哪个方向的边。一旦你在两个方向上穿过了一个边缘,你就能识别出它所分离的面孔。一旦所有的边缘都在两个方向上被跨越,你就可以通过它们的边界来识别所有的面孔。
发布于 2009-05-08 03:45:46
要做到这一点,一个简单的方法是简单地走出去,并列举每一张脸。原则很简单:
行走瓷砖是通过以下方式进行的:
我希望这是有意义的,也许需要一些图表来解释.
https://stackoverflow.com/questions/838076
复制相似问题