BCS*_*BCS 9 language-agnostic algorithm graph-theory planar-graph
我有一个几何无向平面图,这是一个图,其中每个节点都有一个位置,没有2个边交叉,我想找到没有边穿过它们的所有周期.
这个问题有没有什么好的解决方案？
我打算做的是一种A*类似的解决方案:
A*
有没有人看到这个问题？它会工作吗？
use*_*368 11
我的第一直觉是在迷宫求解器之后使用类似于墙的方法.本质上,跟随边,并始终从顶点取出最右边.您使用此方法遇到的任何周期都将是面部边界.您必须跟踪您在哪个方向上经过的边缘.一旦你在两个方向上遍历了一条边,你就已经确定了它所分离的面.一旦所有边都在两个方向上遍历,您就可以通过边界识别所有面.
Joh*_*uhy 5
正如你所说的,"交叉边缘"通常被称为和弦.因此,你的问题是找到所有无弦循环.
这篇论文看起来可能有所帮助.
归档时间：
16 年，9 月 前
查看次数：
2741 次
最近记录：
14 年，4 月 前