如何检测多边形是否存在自相交？

Question

8

假设你有一个二维多边形（更准确地说，是一个二维闭合折线）。如何检查它是否包含自相交？它可以是凸的或凹的，顺时针或逆时针方向。

现在，我可以运行标准的O(N log N)算法来检查任何两个线段是否相交。但是我相信，由于我们有一些额外的结构--线段的顺序和每两个连续的线段在端点处相遇--可以设计一个更简单、更快速（也许是O(N)？）的算法。

有什么想法吗？

- Jasiu

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- n. m. · Accepted Answer

你只需要检查自相交还是找到所有的自相交？后者比O(N log N)更难，因为你可以有n个线段和O(n^2)个交点。

如果你只需要找出是否存在自相交或者只需找到少量自相交，则可以看看这里。这篇论文似乎声称正好符合你的需要，特别是在多边形平面化部分。我怀疑实现那里描述的算法将不简单，对于任何合理大小的问题都不值得。但这样的算法确实存在。免责声明：我没有尝试阅读论文并理解它。