c# - 线段的多边形

Question

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

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

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

Answer 1

一种方法是构建如下图:

节点是边的交点

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

一旦你建立了图表:

运行 Connected Components Algorithm在其上，并检查大小 > 2

的连接组件

运行 convex hull关于此类组件内交点的算法

编辑 由于 FooBar 的出色之处，从原始版本进行了修改。