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

Question

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

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

Answer 1

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

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