线段交点检测扫描线算法

几何对象的相交检测是计算几何中的一项基本操作。它具有广泛的应用,其中一些列在下面:

  • 计算机游戏和模拟中的碰撞检测。
  • 计算机图形学中的射线射击。
  • 地理信息系统 (GIS) 中的地图叠加。
  • 机器人导航中的防撞。
问题陈述:给定平面中 𝑛 条线段的集合 𝑆 = { 𝑠1, 𝑠2, …, 𝑠𝑛},报告所有交点:
七条线段求交问题实例

1、朴素算法:检查所有线段对

𝑛 线段的交点数范围从零(没有一对线相交)到 𝑂(𝑛^2)(所有对相交)。

简单的朴素方法检查所有线段对之间的交点。由于所有线段对都可能相交,因此朴素算法对于最坏情况的输入是最佳的,时间复杂度为 𝑂(𝑛^2)。

对于输出大小变化的问题,输出敏感算法是首选,因为它们的时间复杂度取决于问题大小和输出大小。对于具有 𝑛 线段的线段相交问题的实例,让 𝑘 表示交点数。

现在我们将讨论用于线段相交检测的 𝑂((𝑛+𝑘)𝑙𝑜𝑔(𝑛)) 扫描线算法。对于二维平面中的各种几何问题,扫描线算法是一种基本且有效的方法。这些算法涉及系统地扫描平面上的垂直线或水平线,以处理和分析几何对象,例如线段、点或其他几何实体。

2、一般位置假设

在解决几何问题时,可以方便地忽略几何输入的某些特殊配置,以保持算法简单。这些特殊情况是单独处理的。当它们被忽略时,问题的输入被视为处于一般位置,一般位置假设定义了重合配置。

对于线段相交问题,忽略以下特殊配置:

  • 没有三条线在同一点相交。
  • 没有端点位于另一个线段上。
  • 端点和交点的𝑥坐标是唯一的。
一般位置假设忽略的配置

3、扫描线算法

垂直扫描线从左到右扫描输入。扫描线与线段的交点用于发现即将发生的交点。

3.1 扫描线状态和事件点

设 𝑙 表示垂直扫描线。与扫描线 𝑙 相交的线段按从上到下的顺序存储。这称为扫描线状态。

扫描线 l 与四条线段相交

我们注意到,只有当扫描线遇到输入中的某些特殊点时,扫描线状态才会发生变化。这些点称为事件点,下面列出了它们以及它们在扫描线状态中触发的变化。

  • 线段𝑠的左端点:在正确的位置添加线段𝑠。
  • 线段𝑠的右端点:删除线段𝑠。
  • 一对线段𝑠和𝑟的交点:交换𝑠和𝑟的顺序。

由于扫描线状态仅在事件点处发生变化,因此扫描线可以从一个事件点跳转到下一个事件点,而不是连续扫描平面。

为了保证𝑂((𝑛+𝑘)𝑙𝑜𝑔(𝑛))的时间复杂度,扫描线状态和事件点存储在支持𝑂(𝑙𝑜𝑔𝑛)操作的数据结构中。

3.2 数据结构

扫描线状态是与扫描线相交的线段的从上到下的有序列表,存储在有序字典中。事件点存储在优先级队列中。这些数据结构中的每一个都支持以下操作。

扫描线状态的有序字典

𝑂(𝑙𝑜𝑔 𝑛) 中的有序字典支持以下操作:

  • 插入线段
  • 删除线段
  • 获取前任
  • 获取后继
  • 交换两个线段
事件点的优先级队列

𝑂(𝑙𝑜𝑔 𝑛) 中的事件队列支持以下操作:

  • 插入事件点
  • 删除事件点
  • 提取优先级最高的事件点

3.3 算法与案例分析

扫描线算法以一个空的事件队列和一个空的有序字典开始。开始时,所有线段的端点都插入到事件队列中。在事件队列中,具有最低𝑥坐标的点具有最高优先级,表示扫描线从左向右移动。在算法过程中,交点会动态添加到事件队列中并从中删除。

请注意,任何两个相交的线段在相交之前在扫描线上相邻。因此,该算法仅将相邻线段之间的交点插入事件队列,将不相邻线段之间的交点的发现推迟到后期。

当新的线段插入优先级队列时,算法会检查其与前一个和后一个线段的交点,而不是检查其与扫描线上所有 𝑂(𝑛) 个线段的交点。这确保了处理每个事件点所花费的时间是 𝑂(𝑙𝑜𝑔 𝑛)。

接下来,我们来看看三种事件点的扫描线状态和事件队列是如何变化的。在接下来的三幅图中,虚线灰色线是扫描线。

线段𝑠的左端点

发现左端点标志着发现了一条新的线段,从而触发了扫描线状态和事件点的以下变化:

  • 在扫描线上插入𝑠。让𝑞和𝑡成为扫描线上𝑠上方和下方的线段。
  • 从事件队列中删除𝑞和𝑡之间的交点(如果适用),如下图所示为红色圆圈,因为它们不再相邻。
  • 检查𝑞,𝑠和𝑠,𝑡对之间的交点,如果线段相交,则将它们添加到事件队列中。
扫描线 l 发现线段 s 的左端点
线段 𝑠 的右端点

右端点的发现会触发扫描线状态和事件点的以下变化:

  • 让 𝑞 和 𝑡 成为扫描线上 𝑠 上方和下方的线段。
  • 从扫描线状态中移除 𝑠。
  • 检查 𝑞 和 𝑡 之间的交点,如果交点存在于扫描线的右侧,则将其添加到事件队列中。

请注意,𝑞、𝑠 或 𝑠、𝑡 对之间的可能交点位于过去,并且已被算法发现。

扫描线 l 发现线段 s 的右端点
线段𝑠和𝑟的交点

发现交点后,将其添加到解决方案中,并对扫描线状态和事件点进行以下更改:

  • 让𝑞成为𝑟的前任,𝑡成为𝑠在扫描线上的后继。
  • 交换扫描线上的线段𝑟和𝑠。
  • 从事件队列中删除对𝑞,𝑟和𝑠,𝑡(如果适用)之间的交点,如下图红色圆圈所示,因为这些对不再相邻。
  • 检查对𝑞,𝑠和𝑟,𝑡之间的交点,如果它们存在于扫描线的右侧,则将它们添加到事件队列中。
扫描线 l 发现线段 s 和 r 的交点

概括来说,检查扫描线上任何一对相邻的线段的交点,并将交点添加到事件队列中。任何一对不再相邻的线段的交点将从事件队列中删除。

4、复杂度分析

对于具有𝑛线段和𝑘交点的输入,算法需要处理的事件有2𝑛+𝑘=𝑂(𝑛+𝑘)个。每个事件需要𝑂(𝑙𝑜𝑔 𝑛)时间来更新数据结构。因此,扫描线算法的时间复杂度为𝑂((𝑛+𝑘)𝑙𝑜𝑔 𝑛) 。


原文链接:Line segment intersection detection using sweep line algorithm

BimAnt翻译整理,转载请标明出处