计算几何（多边形）

Question

如果我们给出了一组S段，我们可以设计一个算法来测试集合S中的段是否可以形成一个多边形，如果它们与多边形相交，我不感兴趣，我只是想知道关于我可以测试什么标准，

任何建议

Answer 1

构造一个图形数据结构，其中节点表示在集合S连接段A和链段B与如果A和B相交的边缘区段。遍历图来确定是否有任何循环。每个周期对应一个候选多边形。

Answer 2

为了记录，这里是一个可能更直接的解决方案（第一个答案是构造双图可能不太明显）。

构造一个图形，其中来自给定线段的每个（不同的）端点都是一个顶点，并且每个给定的线段都是一条边线。对此图进行深度优先搜索遍历以查找循环。这些周期是候选多边形。