线段的多边形

Question

我有一个没有特定顺序的线段列表。

我想找到由线段形成的所有封闭空间（多边形）。有没有一种有效的算法或方法可以用来做到这一点？

下图说明了这个问题。给定黑色线段，如何检测绿色多边形？

Answer 1

一种方法是构建如下图表：

• 节点是边的交点

• 节点 i 和 j 之间有一条边，当且仅当点 i 和 j 位于同一条边上

构建图表后：

• 在其上运行连通分量算法，并检查大小 > 2 的连通分量

• 在此类组件内的交点上运行凸包算法

编辑由于 FooBar 的优秀观点而对原始内容进行了修改。

Answer 2

这确实是计算几何中的经典问题。

您正在寻找您的分段的

faces

安排。

对于这个主题的讨论（太多）细节和源代码，有这个很棒的库：CGAL。

请注意，您必须决定要做什么，例如一个多边形位于另一个多边形内，许多多边形交织在一起，等等

Answer 3

Ami 的答案很好地指明了正确的方向，但以下是您可能需要了解的更详细的步骤：

1. 获取线段列表并构建顶点集合。由于通过暴力方式检查每个单独的线段是否与其他线段相交基本上是一个 N^2 操作，因此您可能需要构建一个四叉树并使用它来减少正在执行的检查数量。如果 n 很小或者你有很多 cpu 时间需要消耗，就暴力破解它，否则你需要巧妙地进行碰撞检测。这是一个实现四叉树碰撞检测的库：https://github.com/hroger1030/SpatialTrees

2. 有了节点和边的列表，您就可以构建图表了。您可以将线称为节点，将交点称为边缘，反之亦然，这并不重要。重要的是，您现在可以找到图表上的所有循环，其中循环中的节点数 > 2。

我正好用c#写了一个Tarjan Cycle检测的实现：Tarjan Cycle detector help C#。这可能是建议的连通分量算法的替代方案。

Answer 4

几年后我知道了，但我可以推荐 Stijn Oostdam 出色的“PolygonsFromLines”nuget，它非常优雅地解决了这个问题。 Nuget 画廊链接