从一组线中检测多边形？
Polygon Detection from a Set of Lines?
我有一组相连的相交线段。我想检测由这些线段相交产生的所有多边形，如下所示：
我找到了一篇论文，介绍了解决这个问题的算法，但我不是计算机科学专业的人，所以我无法理解它。这是 link 到 paper。此时此刻，我的计划是 1) 找到所有交点，以及 2) 以某种方式使用这些交点来识别多边形。我能够通过蛮力解决 (1)，但 (2) 有点棘手。我更喜欢 R 或 C++ 中的解决方案，但任何语言都可以。
假设您的线段始终作为闭合的多边形链，并且您将它们放在某种边缘列表中。而且，正如您所说，您已经计算出交点（蛮力意味着 O(n^2) 时间，在这种情况下是最佳的，因为线段可以相交 n^2 次）。
您可以将 (1) 中的交点插入到此列表中，拆分相交线段，将它们标记为交点并引用该点的所有相交线段。此外，在每条线段上都有两个多边形入射，因此将各自的参考字段添加到每条边。然后只需要输入中最左边的顶点并沿着边列表走。向遍历的每条边添加对其左侧入射多边形（在本例中）多边形一号的引用。如果你到达一个交叉点，把它放在某种堆栈上以供以后恢复。现在分析该点并继续沿着最左边的路径行走（在您到达交点的线段和所有出线段之间）。在某个时候，您到达了起点，并且您已经关闭了第一个简单的多边形。
现在从栈中取出第一个交点。 start/end 必须有偶数个线段。找到一条线段，该线段最多引用一个事件多边形（尚未），并将其用作第二个多边形的起始线段。您可以像以前一样沿着它的链走。 （如果您参考线段的右侧入射多边形，请在交点处向右转。）当您的堆栈为空时，您就完成了。
编辑：在我再次寻找解决方案后，我找到了这个 implementation from Dan Sunday。我认为这更有用，因为它也已经实现了。
Alfredo Ferreira 开发了用于从一组重叠线中检测多边形的 C++ 代码。您可以在他的页面上找到代码：http://3dorus.ist.utl.pt/tools/PolygonDetector.html
希望这有帮助
我刚刚发布了我的实现，在尝试了论文中的算法后速度非常快。
基本思路是去除检测到的循环并重新搜索（去除检测到的循环的“耳朵”）。
我还取消了将点连接到图形的线段。分两步去除重叠：使用面积公式，非常精确，然后近似特定范围内的交点差异。
我有一组相连的相交线段。我想检测由这些线段相交产生的所有多边形，如下所示：
我找到了一篇论文，介绍了解决这个问题的算法，但我不是计算机科学专业的人，所以我无法理解它。这是 link 到 paper。此时此刻，我的计划是 1) 找到所有交点，以及 2) 以某种方式使用这些交点来识别多边形。我能够通过蛮力解决 (1)，但 (2) 有点棘手。我更喜欢 R 或 C++ 中的解决方案，但任何语言都可以。
假设您的线段始终作为闭合的多边形链，并且您将它们放在某种边缘列表中。而且，正如您所说，您已经计算出交点（蛮力意味着 O(n^2) 时间，在这种情况下是最佳的，因为线段可以相交 n^2 次）。
您可以将 (1) 中的交点插入到此列表中，拆分相交线段，将它们标记为交点并引用该点的所有相交线段。此外，在每条线段上都有两个多边形入射，因此将各自的参考字段添加到每条边。然后只需要输入中最左边的顶点并沿着边列表走。向遍历的每条边添加对其左侧入射多边形（在本例中）多边形一号的引用。如果你到达一个交叉点，把它放在某种堆栈上以供以后恢复。现在分析该点并继续沿着最左边的路径行走（在您到达交点的线段和所有出线段之间）。在某个时候，您到达了起点，并且您已经关闭了第一个简单的多边形。
现在从栈中取出第一个交点。 start/end 必须有偶数个线段。找到一条线段，该线段最多引用一个事件多边形（尚未），并将其用作第二个多边形的起始线段。您可以像以前一样沿着它的链走。 （如果您参考线段的右侧入射多边形，请在交点处向右转。）当您的堆栈为空时，您就完成了。
编辑：在我再次寻找解决方案后，我找到了这个 implementation from Dan Sunday。我认为这更有用，因为它也已经实现了。
Alfredo Ferreira 开发了用于从一组重叠线中检测多边形的 C++ 代码。您可以在他的页面上找到代码：http://3dorus.ist.utl.pt/tools/PolygonDetector.html 希望这有帮助
我刚刚发布了我的实现，在尝试了论文中的算法后速度非常快。
基本思路是去除检测到的循环并重新搜索（去除检测到的循环的“耳朵”）。 我还取消了将点连接到图形的线段。分两步去除重叠：使用面积公式，非常精确，然后近似特定范围内的交点差异。