线段与凸多边形的交点

Question

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

这可以通过获取所有线的方程并检查它们是否相交来完成，但这将是 O(n)，因为需要检查 n 条线是否相交。我认为应该可以使用二进制搜索（因为 logn 绑定）来降低复杂性，但我无法理解应用它的内容。

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

此外，您还必须计算定向多边形边之间的关系 - “跟随/领先”。可以使用相对边缘角度来完成 - “后续”边缘必须相对于“前一个”边缘向左转动（由于凸性）。