algorithm - 线段与凸多边形的交集

Question

寻找 O(logn) 算法来识别与延长线段相交的凸多边形线段。可以确定线段完全位于凸多边形内。
例子:输入:ab/线段/, {1,2,3,4,5,6}/CCW 顺序的凸多边形顶点及其坐标/
输出:3-4,5-6

这可以通过获取所有直线的方程式并检查它们是否相交来完成，但这将是 O(n)，因为需要检查 n 条直线是否相交。我认为应该可以使用二进制搜索(因为 logn 绑定(bind)) 来降低复杂性，但我不明白如何应用它。

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) - 在这种情况下你不能删除任何路径，但看起来它不能对整个多边形重复。

此外，您还必须计算定向多边形边之间的关系 - “跟随/先行”。这可以使用相对边缘角度来完成 - “后续”边缘必须相对于“先前”边缘转向左侧(因为凸性)。