线段与凸多边形的交集

Question

寻找一个O(logn)算法来识别与扩展线段相交的凸多边形的线段。已知该线段完全位于凸多边形内部。
例如：
输入：ab /线段/，{1,2,3,4,5,6} /凸多边形沿逆时针顺序的顶点及其坐标/
输出：3-4,5-6 可以通过获取所有线段的方程并检查它们是否相交来完成此操作，但这将是O(n)，因为需要检查n条线段是否相交。我认为可以使用二分搜索(由于logn限制)来降低复杂度，但我不知道在什么上应用它。

- Sahil Sareen

---

我该在什么上应用二分查找？ - Sahil Sareen

我有一个想法，但是有一些边角案例需要考虑。我会尽力完整地定义这个想法，完成后再回复你。(简而言之，你可以使用三分查找来计算距离线的距离，但在某些情况下，这种方法可能会丢失解决方案) - yasen

一个重要的问题 - 你如何存储关于多边形的数据？ - Danstahr

任何数据结构都可以使用。该数据结构可以直接从输入中构建，输入以点（x，y）的形式给出。 - Sahil Sareen

定理3似乎也能解决动态多边形的问题。 - ile

Answer 1

首先，您需要使用有向多边形边缘并将它们存储在数组中（或者可能是另一个数据结构，允许直接访问时间复杂度不超过 O(logN)）。链表对于这个问题不好。

此外，您需要为扩展段分配方向-假设它从A到B定向。然后，它将平面分成两个半平面-左和右。您选择初始边缘（顶点为0和1），然后选择中间边缘（顶点为[n/2]-1和[n/2]）。有两种情况-初始边缘与扩展段相交或不相交。我将在此处考虑第一种情况，将第二种情况留给您。我还将假设初始边缘完全位于右半平面中（左平面的情况是对称的）。中间边缘将多边形分成两个边缘路径-我将称其为第一个路径（从0到[n/2]的顶点）和第二个路径（从[n/2]到0的顶点）。

中间边缘可以有五种情况：

1. 完全位于右半平面（与初始边缘相同），并且跟随初始边缘-然后您递归地分析第二个路径。
2. 完全位于右半平面（与初始边缘相同），并且在初始边缘之前-然后您递归地分析第一个路径。
3. 完全位于左半平面（不是初始边缘所在的那个）-那么您必须递归地分析两个路径。
4. 与从右半平面到左半平面的扩展段相交-找到一个交点，然后递归地分析第二个路径。
5. 与从左半平面到右半平面的扩展段相交-找到一个交点，然后递归地分析第一个路径。

因此-最“不方便”的情况是（2）-在这种情况下不能放弃任何路径，但看起来它无法重复整个多边形。

此外，您还需要计算有向多边形边缘之间的关系-“跟随/在...之前”。可以使用相对边缘角度来完成-“跟随”边缘必须相对于“在...之前”边缘向左转（由于凸性）。

- HEKTO

Answer 2

这个答案有些令人困惑，所以我想用另一种方式提供更多细节。

假设您的数据存储在数组P中，并且您正在检查线U。 p_0是最左下角的点。即p_0.x < p_i.x，并确保在平局的情况下p_0.y < p_i.y。 P按照大多数ConvexHulls的ccw进行排序。您还有p_m，其中m是半程点，即n/2首先。我们将L、M、H定义为二进制搜索索引，其中L= 0，M= n/2，H=n-1。我将编写递归，但您可以展开此操作。

基本情况：

"多边形"数组是否具有n<= 3个点。在这种情况下，只需检查三角形或直线中的每条线与U O(1)的交点。

递归步骤：

通过计算L_m = Line(p_0, p_m)与U的交点p_I来确定是否相交，时间复杂度为O(1)。如果p_I是NULL，我们知道U是从L_m的顺时针或逆时针方向，可以使用有向定向测试(Directed Orientation Test)在O(1)的时间内找到哪个方向是顺时针，如果是逆时针，则使用ConvexLineInt({p_0,p_m,...,p_h},U)进行递归；否则使用ConvexLineInt({p_0,p_l,...,p_m},U)。

如果p_I存在，它必须出现在线L_m中，即它在一个完全有序的集合中，并且我们检查以下情况：

L_m.0 <= p_I <= L_m.1 (在之间) => 返回“线相交”

p_I < L_m.0，即在多边形的左侧。我们计算p_U，它与L_0 = Line（p_0，p_l）相交，O（1）。如果p_U为NULL，则意味着线U在多边形外部。这意味着U是ccw到L_0。由于p_U存在，我们可以检查Orient（L_m，p_U）= w，这不能为0，因为有一个交点。如果w> 0，则交点是ccw，即U只能是ccw到L_m，我们可以像上面一样递归“右”集。否则，该点在下方，U只能是cw到L_m，在“左”集上递归。请注意，我们始终保留p_0，它是我们的枢轴点。

p_I > L_m.1应该是对称的，我将其留作练习。

由于每个检查都是O（1），而且我们将集合分成两个或更多，因此运行时间就是二分搜索的时间，即O（log n）。如果您想要正式一些，请使用主定理。

希望这对你有所帮助！ 方向测试：如何判断一个点在直线的左侧还是右侧
寻找两条直线的交点： https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection

- Luke Quinn