掃描線範式（line-sweep paradigm）

想像一條垂直線，你把它從左拖到右掃過整個平面，恰好經過每個點、每個形狀一次。你不再一開始就比較所有物件對，而是依掃描線抵達的順序處理物件，且只比較此刻在掃描線附近的東西。這套由左到右的紀律就是掃描線範式：把靜態的二維問題化為一連串依序處理的一維事件，只維護一個由掃描線目前碰到的物件組成的小型活躍集合。

讓它運作的有兩個要素。第一，排好序的事件排程：發生有趣事情的 x 座標（抵達某點、某線段開始或結束）。你依 x 遞增處理事件。第二，一個活躍結構（常是平衡搜尋樹，或就是一個有序集合），存放目前被掃描線切到的物件，依其 y 座標排序，使結構中的相鄰者在垂直方向也相鄰。關鍵洞見是：你在意的互動——最近點對、兩線段的交點——只可能發生在沿掃描線相鄰的物件之間，所以你永遠不需測試相隔很遠的物件。對最近點對，你由左掃到右，把落在目前最佳距離 d 內的點維護在一個依 y 排序的集合中，對每個新點只與一個 d 高視窗內的少數幾個點比較——整體給出 O(n log n)。對線段相交，交叉只可能發生在 y 序中相鄰的線段之間，所以線段進入、離開、交換次序時只檢查相鄰者，便能以 O((n + k) log n) 找出全部 k 個交點。

掃描線之所以重要，是因為它系統性地把 O(n^2) 的全配對比較砍到 O(n log n) 或 O((n+k) log n)，靠的是利用局部性：只有鄰近的東西才會互動，而掃描把鄰近的東西組織好。它是計算幾何乃至更廣領域中最可重複使用的設計概念之一，出現在最近點對、線段相交（Bentley-Ottmann）、矩形聯集面積與區間問題。誠實的代價是簿記：你必須謹慎維護事件佇列與活躍結構，且退化情形（垂直線段、x 平手、同一座標多個事件）需要刻意的平手處理，否則掃描會把事件排錯序。