凸包算法是一 類 計算 幾何算法，旨在找到 一個能包含所有 給定 點的最小凸多 邊形。 這 類算法在 計算 機 圖形 學、 機器人路 徑 規劃等 領域有 廣泛 套用。常 見的凸包算法 包括Graham 掃描法、Jarvis步 進法、卷包裹法、分治法等，其中Graham 掃描法和Jarvis步 進法 較 為著名。
以下是凸包算法的 詳 細介 紹：
Graham 掃描法。 該算法首先 選 擇 一個基 點（通常是所有 點中x坐 標最小的 點，如果x坐 標相同 則考 慮y坐 標最小的 點），然 後 將其他 點按照 與基 點的 極角 順序排序。使用 一個 棧 來存 儲凸包上的 點，首先 將基 點入 棧，然 後逐 個 將其他 點加入 棧中，同 時 維 護 一個指 針（如T 棧） 來 處理不在凸包上的 點。在加入新 點 時，需要 檢查新 點 與 棧 頂和次 棧 頂 點 構成的折 線段的拐向，如果新 點使得折 線段向右拐， 則 彈出 棧 頂 點，直到折 線段向左拐或 棧中只剩 兩個 點。
Jarvis步 進法。 該算法 從任意 點 開始， 選 擇 一個未被 處理 過的最近 點（即到 當前凸包 頂 點的距 離最近的 點）， 將其加入凸包，然 後 繼 續 選 擇下 一個未被 處理 過的最近 點，直到所有 點都被 處理 過。
卷包裹法和分治法。 這 兩 種算法也常 用於求解凸包 問 題，但它 們的 實 現和 複雜度 與Graham 掃描法和Jarvis步 進法有所不同。
這些算法的 時 間 複雜度主要 取決於 點的 數量和分 布。Graham 掃描法和Jarvis步 進法的平均 時 間 複雜度 為O(nlogn)，其中n是 點的 數量。