扫描线求交（Bentley-Ottmann）
计算几何 · 事件驱动 · n 条线段求所有交点
从「两条」到「n 条」
线段相交一页用叉积回答了「两条线段交不交」。现在 n 条线段要找所有交点：两两全查是 O(n²)，可地图上千万条道路的交点远比 n² 稀疏——为「有几个交点就干几分活」，Bentley-Ottmann 给出 O((n + k) log n)（k 为交点数）。
一条扫描线，两个数据结构
想象一条竖直扫描线从左往右扫过平面。事件队列按 x 排序存三种事件：线段起点（入场）、终点（离场）、以及扫描中动态加入的交点事件。状态结构维护当前与扫描线相交的线段、按交点 y 有序。核心洞察：两条线段相交前，必先在状态结构中相邻——所以永远不用两两全查，只在插入/删除/交换时检查新相邻对，未来的交点丢回事件队列等着扫描线到达。
下面三条线段 A、B、C 有 3 个交点。点「下一步」看扫描线（紫虚线）逐事件右移：入场线段亮琥珀、交点事件亮绿并落下红标、离场变灰虚线；vars 里同步展示状态结构（下 → 上）与新入队的交点。右侧代码随每一步同步高亮。
3 条线段求所有交点。6 个端点事件按 x 排好队，一条竖直扫描线从左往右扫；交点事件在扫描中动态加入——两条线段相交前，必先在「状态结构」里相邻
1function bentleyOttmann(segs: Seg[]): Pt[] {
2 const events = new EventQueue(segs); // 端点按 x 排序入队
3 const status = new SweepStatus(); // 在场线段按 y 有序
4 const out: Pt[] = [];
5 while (!events.empty()) {
6 const e = events.pop(); // 最左事件
7 if (e.type === 'start') status.insert(e.seg);
8 else if (e.type === 'end') status.remove(e.seg);
9 else { out.push(e.pt); status.swap(e.s1, e.s2); } // 报告交点
10 for (const [u, v] of status.newAdjacent()) // 只查新相邻对
11 events.addCross(intersect(u, v)); // 未来交点入队
12 }
13 return out;
14}
线段A(1,1)-(9,9)、B(2,8)-(8,2)、C(2.5,6)-(8.5,6)
事件队列6 个端点事件（交点事件动态加入）
1 / 11
细节与应用
事件：起点入场 / 终点离场 / 交点报告 + 交换位置——三种都可能制造新相邻对。
不变量：状态结构始终 = 与扫描线相交的线段按 y 排序；交点事件按 x 先后被处理。
复杂度：每个事件一次 O(log n) 的队列/平衡树操作，共 2n + k 个事件 → O((n+k) log n)。
退化：竖直线段、三线共点、重合端点需要额外约定（本页固定实例规避）。
不变量：状态结构始终 = 与扫描线相交的线段按 y 排序；交点事件按 x 先后被处理。
复杂度：每个事件一次 O(log n) 的队列/平衡树操作，共 2n + k 个事件 → O((n+k) log n)。
退化：竖直线段、三线共点、重合端点需要额外约定（本页固定实例规避）。
这套「事件队列 + 扫描线状态」的范式在计算几何里随处可见：GIS 图层叠加、CAD 布线检查、地图多边形布尔运算（求并/求交），乃至矩形面积并、最近点对的扫描线版本——都是同一个骨架换不同的状态结构。