在无向图内查找多边形

Question

请参阅图片：http：//i.stack.imgur.com/NPUmR.jpg

我有一个无向图，其中包含一个或多个连接的子图。该图由一组连接的顶点的有序对定义。最多可能有300个顶点。该图是平面的。

我需要识别图像中所示的多边形。每个单独的多边形中的彩色区域。粗略的试探法可能是，多边形是图形中封闭边缘环（循环）之间的“封闭区域”。在类似的帖子中已经建议可以使用“深度优先”遍历并标记访问的顶点来标识周期。

但是，我不确定在此之后如何进行操作以获取所需的输出，如图中所示。

要求 ：

i）多边形不得重叠或相交。即：循环ABFHDCA不是有效的多边形，因为它将与多边形FHGE重叠。循环ABFEGHDCA是有效的多边形。

ii）多边形可以具有3个或更多的边，并且多边形必须以图形的边为边界。XYZ是有效的多边形，尽管与图的其余顶点断开了连接。

iii）诸如K和L（即叶子）之类的顶点不构成多边形的一部分。我们不在乎边缘JK。

更新： iv）在图中，边不交叉。两条边只能相交的地方是顶点。通过前一阶段/算法可以保证确实如此。

问题：

1. 我是否在使用DF纵行寻找轨道方法的正确轨道上？在这种情况下，DF遍历会给我提供我需要考虑的所有（简单）循环吗，尤其是在XYZ与图的其余部分断开连接的情况下？

2. 是否存在解决此问题的替代算法？

附加条款：

a）我在用更具体的计算几何术语来定义此问题时遇到了麻烦，因此坚持在无向图内查找多边形。我必须承认，自从学习图论以来已经有好几年了。我现在正在整理。

b）对此的解决方案似乎不是凹/凸包算法。我们正在谈论的是一组相连的边-真正的多边形，而不仅仅是需要包含的点云。

c）上面的示例是我可以在短时间内提出的。我认为它涵盖了大多数“边缘”情况（双关语）:)

类似解决方案

1. 我发现了类似的帖子，但是被接受的解决方案似乎无法为该示例生成正确的周期。

提前致谢！

Answer 1

提取平面图区域的最佳算法：http://www.sciencedirect.com/science/article/pii/016786559390104L

您想要做的是从嵌入的平面图中提取多边形/区域。上面的论文给出了算法。时间复杂度为 \Omega (m \log{m})，空间复杂度为 \Omega (m)，其中 m 是图中的边数。