从具有共线边的多边形中提取多边形

Question

如何从包含共线边的多边形中提取简单多边形？对于下面非常简单的情况，边2-3和6-0是共线的。我想把它分成0，1，2和3，4，5，6。

我可以将每条边的共线性与其他每条边的共线性进行比较，但这是一个很慢的O(n^2)方法。有没有更快的方法？

​

​

Answer 1

找到一个边界圆。计算边界圆和每条边所在的线之间的上/右交点。这是O(n)。现在，根据每条边的角度元组以及它与边界圆相交的角度位置对每条边进行排序。这是O(nlogn)，它会将排序列表中的共线边组合在一起。

如果你不太可能有很多平行但不共线的边，那么你可以跳过边界圆的事情，只按角度排序。如果有很多平行的非共线角度，那么仅仅使用角度仍然是“有效的”，它不会给你带来更多的效率提升。

Answer 2

你能找到1-2和6-0的交点吗？如果是这样，您可以生成一个包含边和顶点的图。然后，找到所有不重叠的多边形就很简单了。