concept · sweep and prune

若干矩形里，哪些两两重叠？

游戏物理引擎每一帧都要回答：这一大批物体里，哪些对可能发生碰撞？两两逐一测试固然可行，但那是 $O(n^2)$ ——上千个物体就是上百万次测试。Sweep and Prune（也叫 sort & sweep）用一个极为朴素的观察把它降下来：先按左边界排好序，扫描线从左往右扫，某个矩形一旦 «左边» 越过了当前矩形的右边，由于已排序，它后面的全都不可能重叠——整批直接 break 剪除。

在画布里拖动矩形看重叠对实时更新（绿色交集块）。下面先用暴力法给出基准结果（一定正确），再点 Sweep and Prune 单步看扫描线如何推进、break 在哪一刻剪掉一整批——右下角对比两者的相交测试次数。

1 · 为什么排好序就能整批 break?

两个矩形要在 x 上重叠，必要条件是各自的 x 区间 [left, right] 有交集。把矩形按 left 升序排好后扫描：对当前矩形 cur，往右看的每个 other 都满足 $other.left \ge cur.left$ 。于是只要 $other.left \le cur.right$ ，就有 $cur.left \le other.left \le cur.right$ ——x 区间必然重叠，连判都不用判，只剩 y 要测。反过来，一旦某个 other.left > cur.right，由传递性（它之后的 left 只会更大）可知后面所有矩形在 x 上都触及不到 cur, break 掉一整批。

复杂度：排序 $O(n \log n)$ + 扫描时每个矩形只碰到 x 上和它邻近的常数个 → 总体 $O(n \log n + k)$ , k 是重叠（候选）对数。物体在 x 上分布越均匀，被 prune 掉的越多，越接近线性。看右下角：本例暴力 C(n,2) 次，sweep 只需寥寥数次。

2 · 单轴只是 broad-phase: x 接近 ≠ 真正碰撞

只按 x 扫，会漏判 y 吗？不会漏——真正重叠的对 x 一定重叠，必被扫到；但会多出「x 相邻、y 却相距甚远」的对（画布里橙色虚线那些）。所以单轴 sweep 是 broad-phase 粗筛：它快速排除绝大多数毫不相干的对，留下少量候选，再交给 narrow-phase 做精确求交（本页对候选一并测试了 y）。工程上常两个轴都投影各扫一遍、取候选对的交集，进一步减少误报。

时间相干性 (temporal coherence) 是 SAP 在物理引擎里高效的关键：每帧物体只移动一点点，上一帧排好的顺序几乎仍然有序。于是不必每帧重新 $O(n \log n)$ 排序，改用插入排序维护那个「基本有序」的端点列表，均摊接近 $O(n)$ ；端点相邻次序发生交换的那一刻，正好对应一对物体「开始/结束」在该轴重叠——增量地维护重叠集即可。

3 · 它用在哪里

物理引擎的 broad-phase:Box2D / Bullet 等都用 Sweep and Prune (SAP / sort-and-sweep) 做第一道粗筛，再对候选对跑 GJK / SAT 精确碰撞。2D 游戏的子弹命中、平台碰撞同理。它和本系列最近点对是同一种思路——先排序暴露出空间的 «邻近» 结构，再用一个几何不等式剪掉绝大多数无谓比较；也和分支限界用 bound 剪掉大片解空间一脉相承。broad-phase 也不止 SAP 一路——还有把场景按空间切块的四叉树 / 空间哈希 / BVH（见下文 用空间划分做 broad-phase 一节）, SAP 则胜在简单且充分利用时间相干性。

4 · 另一条路：用空间划分（四叉树）做 broad-phase

SAP 的思路是把碰撞问题压到一维：沿一个轴排序、扫描、用一个不等式整批剪枝。还有一大类 broad-phase 反其道而行——直接按物体在二维平面上的位置把空间切成块，只让同一块或相邻块里的物体两两去测。四叉树 (quadtree) 是其中最经典的一种。

怎么切？ 根节点是整个场景的方框。往里插入物体，当某个格子里的物体数超过容量阈值，就把它四等分成四个子格、物体随之下沉到所属子格；再超就再分，递归下去。于是物体密集处格子细、空旷处格子大（上图）。查询时（粗筛某物体的碰撞候选，或框选一片区域），从根往下走，只进入与目标包围盒相交的子格，空旷或不相交的整片区域直接略过——候选对数因此远少于暴力的 C(n,2)。

和 SAP 怎么选？ SAP 的软肋（一个超大物体撑宽扫描窗口、prune 失效而退化回 $O(n^2)$ ）恰是空间划分较从容之处。但四叉树自有代价：物体移动跨越格子边界时要在树里搬家，动态场景每帧都有重建 / 更新开销；横跨多个子格的物体，要么上挂到父节点、要么在多个叶子里各登记一份，处理不好会反噬性能；容量阈值与最大深度还需调参。实现更简单的均匀网格 / 空间哈希 (spatial hashing) 对疏密均匀的场景够用，但不如四叉树自适应;3D 里对应八叉树 (octree)，而动态刚体更常用 BVH。没有银弹，引擎按物体的数量、疏密、动静来选，甚至几种混用。

5 · 边界情形 / 工程要点

「重叠」是开区间还是闭区间：刚好边贴边 (cur.right === other.left) 算不算碰撞？本页按严格 < 处理（贴边不算），和大多数 broad-phase 一致——否则静止堆叠的物体会每帧都报一次碰撞。排序键的选择：用 left 端点排序最常见；物体大小悬殊时，一个超大矩形会让窗口很宽、prune 失效（退化回 $O(n^2)$ ），这也是 SAP 不适用于「大物体 + 大量小物体」场景的原因。插入排序维护时要留意端点的稳定次序，避免抖动反复触发增删。