geometry - 如何检测多边形是否具有自相交？

Question

假设您有一个 2D 多边形(更准确地说是 2D closed polygonal chain)。你如何检查它是否包含自相交？它可以是凸面或凹面，顺时针或逆时针方向。

现在，我可以运行标准 O(N log N)检查任何两个段是否交叉的算法。但我相信，因为我们有一些额外的结构——段的顺序以及每两个连续段在端点相遇的事实——可以设计一个更简单和更快(也许 O(N) ？)的算法。

有任何想法吗？

Answer 1

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

如果你只需要查找自交是否存在，或者自相交的数量很少，那么查看here .本文似乎声称正是您所需要的，特别是在多边形平面化部分。我怀疑实现那里描述的算法对于任何合理规模的问题来说是否简单或值得。但是这样的算法确实存在。免责声明:我还没有尝试通读这篇论文并理解它。