从具有共线边的多边形中提取多边形
如何从包含共线边的多边形中提取简单多边形？ 对于下面非常简单的情况，边 2-3 和 6-0 共线。我想将其分为 0、1、2 和 3、4、5、6。
我可以将每个边与其他每个边的共线性进行比较，但这是一种缓慢的 O(n^2) 方法。有没有更快的方法？
How can I extract simple polygons out of a polygon which contains collinear edges?
For the very simple case below, edge 2-3 and 6-0 are collinear. I want to separate this as 0, 1, 2 and 3, 4, 5, 6.
I could compare collinearity of every edge against every other edge, but that is a slow O(n^2) approach. Is there a faster method?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
找到一个边界圆。计算边界圆与每条边所在线之间的上/右交点。这是 O(n)。现在按每条边的角度及其与边界圆相交的角度位置的元组对每条边进行排序。这是 O(nlogn)，并且会将共线边分组到排序列表中。
如果你不太可能有很多平行但不共线的边缘，那么你可以跳过边界圆的事情，只按角度排序。如果有很多平行的非共线角度，那么仅使用角度仍然“有效”，它只是不会为您带来几乎同样多的效率提升。
Find a bounding circle. Compute the upper/right intersection between the bounding circle and the line each edge lies on. This is O(n). Now sort each edge by the tuple of its angle and the angular position of its intersection with the bounding circle. That's O(nlogn), and will group the collinear edges together in your sorted list.
If you're unlikely to have lots of parallel but non-collinear edges then you can skip the bounding circle thing and just sort by angle. If there are lots of parallel non-collinear angles then just using angle still "works", it just doesn't buy you nearly as much efficiency improvement.
你能找到 1-2 和 6-0 的交集吗？如果是这样，您可以生成边和顶点的图。然后，找到所有不重叠的多边形就很简单了。
Can you find the intersection of 1-2 and 6-0? If so, you can generate a graph of edges and vertices. Then, finding the all non-overlapping polygons is simple.