渐进最优算法：计算一条直线是否与凸多边形相交。

Question

渐进最优算法：计算一条直线是否与凸多边形相交。

algorithmlinecomputational-geometryasymptotic-complexityconvex-polygon

22

一种检测直线与凸多边形是否相交的O(n)算法是检查多边形的任一边是否与直线相交，并查看相交点数是奇数还是偶数。

是否存在渐进更快的算法，例如O(log n)的算法？

- infinity_x

4个回答

2

边界框可能会很有用。

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

如果您预计交点数量较少，则所有这些都能更好地发挥作用。

- Alexandre C.

1

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

- Juraj Blaho

0

从凸多边形中随机选取两个点A和B。

如果它们在直线的不同侧，则相交
如果它们在同一侧，在多边形的两个部分（假设顺时针AB和BA）上执行以下操作：
- 创建一条与您的直线l平行的线，该线经过A
- 找到距离多边形上l最远的点，这与查找首先单调不降，然后单调不增的函数的最大值相同。可以通过三分搜索以O(log n)的时间复杂度完成此操作

如果这两个最远的点在您的直线的不同侧，则直线与多边形相交，否则不相交。

顺便说一句，您也可以在O(log n)的时间复杂度内找到实际的交点。

- Sarmun

距离应该不是绝对的（这样一侧为负，另一侧为正），或者对于一侧，l经过A和B。 - Sarmun

非绝对距离可以帮助解决问题，但并非所有情况都适用。请参见http://jurajblaho.wz.cz/path2816.png。按照顺时针顺序的A->B对于三分搜索无效，因为它是先增加，然后减少，最后再增加。 - Juraj Blaho

@在你的直线l旁创建一条通过点A的平行线：如果点B在该线上，则此算法失败... - user500074

@pouncep：不，那不是问题。 - Juraj Blaho

我不明白为什么这会被踩。当然，极端距离到L搜索算法必须得修复，但我觉得这个想法很棒。 - Alexandre C.

显示剩余2条评论

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

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

- Chris Hopman · Accepted Answer

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))相交的一侧背离，我们知道在那一侧不能与多边形相交。 情况2.3：交点更靠近v(n/2) 此情况类似于情况2.2，但使用v(n/2)的相应邻居进行处理。

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