9

请看图片：http: //i.stack.imgur.com/NPUmR.jpg

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

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

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

要求 ：

i) 多边形不得重叠或相交。即：Cycle ABFHDCA 不是有效的多边形，因为它会与 Polygon FHGE 重叠。循环 ABFEGHDCA 是一个有效的多边形。

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

iii) 像 K 和 L（即叶子）这样的顶点不构成多边形的一部分。我们不关心边缘 JK。

更新： iv）在图中边不交叉。两条边唯一可以相遇的地方是一个顶点。前面的阶段/算法保证是这种情况。

问题：

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

  2. 是否有解决此问题的现有替代算法？

补充说明：

a）我在用更具体的计算几何术语定义这个问题时遇到了麻烦，所以我坚持在无向图中寻找多边形。我必须承认，我学习图论已经有好几年了。我现在正在刷它。

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

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

类似的解决方案

  1. 我找到了一个类似的帖子，但接受的解决方案似乎没有为此示例生成正确的周期。

提前致谢！

4

2 回答 2

1

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

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

于 2012-10-20T07:21:15.577 回答
0

对于初学者，让我们摆脱退化的边缘（JK在JL你的例子中）：找到具有单个边缘的顶点并将它们从图中删除。请注意，此删除还可能创建另一个退化边缘，因此每次删除 vertexA和 edgeAB时，再查看 vertexB以查看它现在是否也退化。

现在请注意，虽然每个顶点可以涉及任意数量的多边形，但每条边恰好涉及两个。因此，我建议我们可以通过越过边缘而不是顶点来让自己的生活变得更简单。

  1. 将两个布尔字段与每条边相关联，以记录是否找到了left和right多边形。这些字段最初应该都是false.
  2. 选择任意一条边，我们称之为AB
    1. 如果AB.right是false：
      1. L创建一个用于存储多边形边的空列表
      2. 设置并添加AB.right到trueABL
      3. 迭代顶点的边B以找到多边形的下一条边。想象一下，您从A到开车B，下一个边缘是迫使您在 处做出最急可能右转弯的边缘B。我确信边缘向量的点积将使这个搜索变得微不足道，但是我回忆起细节已经太久了。
      4. 为下一条边递归第 2 步和第 3 步（将right变量设置为true并将边添加到L），直到您碰到right已经是的边true。这将是您开始的边缘 - 您已经找到了一个完整的多边形，并且您已经从搜索空间中消除了一堆边缘！
    2. 如果AB.left是false，请执行与上述相同的步骤，只是这次您朝相反的方向（从B朝向A）行驶，并且您将left字段设置true为 。请注意，您仍在尝试在每个顶点处进行尽可能锐利的右转。这将产生另一个多边形并从您的搜索中消除另一束边。
  3. 重复直到每条边的left和right字段为true。

我们将生成一个多边形列表，但该列表将包含一些我们不想要的多边形 - 包含平面外部空间的多边形（在您的示例图像中，这些将是XZY和ACDHJIB）。这些可以通过检查顶点的缠绕顺序来检测。我们在每个顶点都向右转，所以我们想要的多边形将显示顺时针缠绕顺序。

于 2021-11-16T15:38:42.670 回答