计算几何中的平面扫描算法 好的，我们开始。平面扫描算法是计算几何中一类极为重要的 算法范式 。我会从它的核心思想出发，逐步讲解其工作原理、关键组件、经典应用，并最终总结其特点。 第一步：核心思想与直觉比喻 想象一下，你要数清一片草场上散落的石子数量。一种笨办法是，你走到每一颗石子旁边去标记。而一个更系统的方法是：你从草场的最左边开始， 竖直地 拉起一根看不见的线，从 左到右 匀速扫过整个草场。你的眼睛（或者一个记录仪）始终关注着这条“扫描线”附近的区域。每当扫描线碰到一颗新的石子，你就把它记下来；当扫描线离开某颗石子，你知道它已经被处理过了。 平面扫描算法的思想精髓就在于此 ： 将复杂的二维（或多维）空间中的几何问题，转化为沿着一个方向（通常是x轴）推进的一维“时间”序列问题。通过在“当前时刻”（即扫描线的当前位置）维护一个动态的数据结构（代表与扫描线相交的几何对象的状态），并精心处理“事件点”（如对象的起点、终点、交点），从而高效地解决问题。 它的核心是 降维 ：将一个静态的二维问题，转化为一个动态的一维问题。 第二步：算法的基本框架与关键组件 一个标准的平面扫描算法包含以下几个核心部分： 扫描线 ： 这通常是一条假想的、平行于y轴的直线，其方程为 x = s ，其中 s 是 扫描位置 。 扫描线从左（ x = -∞ ）向右（ x = +∞ ）匀速移动。在实际算法中，我们并不模拟连续移动，而是 离散地 跳转到下一个关键位置。 事件点调度器 ： 这是一个优先队列（通常是最小堆），用于存储所有已知的、需要扫描线停下来处理的关键x坐标。 初始事件点 通常是所有输入几何对象的端点（如线段的左端点、右端点）。 在算法运行过程中，可能会 动态插入 新发现的事件点（例如，检测到两条线段即将相交，则插入其交点的x坐标）。 状态结构 ： 这是一个动态数据结构，用于维护 当前扫描线与所有相关几何对象的交点的有序序列 。 由于扫描线是垂直的，这个顺序通常是交点的y坐标顺序。 常用的数据结构是 平衡二叉搜索树 （如红黑树、AVL树），因为它需要高效地支持 插入 、 删除 、 查找前驱 和 查找后继 操作。 状态结构反映了在当前位置“扫描线看到了什么”。 第三步：算法流程的细化 让我们将上述组件串联起来，描述算法的主循环： 初始化 ： 将所有输入对象的 端点 （例如，线段的左右端点，取x坐标较小的为左端点）作为初始事件点插入事件调度器。 初始化状态结构为空。 主循环 ： 当 事件调度器非空时： a. 取事件 ：从调度器中取出下一个x坐标最小的事件点 p 。 b. 处理事件 ：将扫描线“快速移动”到 x = p.x 的位置。根据事件点 p 的类型，更新状态结构： * 左端点事件 ：将对应的几何对象 插入 状态结构。插入后，需要检查它与其在状态结构中的 上邻 和 下邻 对象在当前位置之后是否可能相交。如果会相交，则将 有效的 交点作为新事件点插入调度器。 * 右端点事件 ：将对应的几何对象 从 状态结构中 删除 。删除后，原来与该对象相邻的两个对象现在变成了邻居。需要检查这两个 新邻居 在当前位置之后是否可能相交，并可能插入交点事件。 * 交点事件 ：在交点 p 处，两条线段相交，意味着它们在状态结构中的 顺序发生了交换 。因此，需要交换这两条线段在状态结构中的位置。交换后，与它们形成的新邻居（原来不相邻的线段变成了相邻）也需要进行相交性检查，并可能插入新的交点事件。 c. 报告/记录 ：根据问题需要，可能在此时进行记录（例如，记录下交点 p ）。 终止 ：当事件调度器为空时，算法结束，扫描完成。 第四步：经典应用实例——线段求交 我们以“寻找平面内一组线段的所有交点”为例，具体化上述流程。 输入 ：平面上 n 条线段。 目标 ：高效找出所有交点（假设交点数量为 k ）。 暴力法 复杂度：O(n²)，检查每对线段。 平面扫描算法 （Bentley-Ottmann算法）可达到 O((n+k) log n) 的时间复杂度，这在 k 远小于n²时优势巨大。 如何运作 ： 事件点：线段端点和已发现的线段交点。 状态结构：按当前扫描线位置，与扫描线相交的线段，按其交点的y坐标排序。 关键操作： 当扫描线遇到一条线段的 左端点 ，将该线段加入状态树。新线段会与它在树中的上下邻居线段“相邻”。 仅相邻的线段才有可能在当前位置右侧首次相交 。因此，只需检查新线段与它的新邻居是否相交，若相交且交点在扫描线右侧，则将该交点加入事件队列。 当扫描线遇到一条线段的 右端点 ，将该线段从状态树中删除。它的删除会使其原来的上下邻居变成彼此的新邻居。因此，需要检查这一对新邻居是否相交。 当扫描线遇到一个 交点 ，在状态树中交换相交的两条线段的位置。交换后，它们各自有了新的邻居，同样需要检查这些新邻居对是否相交。 这个算法的精妙之处 在于，它通过维护“当前扫描线的交点序”，将全局的相交检查，局部化为只检查状态结构中 相邻的线段对 ，极大地减少了不必要的检查。 第五步：总结与扩展 平面扫描算法的特点 ： 优点 ：将高维问题化为一维序列处理，思路清晰，能高效解决许多经典几何问题。 核心数据结构 ：事件队列（优先队列） + 状态结构（平衡二叉搜索树）。 复杂度关键 ：事件总数（O(n+k)）乘以每个事件处理成本（对状态结构的O(log n)操作）。 其他经典应用 ： 计算矩形面积并 ：事件点是矩形的左右边；状态树维护当前被扫描线覆盖的y区间总长度。 寻找最近点对 （在一维排序后，结合扫描线思想）。 多边形布尔运算 （如并、交、差）。 可见性计算 。 注意事项 ： 实现时需要小心处理 特殊情况 ，如垂直线段（可视为左、右端点x坐标相同）、多条线段交于一点、线段端点重合等，这涉及到事件点的排序规则和状态树的比较器设计。 原始的Bentley-Ottmann算法假设没有两条线段重叠，且最多两条线段交于一点。处理更一般的情况需要更复杂的逻辑。 总而言之，平面扫描算法是计算几何工具箱中一把强大而优雅的瑞士军刀，它通过引入“时间”维度，将空间中的静态关系转化为动态过程中的有序事件流，从而系统、高效地揭示几何对象之间的复杂关系。