如何检测多边形是否有自相交？
假设您有一个 2D 多边形（更准确地说，是一个 2D 闭合多边形链）。如何检查它是否包含自相交？它可以是凸面或凹面，顺时针或逆时针方向。
现在，我可以运行标准 O(N log N) 算法来检查是否有任何两个线段交叉。但我相信，因为我们有一些额外的结构——线段的顺序以及每两个连续线段在端点相交的事实——一个更简单、更快的算法（也许O(N)？）可以设计。
有什么想法吗？
Imagine you have a 2D polygon (a 2D closed polygonal chain to be more precise). How do you check if it contains self-intersections? It can be convex or concave, oriented clockwise or counter-clockwise.
Now, I could just run a standard O(N log N) algorithm to check if any two segments cross. But I believe that because we have some additional structure -- the order of the segments and the fact that each two consecutive segments meet at endpoints -- a simpler and faster (maybe O(N)?) algorithm could be devised.
Any ideas?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您是否只需要检查自交点，还是找到所有自交点？后者比
O(N log N)更难，因为您可以与n段有O(n^2)交集。如果您只需要找出是否存在自相交，或找到少量自相交，请查看此处。这篇论文似乎声称正是您所需要的，特别是在多边形平坦化部分。我怀疑实现其中描述的算法是否简单，或者对于任何合理规模的问题是否值得。但这样的算法确实存在。免责声明：我没有尝试通读并理解这篇论文。
Do you need just to check for self-intersections, or find all of them? The latter is harder than
O(N log N), as you can haveO(n^2)intersections withnsegments.If you only need to find out if self-intersections exist, or find a small amount of them, then look here. This paper seems to claim just what you need, particularly in the polygon planarization section. I doubt implementing the algorithm described there would be simple, or worthwhile for any problem of reasonable size. But such an algorithm does exist. Disclaimer: I haven't tried to work through the paper and understand it.