摘要
凸包（Convex Hull）是指能在歐式幾何平面與空間中包覆一群散佈點的最小凸集合，且其面積或容積為最小。凸包在計算幾何中為一項重要的研究學問，被大量運用在圖形處理、地理資訊系統、無人地面車輛路徑規劃及二次表面巡航導彈任務規劃，可堪稱為指標性演算法。本文中我們提出全新獨創網格新解的凸包演算法。藉由網格建立圍牆並且忽略圍牆內之非凸包節點，可使節點數有效地由n降至n/logn，接著將此n/logn點（離座標中心點較遠的點）代入任意時間複雜度為O（n log n）之凸包演算法，便可在線性期望時間O（n）獲得凸包，其中n為節點總數。在非特殊狀況下本文演算法預期時間複雜度為線性時間O（n），預期實際運算時間較Akl，Jiang及Quick-hull等演算法期望時間更短，為目前實際運算時間最快之演算法。