簡介這套Python項目面向算法學(xué)習(xí)者與圖形學(xué)、機器學(xué)習(xí)開發(fā)者用純Python復(fù)現(xiàn)了Graham掃描、Jarvis步進與Andrew剪枝等經(jīng)典凸包算法并提供numpy向量運算與matplotlib可視化輔助實現(xiàn)可用于碰撞檢測、數(shù)據(jù)聚類、區(qū)域邊界計算等場景。資源包共5個文件以4個Python腳本為主體分別負(fù)責(zé)核心凸包計算、圖形繪制、測試用例與性能基準(zhǔn)測試另含1個Markdown說明文檔整體僅7KB代碼精煉易讀。目前已有261人學(xué)習(xí)瀏覽適合希望理解凸包數(shù)學(xué)原理并快速集成到自身項目中的中高級Python開發(fā)者。通過閱讀源碼與測試可掌握不同算法的適用條件與優(yōu)化思路并借鑒其模塊劃分方式擴展其他幾何算法。1. 凸包算法 Python 實戰(zhàn)從輪子到重構(gòu)這份資源到底解決了什么搞圖像處理或者點云分析的人大概率都遇到過這種場景給了一堆散亂坐標(biāo)點想讓程序畫出它們最外層的輪廓邊界用來做碰撞檢測、多邊形擬合或者聚類可視化。如果自己從零寫凸包算法Graham 掃描、Jarvis 步進、快速凸包、單調(diào)鏈……光排序策略就能折騰一晚上而且數(shù)值誤差、共線點處理、浮點精度這些坑一個接一個。這份用 Python 重寫的凸包項目核心價值就是把軟件工程里常用的那幾類凸包算法重新實現(xiàn)了一遍輸出格式規(guī)整、接口統(tǒng)一拿來就能跑。它適合兩類人一類是做數(shù)據(jù)分析或圖形處理需要快速拿到點集邊界做后續(xù)計算的工程師另一類是學(xué)算法想看點真實工程實現(xiàn)細(xì)節(jié)的學(xué)生。項目不是造了一個新概念而是把 DistMesh、CGAL 這類軟件里常見的凸包策略用 Python 重新表達(dá)出來換點數(shù)據(jù)就能看到結(jié)果測性能也有底。對于不想自己處理排序比較器、共線剔除這些繁瑣細(xì)節(jié)的人這份資源能省掉至少半天調(diào)試時間。2. 算法選型與核心代碼結(jié)構(gòu)為什么灰度測試要同時保留四種策略2.1 凸包問題的定義與四種常見算法選型邏輯凸包問題的數(shù)學(xué)定義很簡單給定平面上的點集 P求一個最小凸多邊形使得 P 中所有點都在該多邊形內(nèi)部或邊界上。看似簡單但不同算法在時間復(fù)雜度、數(shù)值魯棒性和實現(xiàn)復(fù)雜度上的取舍完全不同這也是項目里沒有只留一種實現(xiàn)的原因。項目重構(gòu)的四種算法各代表一種思路Graham 掃描基于極角排序加棧維護適合點數(shù)在幾萬到幾十萬的中等規(guī)模實現(xiàn)直觀Jarvis 步進禮品包裝法的時間復(fù)雜度為 O(nh)其中 h 是凸包頂點數(shù)適合包頂點數(shù)量遠(yuǎn)小于總點數(shù)的場合比如圍繞一個橢圓的隨機點快速凸包是分治思想的典型應(yīng)用平均性能好但最壞情況退化單調(diào)鏈Andrew把排序從極角換成坐標(biāo)字典序避免了反三角函數(shù)的浮點開銷在處理大規(guī)模靜態(tài)點集時最穩(wěn)。選型邏輯是一門工程學(xué)問。如果你的數(shù)據(jù)點分布相對均勻且點量在十萬以內(nèi)Graham 掃描最簡單錯誤率低如果點集呈現(xiàn)出明顯的“外圍點稀疏、內(nèi)部點密集”特征Jarvis 可能更快如果點集是從實時傳感器流式來的每次只新增少量點增量凸包或局部更新策略才是正解。項目沒有做動態(tài)版本但把靜態(tài)算法都補全了測試的時候能直接比出每種算法在同等數(shù)據(jù)下的真實耗時而不是只看理論復(fù)雜度。2.2 入口模塊與統(tǒng)一數(shù)據(jù)結(jié)構(gòu)的工程拆解項目里最值得先看的是入口模塊中的數(shù)據(jù)結(jié)構(gòu)定義。它沒有直接用裸的 list 存二維坐標(biāo)而是定義了一個 Point 集合類型內(nèi)部基于浮點數(shù)數(shù)組存儲。這樣做的好處是第一后續(xù)所有算法都能復(fù)用同一套比較器、排序邏輯和共線判定第二寫可視化測試時可以直接把該結(jié)構(gòu)喂給 matplotlib 的路徑繪制接口不用做數(shù)據(jù)格式轉(zhuǎn)換。常見做法是 Point 類包含 x、y 兩個浮點屬性同時實現(xiàn)__lt__和__eq__方法便于 sorted() 直接使用。如果該點在數(shù)值上等于另一個點誤差在 1e-9 內(nèi)則視為重合點直接跳過。輸入數(shù)據(jù)通過 from_points 之類的方法解析數(shù)組或者從 CSV 讀取時自動完成去重。這部分代碼雖然不算難但四個算法共用一套輸入校驗?zāi)苊黠@降低維護成本。參數(shù)說明核心的 epsilon 參數(shù)是容差值默認(rèn) 1e-9用于浮點比較如果數(shù)據(jù)來源是 GPS 坐標(biāo)或圖像像素建議把它調(diào)大到 1e-6否則靠近邊界的點可能因為微小的浮點誤差被錯誤判定為凸包頂點。另一個重要參數(shù)是include_collinear默認(rèn) False表示把共線點去掉只保留極端頂點做碰撞檢測或渲染時保持 False 即可但做面積計算或者需要精確還原原始邊界時應(yīng)改為 True。3. 從零實現(xiàn) Graham 掃描排序、棧維護與共線點剔除的完整過程3.1 極角排序與基準(zhǔn)點選取的實現(xiàn)要點Graham 掃描的第一步是找到 y 坐標(biāo)最小的點如果存在多個 y 相同的點取 x 最小的那個作為基準(zhǔn)點這個點必然在凸包上。然后計算其他點相對于基準(zhǔn)點的極角按極角升序排序若極角相同則按距離從近到遠(yuǎn)排列。之所以這樣排是因為后續(xù)的棧掃描需要按逆時針一圈處理所有點。def graham_scan(points): # 找基準(zhǔn)點y 最小若 y 相同取 x 最小 start min(points, keylambda p: (p.y, p.x)) # 按極角排序極角相同按距離從近到遠(yuǎn) sorted_pts sorted( points, keylambda p: (math.atan2(p.y - start.y, p.x - start.x), (p.x - start.x)**2 (p.y - start.y)**2) ) stack [sorted_pts[0], sorted_pts[1]] for p in sorted_pts[2:]: while len(stack) 2 and cross(stack[-2], stack[-1], p) 0: stack.pop() stack.append(p) return stack這段代碼里最容易被忽略的是排序時的距離比較。如果只用math.atan2排序極角相等的點順序是隨機的雖然最終棧掃描會剔除部分非凸包點但在邊緣情況下可能出現(xiàn)棧內(nèi)點順序錯亂導(dǎo)致漏點。把它改成“極角加距離”的組合排序后每輪掃描拿到的都是嚴(yán)格的外層點序后面就不用再補一輪碰撞修正了。邏輯說明cross(o, a, b)函數(shù)返回向量 oa 和 ob 的叉積。叉積大于 0 表示 b 在 a 的逆時針方向小于 0 表示順時針等于 0 表示三點共線。while循環(huán)里只要發(fā)現(xiàn)新點讓棧頂兩個點形成的方向不是逆時針就把棧頂點彈出。這個“逆時針維護”是核心所有版本的 Graham 實現(xiàn)都依賴這個判斷。3.2 用繞數(shù)法代替反三角函數(shù)規(guī)避精度陷阱在上面的代碼里用math.atan2排序最直觀但存在兩個問題第一計算量大每個點都需要調(diào)用一次反正切第二對于位于基準(zhǔn)點正上方和正下方的點atan2 的結(jié)果可能在 π 和 -π 附近跳變造成排序不穩(wěn)定。工程上更穩(wěn)的排序方式是把整個排序邏輯改為基于象限加叉積的比較器這樣不需要計算任何角度。def compare_angle(p1, p2, origin): # 按象限分桶4個象限天然有序 q1 quadrant(p1, origin) q2 quadrant(p2, origin) if q1 ! q2: return q1 - q2 c cross(origin, p1, p2) if c 0: return -1 elif c 0: return 1 else: d1 dist_sq(p1, origin) d2 dist_sq(p2, origin) return d1 - d2quadrant 函數(shù)根據(jù)點相對于基準(zhǔn)點的位置返回 03 的整數(shù)值四個象限天然形成全序關(guān)系。象限相同的點用叉積判斷誰在外側(cè)叉積為 0 時用距離區(qū)分。這個改動直接把排序的時間消耗砍掉一半以上因為常見點集大部分點都集中在第一個象限根本不會觸發(fā)atan2調(diào)用。更重要的是它徹底規(guī)避了角度閾值附近的排序不確定問題——這在處理包含大量“中軸線附近”點的數(shù)據(jù)時尤其明顯。我一般會建議把這段排序代碼保存為一個單獨的_sort_by_angle函數(shù)這樣 Graham 掃描和 Jarvis 步進都能復(fù)用。項目里的實現(xiàn)也確實是這樣的結(jié)構(gòu)四個算法模塊共享一套內(nèi)部排序函數(shù)改排序策略時可以只改一處。4. 單調(diào)鏈與快速凸包的對比實現(xiàn)什么時候該換算法4.1 單調(diào)鏈實現(xiàn)不用反三角函數(shù)的絕對優(yōu)勢單調(diào)鏈Andrew把凸包拆成上鏈和下鏈兩部分排序方式直接按 x 坐標(biāo)升序x 相同則按 y 升序。構(gòu)造下鏈時從左往右掃構(gòu)造上鏈時從右往左掃中間用同一個 cross 判斷彈棧。它不依賴極角也沒有象限判斷排序只需要一次字典序比較因此排序過程的常量被壓到最低。def convex_hull_andrew(points): # 排序去重 pts sorted(set(points), keylambda p: (p.x, p.y)) if len(pts) 1: return pts lower [] for p in pts: while len(lower) 2 and cross(lower[-2], lower[-1], p) 0: lower.pop() lower.append(p) upper [] for p in reversed(pts): while len(upper) 2 and cross(upper[-2], upper[-1], p) 0: upper.pop() upper.append(p) return lower[:-1] upper[:-1]這段代碼是最標(biāo)準(zhǔn)的單調(diào)鏈寫法有幾處細(xì)節(jié)值得注意。首先排序前用set(points)去重但如果 Point 類實現(xiàn)了__hash__且基于浮點數(shù)那浮點表示的微小差異可能導(dǎo)致去重失敗或誤去重。項目里提供一個deduplicate參數(shù)默認(rèn)開啟內(nèi)部通過容差分組來去重而不是純靠集合哈希。參數(shù)說明lower[:-1]和upper[:-1]去掉的是兩個鏈的重復(fù)端點順序拼接后得到完整凸包。如果用 0作為彈棧條件會丟棄共線點得到最小頂點集若改為 0則會保留所有共線邊界點這在需要精確還原路徑時很有用。實測下來對于一百萬個均勻分布點Graham 掃描耗時約為單調(diào)鏈的 1.4 倍主要差在排序比較器的計算復(fù)雜度上。4.2 快速凸包的分治結(jié)構(gòu)與遞歸深度控制快速凸包的核心思想是找一條極值邊然后把點分成左右兩部分遞歸處理。每次選離線段最遠(yuǎn)的點作為新的分裂點用叉積判斷點在直線的哪一側(cè)。平均復(fù)雜度 O(n log n)但最壞情況下每次劃分都極度不平衡退化成 O(n^2)。項目里針對這個缺點做了一個改進當(dāng)遞歸層數(shù)超過閾值或者當(dāng)前子點集數(shù)量小于某個值時直接改用暴力枚舉找極值點而不是繼續(xù)遞歸。def quickhull(points, threshold16, depth0): if len(points) threshold or depth 20: return simple_hull(points) # 找 x 方向最左和最右的點作為初始分裂邊 leftmost min(points, keylambda p: p.x) rightmost max(points, keylambda p: p.x) # 按線段左右分割 left_set, right_set [], [] for p in points: c cross(leftmost, rightmost, p) if c 5e-10: left_set.append(p) elif c -5e-10: right_set.append(p) # 遞歸求解兩側(cè)并合并 hull_left quickhull(left_set, threshold, depth1) hull_right quickhull(right_set, threshold, depth1) return merge_hull(hull_left, hull_right, leftmost, rightmost)這里threshold16是葉子節(jié)點大小子集數(shù)量小于等于 16 時直接用一個簡單的 O(n log n) 小規(guī)模排序求解避免遞歸開銷。depth 20是深度上限應(yīng)付極端退化數(shù)據(jù)。叉積判斷時用5e-10而不是 0是給浮點誤差留余量這在大坐標(biāo)數(shù)值比如經(jīng)緯度坐標(biāo)下特別重要。注意兩側(cè)遞歸的叉積符號必須相反否則分割方向會亂。我實際用圖像檢測輸出的幾千個輪廓點測試過快速凸包在隨機分布數(shù)據(jù)下的性能比單調(diào)鏈稍差大概慢 5%10%但在處理近似圓形分布的數(shù)據(jù)時它的增量特征表現(xiàn)很好。如果你的點集分布極不均勻比如點云里有明顯的長尾結(jié)構(gòu)快速凸包容易退化此時優(yōu)先選單調(diào)鏈這是經(jīng)驗之談。5. 凸包算法避坑指南浮點誤差、空集處理與可視化陷阱5.1 浮點誤差導(dǎo)致凸包頂點缺失或多余現(xiàn)象同一個數(shù)據(jù)集多次運行凸包頂點數(shù)量偶爾會相差一兩個邊界點出現(xiàn)微小的鋸齒。原因叉積結(jié)果接近 0 時浮點精度決定它落在 0 的哪一側(cè)。不同的排序、不同的運算次序都會改變浮點累積誤差導(dǎo)致對共線點、近共線點的判定發(fā)生切換。解決建立統(tǒng)一誤差容限。項目里提供一個epsilon參數(shù)貫穿所有算法判定叉積是否等于 0 時用abs(cross_value) epsilon而不是 0。實際調(diào)試中我習(xí)慣在測試代碼里同時計算帶容差和不帶容差的結(jié)果對比兩次輸出頂點集合若差異頂點到擬合直線的距離都在 epsilon 級就說明是精度問題不是邏輯問題。把 epsilon 設(shè)置成 1e-7 到 1e-9 之間較為穩(wěn)妥。5.2 傳入空列表或者單點集直接崩潰現(xiàn)象調(diào)用凸包函數(shù)時傳入空列表程序拋 IndexError傳入一個點或者兩個點返回結(jié)果里出現(xiàn)重復(fù)點。原因算法假設(shè)輸入至少有三個不共線的點空列表時[sorted_pts[0]]直接越界兩點或單點情況下的棧初始化條件沒有覆蓋。解決項目的convex_hull_main入口模塊應(yīng)該統(tǒng)一做前置校驗空列表返回空列表單點返回單點列表兩點返回包含兩個點的列表三點共線的情況根據(jù)include_collinear決定是否去重。自己用的時候也建議加一層防御if len(points) 0: return [] if len(points) 2: return list(points)這類問題最容易出現(xiàn)在把算法嵌入到流水線、但上游數(shù)據(jù)源為空或異常時。血淚經(jīng)驗是不要相信上游數(shù)據(jù)一定合法入口處多做一次長度和類型檢查比在算法內(nèi)部瘋狂 debug 有效得多。5.3 可視化時凸包沒有閉合現(xiàn)象用 matplotlib 繪制凸包結(jié)果時圖形不閉合最后一個點和第一個點之間缺少連線。原因算法返回的是按順序排列的頂點列表但不包含“回到起點的閉合邊”。繪制時需要把第一個點追加到列表末尾。解決項目里配了一段可視化演示代碼繪制前執(zhí)行hull.append(hull[0])。需要注意如果空列表或單點列表也執(zhí)行該操作會引入空元素所以要在長度大于等于 2 時才追加。如果你用 Matplotlib 的 Polygon傳入 hull 頂點列表它不會自動閉合必須手動把起點補在末尾。這段代碼單獨抽成了一個show_hull工具函數(shù)接受 points 和 hull 兩個參數(shù)返回一個圖形對象。5.4 故意構(gòu)造共線大量點導(dǎo)致 GJK 或碰撞檢測誤判現(xiàn)象點集中大量點落在同一直線上算法輸出的凸包退化成一個線段或者一條直線附近的窄長帶后續(xù)基于凸包的碰撞檢測把不相交的物體誤判為相交。原因include_collinearFalse時去掉了共線點但凸包本身是一條退化多邊形面積接近于 0。碰撞檢測模塊通常默認(rèn)凸包是多邊形對退化情形沒有特殊處理。解決在與幾何引擎集成時增加一個輸出后校驗步驟如果凸包面積小于某個閾值比如 1e-8則視為退化凸包返回空區(qū)域或跳過碰撞檢測。通常的做法是計算凸包多邊形面積的絕對值和原始點集的包圍盒面積做對比占比過高或過低都要標(biāo)記為潛在退化。5.5 算法之間結(jié)果不完全一致導(dǎo)致測試斷言失敗現(xiàn)象單元測試?yán)飻嘌运姆N算法輸出完全等同的頂點集合但 Graham 掃描輸出 5 個點單調(diào)鏈和快速凸包輸出 6 個點差一個邊界點。原因前面提到共線點處理策略不一致。Graham 掃描采用cross 0彈棧主動丟共線點單調(diào)鏈用 0也會丟但如果快速凸包分裂時用的是 5e-10容差范圍內(nèi)的點會被當(dāng)成不共線保留下來。解決項目里提供normalize_hull函數(shù)把所有算法輸出統(tǒng)一經(jīng)過共線剔除和去重再比較。做測試對比時對比的是normalize_hull(hull)而不是原始返回。我在調(diào)試時還發(fā)現(xiàn)如果兩個算法的排序方式不同起點位置也會不同所以測試斷言要用集合或環(huán)形序列規(guī)范化旋轉(zhuǎn)到字典序最小起點來比較。6. 把凸包作為計算幾何的基石面積、周長與最小外接矩形擴展拿到凸包頂點后下一步通常不是直接畫圖而是計算它的面積、周長、重心或者求包圍它的最小外接矩形。這些延伸功能在碰撞檢測和路徑規(guī)劃里特別常用而且實現(xiàn)起來都是基于凸包頂點的簡單線性操作。面積用鞋帶公式掃描一圈就能得到不需要額外的排序。在凸包頂點按逆時針或順時針有序的前提下鞋帶公式是穩(wěn)定的若頂點點序混亂面積結(jié)果會在正負(fù)之間跳變絕對值仍正確但效率低。正確的做法是直接對有序凸包頂點做求和順便檢查輸出是否為逆時針不是的話做一次反轉(zhuǎn)。周長計算更簡單相鄰點距離累加一下就好但這里又要注意閉合問題最后一個點到第一個點的距離必須單獨補上否則周長少一條邊。很多初用凸包的人會在這里翻車因為算法返回的頂點列表中第一和最后一個點不是天然的相鄰關(guān)系而是代表兩條不同的邊上的點。重心坐標(biāo)計算稍微麻煩一些不能像面積那樣線性處理。項目里實現(xiàn)的方法是把凸包三角形剖分對每個小三角形用質(zhì)量加權(quán)平均。由于凸包一定是凸多邊形這個剖分永遠(yuǎn)可行不會出現(xiàn)自相交情況。我一般會把這三個計算封裝在polygon_metrics模塊中接收 hull 頂點和閉合標(biāo)志返回面積、周長、重心和一個可選的包圍盒寬高方便直接對接下游邏輯。最小外接矩形屬于進階內(nèi)容嚴(yán)格來說需要旋轉(zhuǎn)卡殼算法但工程上有一個近似技巧先求凸包然后逐邊嘗試將凸包旋轉(zhuǎn)到該邊與坐標(biāo)軸平行的位置計算旋轉(zhuǎn)后的包圍盒面積最終取面積最小的那個旋轉(zhuǎn)角度。這個方法的復(fù)雜度是 O(k^2)k 為頂點數(shù)對幾百個頂點的凸包完全夠用而且它很容易用 numpy 向量化for i, p1 in enumerate(hull): p2 hull[(i 1) % len(hull)] angle math.atan2(p2.y - p1.y, p2.x - p1.x) # 旋轉(zhuǎn)所有點到該角度對應(yīng)的局部坐標(biāo) rotated rotate(hull, -angle) min_x, max_x min(rotated.x), max(rotated.x) min_y, max_y min(rotated.y), max(rotated.y) area (max_x - min_x) * (max_y - min_y) if area best_area: # 保存角度和矩形的參數(shù)在實際項目里我用這套方法做過點云簇的外接框提取再把外接框送入一個簡單的碰撞檢測邏輯效果相當(dāng)穩(wěn)定。從那以后我每次拿到陌生點云數(shù)據(jù)集都會先跑一遍單調(diào)鏈拿凸包再自動算面積和最小外接矩形這個流程已經(jīng)成了我檢查數(shù)據(jù)質(zhì)量的默認(rèn)習(xí)慣。建議你把拿到的資源先跑一遍項目自帶的演示腳本輸入點改為自己的坐標(biāo)數(shù)據(jù)觀察凸包結(jié)果和面積指標(biāo)是否符合預(yù)期。希望這份凸包算法的 Python 實現(xiàn)能幫你少走彎路。本文還有配套的精品資源點擊獲取