线段交点检测扫描线算法
几何对象的相交检测是计算几何中的一项基本操作。它具有广泛的应用，其中一些列在下面：
- 计算机游戏和模拟中的碰撞检测。
- 计算机图形学中的射线射击。
- 地理信息系统 (GIS) 中的地图叠加。
- 机器人导航中的防撞。
问题陈述：给定平面中 𝑛 条线段的集合 𝑆 = { 𝑠1, 𝑠2, …, 𝑠𝑛}，报告所有交点：
1、朴素算法：检查所有线段对
𝑛 线段的交点数范围从零（没有一对线相交）到 𝑂(𝑛^2）（所有对相交）。
简单的朴素方法检查所有线段对之间的交点。由于所有线段对都可能相交，因此朴素算法对于最坏情况的输入是最佳的，时间复杂度为 𝑂(𝑛^2)。
对于输出大小变化的问题，输出敏感算法是首选，因为它们的时间复杂度取决于问题大小和输出大小。对于具有 𝑛 线段的线段相交问题的实例，让 𝑘 表示交点数。
现在我们将讨论用于线段相交检测的 𝑂((𝑛+𝑘)𝑙𝑜𝑔(𝑛)) 扫描线算法。对于二维平面中的各种几何问题，扫描线算法是一种基本且有效的方法。这些算法涉及系统地扫描平面上的垂直线或水平线，以处理和分析几何对象，例如线段、点或其他几何实体。
2、一般位置假设
在解决几何问题时，可以方便地忽略几何输入的某些特殊配置，以保持算法简单。这些特殊情况是单独处理的。当它们被忽略时，问题的输入被视为处于一般位置，一般位置假设定义了重合配置。
对于线段相交问题，忽略以下特殊配置：
- 没有三条线在同一点相交。
- 没有端点位于另一个线段上。
- 端点和交点的𝑥坐标是唯一的。
3、扫描线算法
垂直扫描线从左到右扫描输入。扫描线与线段的交点用于发现即将发生的交点。
3.1 扫描线状态和事件点
设 𝑙 表示垂直扫描线。与扫描线 𝑙 相交的线段按从上到下的顺序存储。这称为扫描线状态。
我们注意到，只有当扫描线遇到输入中的某些特殊点时，扫描线状态才会发生变化。这些点称为事件点，下面列出了它们以及它们在扫描线状态中触发的变化。
- 线段𝑠的左端点：在正确的位置添加线段𝑠。
- 线段𝑠的右端点：删除线段𝑠。
- 一对线段𝑠和𝑟的交点：交换𝑠和𝑟的顺序。
由于扫描线状态仅在事件点处发生变化，因此扫描线可以从一个事件点跳转到下一个事件点，而不是连续扫描平面。
为了保证𝑂((𝑛+𝑘)𝑙𝑜𝑔(𝑛))的时间复杂度，扫描线状态和事件点存储在支持𝑂(𝑙𝑜𝑔𝑛)操作的数据结构中。
3.2 数据结构
扫描线状态是与扫描线相交的线段的从上到下的有序列表，存储在有序字典中。事件点存储在优先级队列中。这些数据结构中的每一个都支持以下操作。
扫描线状态的有序字典
𝑂(𝑙𝑜𝑔 𝑛) 中的有序字典支持以下操作：
- 插入线段
- 删除线段
- 获取前任
- 获取后继
- 交换两个线段
事件点的优先级队列
𝑂(𝑙𝑜𝑔 𝑛) 中的事件队列支持以下操作：
- 插入事件点
- 删除事件点
- 提取优先级最高的事件点
3.3 算法与案例分析
扫描线算法以一个空的事件队列和一个空的有序字典开始。开始时，所有线段的端点都插入到事件队列中。在事件队列中，具有最低𝑥坐标的点具有最高优先级，表示扫描线从左向右移动。在算法过程中，交点会动态添加到事件队列中并从中删除。
请注意，任何两个相交的线段在相交之前在扫描线上相邻。因此，该算法仅将相邻线段之间的交点插入事件队列，将不相邻线段之间的交点的发现推迟到后期。
当新的线段插入优先级队列时，算法会检查其与前一个和后一个线段的交点，而不是检查其与扫描线上所有 𝑂(𝑛) 个线段的交点。这确保了处理每个事件点所花费的时间是 𝑂(𝑙𝑜𝑔 𝑛)。
接下来，我们来看看三种事件点的扫描线状态和事件队列是如何变化的。在接下来的三幅图中，虚线灰色线是扫描线。
线段𝑠的左端点
发现左端点标志着发现了一条新的线段，从而触发了扫描线状态和事件点的以下变化：
- 在扫描线上插入𝑠。让𝑞和𝑡成为扫描线上𝑠上方和下方的线段。
- 从事件队列中删除𝑞和𝑡之间的交点（如果适用），如下图所示为红色圆圈，因为它们不再相邻。
- 检查𝑞,𝑠和𝑠,𝑡对之间的交点，如果线段相交，则将它们添加到事件队列中。
线段 𝑠 的右端点
右端点的发现会触发扫描线状态和事件点的以下变化：
- 让 𝑞 和 𝑡 成为扫描线上 𝑠 上方和下方的线段。
- 从扫描线状态中移除 𝑠。
- 检查 𝑞 和 𝑡 之间的交点，如果交点存在于扫描线的右侧，则将其添加到事件队列中。
请注意，𝑞、𝑠 或 𝑠、𝑡 对之间的可能交点位于过去，并且已被算法发现。
线段𝑠和𝑟的交点
发现交点后，将其添加到解决方案中，并对扫描线状态和事件点进行以下更改：
- 让𝑞成为𝑟的前任，𝑡成为𝑠在扫描线上的后继。
- 交换扫描线上的线段𝑟和𝑠。
- 从事件队列中删除对𝑞，𝑟和𝑠，𝑡（如果适用）之间的交点，如下图红色圆圈所示，因为这些对不再相邻。
- 检查对𝑞，𝑠和𝑟，𝑡之间的交点，如果它们存在于扫描线的右侧，则将它们添加到事件队列中。
概括来说，检查扫描线上任何一对相邻的线段的交点，并将交点添加到事件队列中。任何一对不再相邻的线段的交点将从事件队列中删除。
4、复杂度分析
对于具有𝑛线段和𝑘交点的输入，算法需要处理的事件有2𝑛+𝑘=𝑂(𝑛+𝑘)个。每个事件需要𝑂(𝑙𝑜𝑔 𝑛)时间来更新数据结构。因此，扫描线算法的时间复杂度为𝑂((𝑛+𝑘)𝑙𝑜𝑔 𝑛) 。
原文链接：Line segment intersection detection using sweep line algorithm
BimAnt翻译整理，转载请标明出处