我有一个边列表和一个顶点列表每个边引用两个顶点，每个顶点维护一个边列表。
我想找到从这个图产生的所有不重叠的多边形。
例如
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）
最佳答案
你所描述的是在图中找到所有最小电路的问题（我认为，它碰巧有一个几何模型是不相关的）有一篇关于寻找最小电路的论文您可以通过删除最小电路的边并再次运行算法来构建它。
对于有向图的情况，在here中也讨论了这个问题。您可以将图转换为有向图，方法是复制每个顶点反转的边，然后将其视为有向图唯一的问题是每个多边形将被发现两次，在每个遍历方向一次。您可以通过后期处理步骤或在算法运行时进行一些巧妙的记帐来清理该问题。