凸包演算法（convex-hull algorithm）
在一組點上釘下釘子，再用一條橡皮筋把它們全部圈起來：當它繃緊時，便描出包含每個點的最小凸形狀。那個輪廓就是凸包，而凸包演算法是計算它的程序——找出究竟哪些點是角落、以及它們繞邊界的順序。它是計算幾何中最基本的非平凡問題，也是通往沃羅諾伊、德勞內與線性規劃的門戶。
有限點集 P 的凸包是包含 P 的最小凸集，等價於 P 中各點所有凸組合的集合；在平面中其邊界是一個凸多邊形，頂點是 P 的一個子集。有數種演算法計算它。Graham 掃描把點繞最低點按角度排序，然後走過排序後的清單，把點推入堆疊，並彈出任何會造成右（順時針）轉的點，耗時 O(n log n)，由排序主導。Andrew 的單調鏈變體按 x 座標排序，分別建上下凸包。禮物包裝（Jarvis 行進）反覆藉挑選最逆時針的點來找下一條凸包邊，耗費 O(n*h)，其中 h 是凸包頂點數——當凸包小時很快。Quickhull 模仿快速排序，遞迴地丟棄內部點，平均表現良好。貫穿始終的關鍵基元是定向測試：一個 2x2（或 3x3）行列式的正負號，告訴你三點是左轉、右轉還是共線。
凸包演算法作為一個建構塊很重要：平面 O(n log n) 界是最優的（排序可化約為凸包），而在高維中凸包撐起德勞內三角剖分（抬升到拋物面、取下凸包）、線性規劃可行性與碰撞偵測。誠實的告誡：輸出大小要緊——在 d 維中，n 個點的凸包可有約 n^{floor(d/2)} 個面，所以「計算凸包」在二維／三維中便宜，在高維卻可能組合爆炸；而這些演算法在定向測試中對浮點誤差出了名地敏感，一個近共線的三元組可能被誤判而毀掉凸包，所以穩健的實作使用精確或自適應精度算術，並明確處理共線與重複的點。
對一組平面點做 Graham 掃描：挑最低點為錨點，把其餘點繞它按極角排序，然後掃過排序後的清單並維護一個堆疊——對每個新點，只要堆疊最後兩點加上新點構成順時針轉（定向行列式為負），就彈出堆疊；否則推入。掃描結束時堆疊以逆時針順序持有凸包頂點，全程 O(n log n)。
Graham 掃描：按角度排序，然後彈出每個順時針轉——堆疊上倖存的就是凸包。
定向（行列式正負號）測試是演算法的罩門：近共線三元組上的浮點捨入誤差可能給出錯誤的轉向，產生一個非凸或自相交的「凸包」。穩健的程式碼使用精確或自適應精度的判定式，並明確處理共線與重複的點；在高維中還要記得輸出本身可能呈指數級龐大。