21

检测一条线是否与凸多边形相交的 O(n) 算法包括检查多边形的任何边缘是否与该线相交，并查看相交的数量是奇数还是偶数。

是否有渐近更快的算法，例如 O(log n) 算法？

4

5 回答 5

19

lhf 的答案接近正确。这是一个可以解决他的问题的版本。

让多边形按逆时针顺序有顶点 v0, v1, ..., vn。让点 x0 和 x1 在直线上。

注意两件事：首先，找到两条线的交点（并确定它的存在）可以在恒定时间内完成。其次，确定一个点是在一条线的左边还是右边可以在恒定时间内完成。

我们将遵循 lhf 的相同基本思想来获得 O(log n) 算法。基本情况是多边形有 2 个或 3 个顶点。这些都可以在恒定时间内处理。

确定直线 (v0,v(n/2)) 是否与直线 (x0,x1) 相交。

情况1：它们不相交。

在这种情况下，我们感兴趣的线位于分割多边形的线的左侧或右侧，因此我们可以递归到多边形的那一半。具体来说，如果 x0 在 (v0,v(n/2)) 的左侧，则右侧“一半”中的所有顶点 {v0, v1, ... v(n/2)} 都在同一侧（x0，x1），所以我们知道多边形的“一半”没有交集。

案例2：它们确实相交。

这种情况有点棘手，但我们仍然可以在恒定时间内将交叉点缩小到多边形的“一半”。有3个子情况：

案例 2.1：交点在点 v0 和 v(n/2) 之间

我们完了。该线与多边形相交。

案例2.2：交点更靠近v0（即在v0一侧的多边形之外）

确定线 (x0,x1) 是否与线 (v0,v1) 相交。

如果没有，那么我们就完成了，这条线不与多边形相交。

如果是，请找到交叉点，p。如果 p 位于线 (v0, v(n/2)) 的右侧，则递归到多边形的右“一半”，{v0, v1, ..., v(n/2)}，否则递归向左“一半”{v0, v(n/2), ... vn}。

这种情况下的基本思想是多边形中的所有点都在线的一侧（v0，v1）。如果 (x0, x1) 在与 (v0, v(n/2)) 相交的一侧偏离 (v0, v1)。我们知道在那一侧不能与多边形相交。

案例 2.3：交点更接近 v(n/2)

这种情况的处理与案例 2.2 类似，但使用了 v(n/2) 的适当邻居。

我们完了。对于每个级别，这需要两个线交叉点、左右检查并确定点在线上的位置。每次递归将顶点数除以 2（技术上至少将它们除以 4/3）。所以我们得到了 O(log n) 的运行时间。

于 2010-12-22T08:22:29.210 回答
3

我认为这篇文章给出了一个明确的 O(log n) 解决方案。在垂直于给定线的方向上找到极值。

于 2011-04-26T09:14:35.783 回答
2

边界框可能被证明是有用的。

回想一下，仿射空间的凸部分是其所有包络超平面的交集：您可以通过仅考虑包络超平面子集的交集来获得多边形的近似值（阅读“边界凸多边形”），测试将您的线与此近似值相交，并在必要时进行细化。

如果您预计交叉路口数量较少，所有这些都会更好。

于 2010-12-21T10:04:39.030 回答
1

您只需要找到在线左侧的点 A 和右侧的另一个点。剩下的问题是如何快速找到这些点。

于 2010-12-21T13:45:29.020 回答
0

从凸 poligon 中随机取两个点 A 和 B。

  • 如果它们在线的不同侧，它们相交
  • 如果它们在同一侧，则在两个 poligon 部分（假设顺时针 AB 和 BA）执行：
    • 创建一条平行于通过 A 的线 l 的线
    • 在 poligon 上找到离 l 最大距离的点，这与在函数中找到最大值相同，首先是单调非递减，然后是单调非递增。这可以通过三元搜索在 O(log n) 中完成


如果这两个最远的点在您的线的不同侧，则线与 poligon 相交，否则不会

顺便说一句，您也可以在 O(log n) 中找到实际的交点。

于 2010-12-21T19:24:06.017 回答