线段的多边形

Question

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

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

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

Answer 1

一种方法是构建如下图：

• 节点是边的交点

• 如果点i和j在同一条边上，则节点i和j之间存在边

一旦你建立了图表：

• 在其上运行连接组件算法，并检查大小 > 2 的连接组件

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

由于 FooBar 的出色之处，从原始编辑修改。