暴力法的高牆，與一條移動的線
在第 1 篇指南裡，你學會用方向測試問兩條線段「它們相交嗎？」。現在把規模放大：給定 n 條線段，哪些對相交？最直白的方法測試每一對，共 n*(n-1)/2 次測試——無論只有一對相交還是百萬對相交，都是 Theta(n^2) 的功夫。對 10,000 條線段而言，這約莫是五千萬次方向測試，而隨著 n 增長，這數字還會暴漲。最令人痛心的是，其中有多少功夫明顯是白費的：平面左上角的一條線段，絕不可能碰到右下角的那條，暴力法卻仍盡職地把它們拿來比對。
掃描線的構想正是針對這份浪費。想像一條垂直線——稱它為掃描線——從遠遠的左邊出發，穩穩地向右滑過整幅圖。它一邊行進，一邊一刻接著一刻地掠過各個幾何物件。關鍵的洞見是：兩條線段只可能在掃描線同時碰到它們兩者的地方相交。所以你不必比對每一對天南地北的物件，而是永遠只比對掃描線目前正重疊到的物件。遠方的左上角與右下角線段從不同時在線上，因此從不被比對。整場較量，就是只看當下，絕不看無關的過去、也不看尚未抵達的未來。
兩個結構：事件佇列與狀態
每一次線掃描都由恰好兩個記帳結構組成，學會認出它們，這門技藝就掌握了大半。第一個是事件佇列：那些有趣時刻排好序的時間軸，依掃描線在各事件發生時所在的位置（通常按 x 座標）排序。對線段相交而言，事件是每條線段的左端點（它進入線的視野處）、右端點（它離開處），以及——邊做邊發現的——交點本身。第二個是狀態：一份小小的紀錄，準確記下掃描線此刻正碰到什麼，並以一種便於找出鄰居的順序維護。對線段而言，狀態存放著線目前切過的那些線段，按它們在線當前 x 處的高度由上而下排序。
為什麼是兩個結構而非一個？因為它們回答兩個不同的問題。事件佇列回答「接下來發生什麼、在哪裡？」——它推動時間前進。狀態回答「此刻誰與誰相鄰？」——它告訴你哪些對才值得做一次相交測試。深層的回報來自一個安靜的幾何事實：兩條會相交的線段，必定在交點前某個 x 處於狀態中成為垂直方向的鄰居——那一瞬間沒有別的線段擠在它們之間。所以你永遠不必測試一對目前在狀態中不相鄰的線段。一堆 n^2 的成對測試，就這樣坍縮成一條細細的鄰居測試之流。
一步步走過線段掃描
讓我們慢慢跑一遍 Bentley-Ottmann 線段相交掃描，把狀態當成一份按高度堆疊、排好序的線段清單。線向右移動，按 x 順序從佇列取出事件。每個事件都小而局部：它插入或移除一條線段，或回報一個交點，並且只重新檢查剛剛變成相鄰的那寥寥幾個鄰居。第 1 篇指南的方向測試，是每一個「這兩條真的相交嗎？」問題裡的主力；而掃描唯一的工作，就是讓它被呼叫的次數少得多。
- 左端點事件：一條新線段 s 進入。把 s 依其高度插入狀態的正確位置。只拿 s 對它緊鄰的上方與下方鄰居做測試——而非整個狀態。你和它們找到的任何交點，都被排入佇列成為未來的事件。
- 右端點事件：一條線段 s 離開。把 s 從狀態移除。它原先的上方與下方鄰居如今彼此相鄰，所以把這新形成的一對測試一次——它們可能在此處右方相交。
- 交點事件：兩條線段在此 x 處交換它們的上下次序。回報這個交點，在狀態中交換它們，再各自對其新的外側鄰居做測試——這次交換可能造出兩組全新的相鄰關係，它們可能在更右方相交。
推演一個小例子來體會它。兩條線段 A（緩緩上升）與 B（緩緩下降），在中間相交一次。線碰到 A 的左端，插入 A——沒有鄰居，無可測試。它碰到 B 的左端，把 B 插在 A 正下方，測試相鄰的一對 A、B，發現它們將相交；那個交點被排入佇列。線推進到該交點事件，回報它，並交換 A 與 B。它們沒有其他鄰居，所以不再排入任何事件。最後兩個右端抵達，線段離開。所做的交點測試總數：寥寥幾次，而非暴力掃描——在這 2 條線段的例子上勝果看不出來，但當成千上萬條線段散布在平面上時，同一套紀律使每條線段只與它當前的鄰居對話。
為何它快——以及誠實的附帶細則
誠實地把成本算清楚。有 n 條線段與 k 個實際交點時，有 2n 個端點事件與 k 個交點事件，所以佇列總共處理 O(n + k) 個事件。每個事件做常數次鄰居測試，但每個事件也要對狀態做插入、刪除或重新排序——而要讓這些操作便宜，狀態必須是一棵平衡搜尋樹，其中插入、刪除、找鄰居各花 O(log n)。事件佇列本身是個有序結構，每次操作花 O(log(n + k))。把事件數乘上每事件成本，你得到 O((n + k) log n) 的時間。把它和暴力法平板的 Theta(n^2) 相比：當 k 很小時——少有線段真正相交的常見情形——這快得驚人，本質上是線性對數而非平方。
現在是誠實的附帶細則，因為漸進描述的是規模的伸縮，而非在每個尺寸上的判決。第一，這份加速是輸出敏感的：它取決於 k。在病態的最壞情況裡每一對都相交，故 k = Theta(n^2)，掃描退化為 O(n^2 log n)——其實還比暴力法慢一個 log 因子，因為那整套樹的機械都有額外開銷。掃描在交點稀疏時取勝，這正是你必須了解自己輸入的原因。第二，那漂亮的 O((n+k) log n) 界假設一般位置——沒有兩個事件共用同一 x 座標、沒有三條線段交於一點、沒有垂直線段。真實資料三條全違反，而處理這些退化情形所需的破除平手規則，正是一個正確實作中真正惱人的部分，在程式碼長度上遠遠蓋過那個乾淨的構想。
一個範式，多種偽裝
掃描配得上範式這個堂皇字眼，原因在於同一副「事件佇列加狀態」的骨架，能解決看似毫不相干的問題。最近點對可用一次由左至右的掃描求得，其狀態存放著目前在線的最佳距離之內的那些點、按 y 排好序；每個新進來的點只需對常數個鄰近候選做檢查，得到 O(n log n)，與較早一篇指南的分治版本相當。注意狀態不再是「按高度排的線段」——骨架不變，內容隨問題而換。
區間問題也是偽裝過的掃描，只是發生在一維直線上。把區間端點排序，再讓一個點掃過它們；狀態不過是「目前有幾個區間開著」的一個計數器。那單一計數器就解決了區間劃分——同時最忙的房間數，就是那計數器的執行中最大值——並且因為讓「此刻有什麼重疊？」可瞬間回答，它撐起了經典的區間排程論證。連矩形聯集面積、重疊範圍的合併，也都是掃描，其中狀態概括了線目前切出的橫截面。不同的狀態，相同的心跳：推進到下一個事件、更新那份小小的概要、讀出答案。
退一步，你便能看出它與這一階其餘部分的家族相似。如同方向基本運算，掃描以一份有限、可判定的情形清單取代模糊的視覺推理。如同你剛認識的凸包掃描，它重重倚賴「先排序、再做單次有紀律的遍歷」。而這個教訓可推而廣之：每當一個問題的答案只在一組離散時刻改變、且只取決於一個小小的局部鄰域時，就問問你能否把那些時刻排成事件並加以掃描。那份直覺——把靜態的二維亂局，轉成一條移動的一維時間軸——才是你真正帶走的東西，遠比任何單一演算法的程式碼來得耐久。