线段与凸多边形的相交

Question

寻找一个O(logn)算法来识别与扩展线段相交的凸多边形的线段。众所周知，直线段完全位于凸多边形内。

输入: ab /Line段/，{1,2,3,4,5,6} /Convex多边形顶点，其坐标/

产出: 3-4,5-6

​

​

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

Answer 1

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

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

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

1. 完全躺在右半平面(与初始边缘相同)，遵循(初始边缘)，然后递归分析第二条路径。
2. 完全位于右半平面(与初始边缘相同)，位于初始边缘之前，然后递归地分析第一条路径。
3. 完全位于左半平面(而不是初始边缘所在的那个平面)--然后您必须递归地分析和路径。
4. 将从右半平面到左半平面的扩展段相交，然后递归地分析第二条路径。
5. 将从左半平面到右半平面的扩展段相交，然后递归地分析第一条路径。

所以--最“不方便”的情况是(2) --在这种情况下，你不能丢弃任何路径，但是看起来整个多边形都不能重复。

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