凸包（convex hull）

在木板上、你的每個點位置各釘一根釘子，把一條橡皮筋撐開、繞住所有釘子，然後放手讓它縮緊。它穩定下來的繃緊形狀——只碰到最外圈的釘子、跳過所有藏在裡面的——就是凸包（convex hull）。形式上，一組點的凸包是包含所有點的最小凸多邊形：凸的意思是沒有凹陷，邊界永不往內折回，且該區域內任兩點的連線段都留在區域之內。凸包的頂點是原始點的子集；其餘的點都落在邊界上或邊界內。

它是計算幾何中最基本的結構，因為它抓住了點雲的外形、丟掉了內部的雜亂。一旦有了凸包，你就能很快讀出直徑（最遠的兩個點）、最小包圍盒，或判斷一個新點是否落在點雲內部。對給定的點集，凸包是唯一的；沿邊界依序列出其頂點時，會做出你預期的轉向：逆時針沿邊界走，你只會一直左轉（或直走）。正是這個性質——每個邊界轉向都是左轉——讓凸包演算法得以利用，並用方向測試來驗證。

有好幾種演算法可計算凸包，它們的取捨頗具啟發性。葛立恆掃描（Graham scan）與安德魯單調鏈（Andrew's monotone chain）都先排序，跑 O(n log n)；禮品包裝法（gift wrapping，又稱賈維斯步進）跑 O(n*h)，其中 h 是凸包頂點數，當凸包很小時很棒，但當幾乎所有點都在凸包上時可能變成 O(n^2)。在最壞情況下，任何以比較為基礎的方法都無法勝過 O(n log n)，因為排序可歸約成求凸包——這就是凸包下界。凸包出現在碰撞偵測、模式辨識、計算界定資料的形狀，以及作為許多其他幾何演算法的子程序。