Jas*_*siu 6 geometry computational-geometry
想象一下,您有一个2D多边形(2D 闭合多边形链更精确).你如何检查它是否包含自交叉？它可以是凸形或凹形,顺时针或逆时针方向.
现在,我可以运行一个标准O(N log N)算法来检查是否有任何两个段交叉.但我相信,因为我们有一些额外的结构 - 分段的顺序以及每两个连续分段在端点处相遇的事实 - O(N)可以设计出更简单,更快(可能是？)的算法.
O(N log N)
O(N)
有任何想法吗？
n. *_* m. 3
您是否只需要检查自交点，还是找到所有自交点？后者比 更难O(N log N)，因为您可以O(n^2)与线段有交集n。
O(n^2)
n
如果您只需要找出是否存在自相交，或找到少量自相交，请查看此处。这篇论文似乎声称正是您所需要的，特别是在多边形平坦化部分。我怀疑实现那里描述的算法对于任何合理规模的问题来说是否简单或值得。但这样的算法确实存在。免责声明：我没有尝试通读并理解这篇论文。
归档时间：
14 年，5 月 前
查看次数：
1990 次
最近记录：