如何从包含共线边的多边形中提取简单多边形？
对于下面非常简单的情况，边2-3和6-0是共线的我想把它分成0，1，2和3，4，5，6。
我可以比较每一条边和每一条边的共线性，但这是一个缓慢的o（n^2）方法。有更快的方法吗？
最佳答案
找到一个边界圆。计算边界圆和每条边所在的直线之间的上/右交点。我是O（n）现在，根据每条边的角度元组及其与边界圆相交的角度位置对每条边进行排序这是o（nlogn），将在排序列表中将共线边组合在一起。
如果你不太可能有很多平行但非共线的边，那么你可以跳过边界圆的事情，只是按角度排序如果有很多平行的非共线角度，那么仅仅使用角度仍然“有效”，这并不能给你带来效率的提高。