橡皮筋知道什麼
在一塊木板上釘下幾根釘子，套上橡皮筋把它們全圍起來，再鬆手。它會卡在最外圍的釘子上、形成一個繃緊的多邊形；其餘每根釘子都落在裡面。那個多邊形就是這些點的凸包——包含它們的最小凸區域，這裡「凸」的意思是：任取裡面兩點，它們之間的直線段都留在裡面，不准有凹陷。凸包是計算幾何的標準第一道題，因為它是「資料住在哪」的形狀：一團點雲的空間範圍、機器人不可越過的輪廓、你拉防水布要繞的邊界。
這裡有一個與上一篇相連的關鍵觀察。沿著那條繃緊的橡皮筋逆時針走一圈。在它碰到的每根釘子上，橡皮筋都只朝同一個方向彎：向左。它從不右轉、也從不原路折返，因為右轉意味著凹陷，而凹陷正是繃緊的橡皮筋不可能有的。於是「這個形狀是不是凸包？」就化成一連串的方向測試——就是你學會判讀為左轉、右轉或共線的那個外積符號。凸包正是那個「每三個連續頂點都構成左轉」的多邊形。這個單一事實，就是底下每個演算法的引擎。
Andrew 單調鏈：先排序，再掃兩遍
最適合先學的凸包演算法是 Andrew 單調鏈。它分兩半建出凸包。首先把所有點依 x 座標排序（x 相同時看 y）。接著由左掃到右建出下凸包，再由右掃到左建出上凸包，並在最左與最右的點處把兩者黏起來。每一半都用同一條小小的堆疊規則建成，所以你懂了一半就懂了兩半。畫面是這樣：下鏈從底下托住這些點，上鏈從上方蓋住它們，兩者合起來就把一切包住。
堆疊規則就是全部的訣竅。維護一個目前凸包頂點的串列（當堆疊用）。要加入下一個點 p 時：當串列至少有兩個點、且它最後兩個點連同 p 並未構成左轉時，就把最後一個點彈出；然後壓入 p。「不是左轉」表示對頂端兩點與 p 做方向測試得到右轉或共線——一個凹陷或一個多餘的平直點——所以前一個頂點不可能在凸包上、應被丟棄。你正在抹去：橡皮筋繃過 p 而收緊時會抬離的每一根釘子。兩遍掃描後，串接起來的兩條鏈就是逆時針順序的凸包。
build_lower(points sorted by x):
hull = []
for p in points: # left to right
while len(hull) >= 2 and
orient(hull[-2], hull[-1], p) <= 0: # not a left turn
hull.pop() # drop the dent / flat point
hull.append(p)
return hull # upper hull: same loop over points REVERSED為何它花費 O(n log n)，以及為何每個點只被碰兩次
把成本拆成兩塊看。排序花 O(n log n)——這是主導項，而且就是你早已信得過的那個排序。兩遍掃描因為內層那個會彈出的 while 迴圈，看起來可能是平方級，但其實不是：它們合計只跑 O(n)。理由是一個經典的記帳論證。在整趟掃描中，每個點恰好被壓入堆疊一次。一次彈出只能移除先前被壓入過的點，所以整趟掃描的彈出總次數絕不可能超過壓入總次數、也就是 n。內層迴圈不是「每個點 n 次功夫」——而是「n 次彈出由所有點分攤」。
所以每個點進堆疊一次、最多離開一次：它被碰觸的次數是常數，掃描花 O(n)，整個演算法是 O(n log n)，完全由排序主導。這正是資料結構那條梯子上的攤還計數風格——你把一連串操作當作整體去界定，而不是把最壞情況算在每一步頭上。光看那層巢狀迴圈就斷言掃描是 O(n^2)，會是個真切的錯誤；是那份彈出預算救了它。
葛立恆掃描：同樣的構想，極角排序
歷史上著名的版本是 葛立恆掃描，它是同一具「左轉堆疊」引擎，只是換了排序鍵。它不依 x 排序，而是挑出最低的點（y 最小、y 相同看 x）當樞軸——這個點保證在凸包上。接著把其餘所有點依它們與樞軸所成的角度排序，像雷達臂繞著樞軸由右掃到左。然後沿那個角度順序走過各點，套用一模一樣的規則：當堆疊頂端兩點與下一個點未能構成左轉時，彈出；然後壓入。結果是一趟就走完整個凸包，而非兩半。
為什麼依角度排序行得通？因為繞樞軸依角度遞增掃過各點，正好以「逆時針凸包會依序遇到它們」的順序造訪。樞軸固定住底部，當角度增大，你自然先遇到右側、再到頂部、再到左側。整趟維持同一個「只准左轉」的不變量，所以同一個「彈出凹陷」的堆疊建出凸包。葛立恆掃描的角度排序比單調鏈的 x 排序略為講究——你是用方向去比較點、而非比一個普通數字，而且必須小心處理角度相等的並列——這也是許多人實務上偏好單調鏈的原因。但成本完全相同：排序 O(n log n)，那趟掃描以同一個彈出計數論證得 O(n)。
一個小推演，以及它為何正確
取五個點，用單調鏈建下凸包。依 x 排序後是 A(0,0)、B(1,2)、C(2,1)、D(3,3)、E(4,0)。壓入 A、壓入 B。加入 C：看最後兩個 A、B 與 C——A 到 B 到 C 向下彎，是右轉，故彈出 B；堆疊剩 [A]，不足兩點，故壓入 C。現在是 [A, C]。加入 D：A、C、D 構成左轉（向上彎），故不彈出，壓入 D——[A, C, D]。加入 E：C、D、E 向下彎、是右轉，彈出 D；現在 A、C、E——A 到 C 到 E 又向下彎，彈出 C；堆疊剩 [A]，壓入 E。下凸包：A、E。注意 B、C、D 都被丟棄了：B(1,2) 與 C(2,1) 都落在 A-E 這條 y=0 的底邊之上，而 D(3,3) 更是高高凸在它上方，所以都不屬於下邊界。
- 不變量：每處理完一個點後，堆疊依序存放「目前所見全部點的下凸包」——其中每個連續三元組都構成左轉（無凹陷）。這就是迴圈不變量；確認它在起點成立（單一點自然沒有三元組），且在每一步之後也成立。
- 維持：加入 p 時，每次彈出移除的頂點，連同它的兩個鄰點未通過左轉測試——這個點不可能在「含 p 的點集」的凸包上，因為它落在 p 所造出的彎折內側。把所有壞頂點彈出、再壓入 p 後，每個三元組又都左轉，故不變量存活。
- 終止與正確性：處理完最後一個點後，不變量說明堆疊就是「全部點的下凸包」。上掃描以同樣方式給出上凸包；接起來便得完整凸包，而樞軸／最左／最右端點保證兩條鏈乾淨地相接。
誠實的限制，與那個下界
我們能勝過 O(n log n) 嗎？對基於比較的凸包演算法而言，不能——而理由很美。這裡有一個凸包下界：若你能以快於 O(n log n) 算出凸包，你就能以快於 O(n log n) 排序 n 個實數，而這是比較排序下界所禁止的。訣竅是一個歸約：把每個數 a 映到點 (a, a^2)，全都坐在一條拋物線上，每個點都在凸包上。依序讀出凸包就還原出排好序的那些數。所以排序歸約到求凸包；凸包至少和排序一樣難；Theta(n log n) 就是這整族演算法誠實的下限。
兩點誠實的提醒收尾。第一，那個下界是針對比較／代數模型的；當凸包很小時，輸出敏感的演算法可以更快，以 O(n log h) 執行，其中 h 是凸包頂點數——所以一千個點卻只有三角形凸包，不必付出完整的排序成本。第二，當心退化情形：凸包邊上三點以上共線、或重複點，正是草率的「非左轉就彈出」實作會出錯的地方。要刻意決定邊上的共線點該保留還是丟棄，並在方向測試中用整數或精確算術，免得一個近乎零的外積被浮點誤差翻了符號——正是上一篇貫穿全文的同一份穩健性顧慮。