我有一个边列表和一个顶点列表。每条边引用两个顶点，每个顶点维护一个边列表。
我想找到从此图生成的所有不重叠的多边形。
例如
0,0) (4,0) (4,2) (4,4) (2,4) (2,2) (4,2) (6,2) (6,6) (0 ,6) (0,0)
该路径应描述每个唯一的边，并在某些顶点上发生碰撞。在实际的图中，顶点是不同的。我需要的两个多边形是 (0,0) (4,0) (4,2) (2,2) (2,4) (4,4) (4,2) (6,2) (6,6) (0,6) 和 (2,2) (2,4) (4,4) (4,2)
I have a list of edges and a list of vertices. Each edge references two vertices, each vertex maintains a list of edges.
I want to find all non-overlapping polygons produced from this graph.
An example would be
0,0) (4,0) (4,2) (4,4) (2,4) (2,2) (4,2) (6,2) (6,6) (0,6) (0,0)
This path should describe each unique edge with collisions on some verticies. In the actual graph, the vertices are distinct. The two polygons I would need from this set are (0,0) (4,0) (4,2) (2,2) (2,4) (4,4) (4,2) (6,2) (6,6) (0,6) and (2,2) (2,4) (4,4) (4,2)
发布评论
评论（2）
您所描述的是在图中找到所有最小电路的问题。 （我认为，它恰好有一个几何模型是无关紧要的。）有一篇论文 此处用于查找最小电路。您可以在此基础上删除最小电路的边缘并再次运行算法。
对于有向图的情况，此线程中也讨论了该问题。您可以通过制作每条边的副本并反转顶点，然后将其视为有向图，将图转换为有向图。唯一的问题是每个多边形都会被发现两次，每个遍历方向各一次。您可以通过后处理步骤或在算法运行时通过一些巧妙的簿记来清理它。
What you are describing is the problem of finding all minimal circuits in a graph. (That it happens to have a geometric model is irrelevant, I think.) There's a paper here for finding a minimal circuit. You can build on that by removing the edges of the minimal circuit and running the algorithm again.
The problem is also discussed in this thread for the case of directed graphs. You can turn your graph into a directed graph by making a copy of each edge with the vertices reversed and then treating it as directed. The only problem will be that each polygon will be found twice, once in each traversal direction. You can clean that up with a post-process step or perhaps by some clever bookkeeping while the algorithm is running.
嗯，我在想......
唯一特别感兴趣的顶点是具有两条以上边的顶点。找到所有具有两条以上边的顶点的时间复杂度为 O(n)。然后，找到最紧密的闭环与在给定顶点处找到给定一条边和另一条边之间的最小 theta 相同（如果顶点是 ccw，则这是从当前边顺时针方向的最小角度）。为了找到所有最紧密的闭环，我需要检查边缘计数大于 2 的顶点处的所有边缘 ccw 边缘对。这是迹线的初始化。从该点开始，迹线将始终顺时针选取具有最小 θ 值的下一条边。返回路径后，我将移动到根顶点中的下一个边对，然后再次路径。检查完所有对后，我将移动到边数大于 2 的下一个顶点。现在，我只能确定是否陷入已知循环而不是跟踪。也许如果路径的前两个顶点以相同的顺序出现在已知的多边形中......
听起来怎么样？我知道这不是 djikstra，但它会起作用，并且希望比暴力破解所有周期更快。
Well, I was thinking...
The only vertices of particular interest are ones with more than two edges. To find all vertices with more than two edges is O(n). Then to find the tighest closed loop is the same as finding the smallest theta between a given an edge and another edge at a given vertex (if the vertices are ccw, this is the smallest angle clockwise from the current edge). In order to find all tightest closed loops, I need to check all edge ccw edge pairs at a vertex where the edge count is greater than 2. This is the initialization of the trace. From that point on, the trace will always pick the next edge with the smallest theta clockwise. Once the path is returned, I move to the next edge pair in the root vertex, and path again. Once all pairs are checked, I move to the next vertex with an edge count greater than 2. Now, if I can only determine if I am falling into a known loop and not trace. Maybe if the first two vertices of a path occur in the same order in an already known polygon...
How does that sound? I know it's no djikstra, but it will work, and hopefully faster than finding all cycles brute force.