小周发现在平面图 [英] small cycle finding in a planar graph

问题描述

我有一个几何无向平面图，这是一个图，其中每个节点都有一个位置没有2边穿过，我想找出所有没有边缘十字交叉循环。

I have a geometric undirected planar graph, that is a graph where each node has a location and no 2 edges cross, and I want to find all cycles that have no edges crossing them.

有没有知道这个问题什么好的解决办法？

Are there any good solutions known to this problem?

我正打算做一个排序 A * 类似的解决方案：

What I'm planning on doing is a sort of A* like solution:

• 插入最小堆每条边为路径
• 延长最短路径与每一个选项
• 扑杀路径的循环回以外那里开始（可能并不需要）
• 这将是第三次扑杀路径使用昂给定边

有谁看到一个问题吗？它会甚至工作？

Does anyone see an issue with this? Will it even work?

推荐答案

我的第一反应就是用类似的墙下面迷宫求解。从本质上讲，遵循边缘，始终把最右边了顶点。您遇到这种方法的任何周期将是一个面的边界。你必须跟踪哪些边你走过的方向。一旦你已经走过两个方向的边缘，你发现它分离的面孔。一旦所有的边缘已经走过两个方向，你就必须通过其边界确定所有面。

My first instinct is to use a method similar to a wall following maze solver. Essentially, follow edges, and always take the rightmost edge out of a vertex. Any cycles you encounter with this method will be boundaries of a face. You'll have to keep track of which edges you've traversed in which direction. Once you've traversed an edge in both directions, you've identified the faces it separates. Once all edges have been traversed in both directions, you'll have identified all faces by their boundaries.

这篇关于小周发现在平面图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！