簡(jiǎn)介這是一款基于JavaScript實(shí)現(xiàn)的Alpha Shape計(jì)算工具包專為需要在任意維度點(diǎn)集中提取邊界輪廓的開(kāi)發(fā)者設(shè)計(jì)常用于計(jì)算幾何、點(diǎn)云數(shù)據(jù)分析、三維重建以及非凸形狀檢測(cè)等場(chǎng)景。壓縮包共含7個(gè)文件核心alpha.js負(fù)責(zé)形狀計(jì)算viewer.js提供可視化示例README.md說(shuō)明安裝與API用法alpha.png為效果示意圖另有package.json、LICENSE、.gitignore等配套文件整體僅39KB結(jié)構(gòu)清晰便于快速集成或研讀源碼。目前已有1515人學(xué)習(xí)下載。借助該資源讀者可直接調(diào)用alpha-shape接口通過(guò)調(diào)節(jié)alpha參數(shù)如0.1控制形狀的精細(xì)程度適應(yīng)不同密度的點(diǎn)集同時(shí)可從示例代碼中掌握模塊封裝、隨機(jī)點(diǎn)生成、結(jié)果輸出的完整流程并結(jié)合注釋理解算法邊界判定的實(shí)現(xiàn)思路對(duì)計(jì)算幾何學(xué)習(xí)與前端圖形開(kāi)發(fā)都很有幫助。1. alpha shape 是什么從一堆散點(diǎn)里找回被凸包吞掉的凹邊界做點(diǎn)云處理時(shí)最常遇到的尷尬時(shí)刻是你把一堆邊界點(diǎn)扔給凸包算法明明有條內(nèi)凹的溝壑凸包卻把它填成一個(gè)飽滿的多邊形三維里更明顯轉(zhuǎn)個(gè)角度就發(fā)現(xiàn)表面凹進(jìn)去一塊凸包直接給你一個(gè)鼓包。alpha shape 就是為這個(gè)場(chǎng)景準(zhǔn)備的它允許你用同一個(gè)算法在二維畫出帶凹坑的輪廓在三維生成能貼住真實(shí)表面的網(wǎng)格而且理論框架不限制維度二維、三維、甚至更高維都能用同一套邏輯去描述。我最初接觸 alpha shape 是為了重建一塊激光掃描點(diǎn)云的輪廓凸包把所有缺口都蓋住了手工編輯又太慢。后來(lái)看明白它的幾何判定發(fā)現(xiàn)它并不玄學(xué)它用一條固定半徑的圓滾過(guò)點(diǎn)集邊界圓能滾過(guò)去的部分才屬于邊界。這個(gè)半徑反過(guò)來(lái)就是 alpha 值的倒數(shù)也就是全局的細(xì)節(jié)程度。這個(gè)工具適合誰(shuí)適合手里有點(diǎn)集、想恢復(fù)邊界或表面、又不想逐段手工修線的人。相比凹包算法它有嚴(yán)格的數(shù)學(xué)定義和穩(wěn)定實(shí)現(xiàn)路徑相比人工畫輪廓它可以批量處理成百上千份數(shù)據(jù)。下面從原理講到二維和三維的可用實(shí)現(xiàn)再落到參數(shù)怎么調(diào)、哪些坑不能踩最后給一個(gè)我常用的驗(yàn)證手法。2. 從凸包到 alpha shapealpha 值如何決定邊界細(xì)節(jié)2.1 凸包只是最粗的殼凹形才是大多數(shù)點(diǎn)云的真實(shí)邊界凸包的定義很簡(jiǎn)單包含所有點(diǎn)的最小凸集。它算法穩(wěn)定、幾十個(gè)點(diǎn)也能秒出結(jié)果所以經(jīng)常被當(dāng)成點(diǎn)云默認(rèn)邊界但它有個(gè)天然缺陷看不到凹形。想象一個(gè) C 形點(diǎn)集凸包直接畫成一個(gè)大圓盤C 的開(kāi)口被完全吞掉而真實(shí)物體的輪廓、自然地形、人體輪廓、河岸線幾乎都不是凸的。如果你把凸包結(jié)果直接給數(shù)控加工路徑或碰撞檢測(cè)會(huì)出現(xiàn)明明可以避開(kāi)的區(qū)域被當(dāng)成實(shí)體造成材料浪費(fèi)或路徑誤判。alpha shape 保留了凸包“只用點(diǎn)集本身生成邊界”的優(yōu)點(diǎn)同時(shí)解除了“必須凸”的限制。它的核心建立在 Delaunay 三角剖分上先對(duì)點(diǎn)集做三角剖分然后刪除那些外接圓半徑大于給定閾值的三角形。刪掉大三角形后邊界會(huì)沿著點(diǎn)集的密度和實(shí)際形狀收縮。因此 alpha 值越小允許留下的三角形外接圓越大邊界越接近凸包alpha 值越大允許留下的三角形外接圓越小邊界細(xì)節(jié)越豐富但也越容易碎成斷層。在實(shí)際項(xiàng)目里我一般先把 alpha 設(shè)成一個(gè)能保證點(diǎn)集整體連通的較小值然后逐步放大找出細(xì)節(jié)穩(wěn)定的區(qū)間。這個(gè)區(qū)間通常存在一個(gè)“肘部”拐點(diǎn)alpha 增到某個(gè)值之后邊界形態(tài)的變化從劇烈變成緩慢。做批量處理時(shí)用這個(gè)拐點(diǎn)對(duì)應(yīng)的 alpha 作為默認(rèn)參數(shù)比手工指定一個(gè)固定值穩(wěn)得多。如果業(yè)務(wù)只求外接范圍、做碰撞體積、算軸向包圍盒凸包足夠如果把邊界輸出給下一條工序比如加工路徑、體積估算、河岸線提取就必須考慮凹形。我的習(xí)慣是先跑凸包當(dāng)兜底再在需要細(xì)節(jié)的局部用 alpha shape 做切削這樣可控性最高。2.2 alpha 參數(shù)的幾何含義滾圓法與 Delaunay 判定alpha shape 最出名的直覺(jué)模型是滾圓法想象用一把固定半徑的圓規(guī)沿著點(diǎn)集外側(cè)滾動(dòng)圓規(guī)能卡住哪些點(diǎn)哪些點(diǎn)就在邊界上。這個(gè)解釋容易理解但它更像物理過(guò)程很難直接寫成算法。真正實(shí)現(xiàn)里用的是 Delaunay 剖分后的外接球半徑判定對(duì)每個(gè) d 維單純形二維是三角形、三維是四面體計(jì)算它外接球半徑 R如果 R 小于 1/alpha就保留這個(gè)單純形否則刪除。這里有一個(gè)我一開(kāi)始也踩過(guò)的坑alpha 與半徑是倒數(shù)關(guān)系。alpha 越小半徑越大允許保留的大外接球越多結(jié)果越粗糙alpha 越大半徑越小只有外接球很小的局部結(jié)構(gòu)才能保留結(jié)果越細(xì)碎。看代碼或論文時(shí)你會(huì)看到有的參數(shù)叫 alpha有的叫 radius兩者互為倒數(shù)如果搞反調(diào)參時(shí)所有結(jié)論都會(huì)違背直覺(jué)越調(diào)越茫然。滾圓法還有一層誤導(dǎo)它讓人以為每個(gè)點(diǎn)是獨(dú)立判斷的但 alpha shape 的篩選是全局的。同一個(gè)點(diǎn)在 alpha 比較小的時(shí)候可能是邊界點(diǎn)alpha 變大后可能變成內(nèi)部點(diǎn)。它不識(shí)別“孤立點(diǎn)”這類局部密度異常而是對(duì)剖分得到的單純形做整體篩選。所以如果你要的是逐點(diǎn)離群點(diǎn)檢測(cè)應(yīng)該用 LOF 或 DBSCAN而不是 alpha shape。明確這一點(diǎn)能避免選錯(cuò)工具。2.3 任意維度的統(tǒng)一視角單純形與 alpha 值的尺度關(guān)系“任何維度”不是營(yíng)銷話術(shù)它來(lái)自單純形的推廣。二維點(diǎn)集被剖成三角形三維點(diǎn)集被剖成四面體Delaunay 剖分和凸包本身就是維度無(wú)關(guān)的概念。alpha shape 的過(guò)濾條件只依賴外接球半徑和一個(gè)標(biāo)量 alpha這兩個(gè)概念在高維同樣成立。只要你能構(gòu)造出給定維度點(diǎn)集的 Delaunay 剖分就能用同一套過(guò)濾邏輯得到該維度的 alpha shape。但請(qǐng)先冷靜維度變高以后Delaunay 剖分的復(fù)雜度會(huì)急劇上升。n 個(gè)點(diǎn)在 d 維空間中的剖分元素?cái)?shù)量和內(nèi)存占用往往隨維度變大而呈指數(shù)增長(zhǎng)開(kāi)源生態(tài)也幾乎只把高維剖分做到三維。所謂“任何維度”在實(shí)現(xiàn)上通常指“算法不限制維度”而不是“高維數(shù)據(jù)跑得飛快”。我見(jiàn)過(guò)有人拿五維特征工程數(shù)據(jù)嘗試跑通用實(shí)現(xiàn)結(jié)果光剖分就等了一刻鐘最后只能降維處理。所以你要把“任何維度”理解為同一套原理、同一套參數(shù)可以放心從二維推廣到三維而不需要換算法。四維以上則先評(píng)估數(shù)據(jù)量通常做法是先用 PCA 降維或者在低維子空間做 alpha shape再根據(jù)業(yè)務(wù)需要還原。不是 alpha shape 不能做高維而是高維 Delaunay 剖分本身成本太高這是任何基于剖分的方法都要面對(duì)的硬邊界。2.4 快速試 alpha 的 30 行實(shí)驗(yàn)先看半徑分布再調(diào)參在進(jìn)入正式實(shí)現(xiàn)前我建議先把點(diǎn)集的“外接球半徑分布”打出來(lái)這能讓你對(duì) alpha 的選擇范圍心里有數(shù)。下面的代碼生成 200 個(gè)二維隨機(jī)點(diǎn)用 SciPy 求出 Delaunay 三角剖分然后計(jì)算每個(gè)三角形的外接圓半徑并輸出分位數(shù)。注意這個(gè)實(shí)驗(yàn)只服務(wù)于調(diào)參直覺(jué)不是完整的 alpha shape。import numpy as np from scipy.spatial import Delaunay # 生成 200 個(gè)二維點(diǎn)均勻采樣 rng np.random.default_rng(42) pts rng.uniform(-10, 10, size(200, 2)) # Delaunay 三角剖分 tri Delaunay(pts) a pts[tri.simplices[:, 0]] b pts[tri.simplices[:, 1]] c pts[tri.simplices[:, 2]] # 向量化計(jì)算三角形外接圓半徑 R a*b*c / (4*S) ab b - a ac c - a area2 np.abs(ab[:, 0] * ac[:, 1] - ab[:, 1] * ac[:, 0]) len_ab np.linalg.norm(ab, axis1) len_ac np.linalg.norm(ac, axis1) len_bc np.linalg.norm(b - c, axis1) radius len_ab * len_ac * len_bc / (2 * area2) print(半徑分位數(shù), np.percentile(radius, [10, 30, 50, 70, 90, 99]))邏輯說(shuō)明先用 scipy.spatial.Delaunay 求得所有三角形再用向量化方式計(jì)算每個(gè)三角形的外接圓半徑。面積用叉積的模長(zhǎng)除以二最終半徑是三條邊長(zhǎng)的乘積除以四倍面積。輸出半徑分位數(shù)是為了讓你看到alpha 取 0.05 時(shí)等價(jià)于半徑閾值 20大部分三角形都會(huì)被保留邊界接近凸包alpha 取 0.5 時(shí)半徑閾值 2很多大三角形被刪掉邊界開(kāi)始出現(xiàn)凹形。這個(gè)分布直方圖會(huì)告訴你點(diǎn)集局部尺度避免盲目試錯(cuò)。參數(shù)說(shuō)明Delaunay 對(duì)象的 simplices 是三角形頂點(diǎn)索引數(shù)組形狀為(num_triangles, 3)直接用 numpy 切片即可得到三個(gè)頂點(diǎn)坐標(biāo)。注意面積接近 0 的退化三角形會(huì)讓 radius 變成無(wú)窮大這類三角形在后續(xù)過(guò)濾時(shí)會(huì)被自然刪除因?yàn)橥饨訄A太大。如果你處理三維點(diǎn)需要改成計(jì)算四面體外接球半徑公式更復(fù)雜但分布直方圖的思路不變也正是下一章要講的通用實(shí)現(xiàn)基礎(chǔ)。3. 實(shí)現(xiàn)“任何維度”基于 Delaunay 剖分的通用算法框架3.1 為什么 Delaunay 是 alpha shape 的地基Delaunay 剖分有一個(gè)關(guān)鍵特性它最大化所有三角形的最小角也就是盡量避免狹長(zhǎng)三角形。這個(gè)性質(zhì)讓外接球半徑計(jì)算更穩(wěn)定也讓剖分結(jié)構(gòu)在幾何上更貼近點(diǎn)集的真實(shí)拓?fù)?。alpha shape 直接建在 Delaunay 剖分上是因?yàn)槠史之a(chǎn)生的單純形集合是有限的、可數(shù)的而且包含凸包的全部信息。對(duì)每個(gè)單純形做外接球半徑過(guò)濾就能得到從凸包到點(diǎn)集本身的一系列嵌套形狀這個(gè)嵌套關(guān)系在學(xué)術(shù)上被稱為 alpha 復(fù)形。實(shí)際開(kāi)發(fā)中Delaunay 剖分也承擔(dān)了“鄰近關(guān)系”的角色。點(diǎn)與點(diǎn)之間哪些該連起來(lái)不是靠歐氏距離硬編碼而是由剖分自動(dòng)決定。這樣 alpha shape 對(duì)點(diǎn)密度有一定自適應(yīng)能力在稠密區(qū)域保留更多細(xì)節(jié)在稀疏區(qū)域自動(dòng)少連線前提是 alpha 選得恰當(dāng)。如果你不用 Delaunay 而直接求所有點(diǎn)對(duì)距離再按半徑連線那本質(zhì)上是在做半徑圖得到的東西不叫 alpha shape邊界也會(huì)混亂得多。另一個(gè)容易被忽視的點(diǎn)Delaunay 剖分在高維仍有嚴(yán)格定義這也讓“任何維度”成為可能。給定 d 維點(diǎn)集剖分把空間切成 d1 個(gè)頂點(diǎn)構(gòu)成的單純形。二維是三角形三維是四面體四維是五胞體。只要維度不高到內(nèi)存崩掉這些單純形都能用統(tǒng)一的方式表達(dá)和遍歷。所以后續(xù)的過(guò)濾與邊界提取完全不關(guān)心具體維度只關(guān)心“頂點(diǎn)索引”。3.2 通用流程剖分 → 過(guò)濾 → 輸出關(guān)鍵代碼與參數(shù)一個(gè)維度無(wú)關(guān)的 alpha shape 核心流程分三步Delaunay 剖分、按外接球半徑過(guò)濾、提取邊界面。先看最簡(jiǎn)單的過(guò)濾核心它返回保留下來(lái)的單純形列表import numpy as np from scipy.spatial import Delaunay def circumradius(vertices): 任意維度單純形的外接球半徑以第一個(gè)頂點(diǎn)為原點(diǎn) p0 vertices[0] mat vertices[1:] - p0 # (d, d) b 0.5 * np.einsum(ij,ij-i, mat, mat) # 1/2 * |v|^2 try: c np.linalg.solve(mat, b) # 球心相對(duì) p0 的坐標(biāo) except np.linalg.LinAlgError: return np.inf return np.linalg.norm(c) def keep_simplices(points, alpha): dela Delaunay(points) threshold 1.0 / alpha if alpha 0 else np.inf kept [] for s in dela.simplices: r circumradius(points[s]) if r threshold: kept.append(s) return np.array(kept)邏輯說(shuō)明頂點(diǎn)數(shù)必須是維度加一所以 vertices 去掉第一個(gè)后得到方陣 mat。方程 2 * v_i · c |v_i|^2 的解 c 就是球心相對(duì)第一個(gè)頂點(diǎn)的坐標(biāo)半徑就是 c 的模長(zhǎng)。如果解線性方程失敗說(shuō)明這組頂點(diǎn)退化外接球半徑視為無(wú)窮大自然被過(guò)濾這也是對(duì)重復(fù)點(diǎn)、共面點(diǎn)的一種容錯(cuò)。參數(shù)說(shuō)明alpha 為正時(shí)閾值是 1/alpha。alpha 傳 0 時(shí) threshold 為 inf所有不退化的單純形都會(huì)保留結(jié)果等于凸包alpha 傳負(fù)數(shù)時(shí)多數(shù)實(shí)現(xiàn)會(huì)報(bào)錯(cuò)所以調(diào)用前先限制 alpha 為正。實(shí)際工程里我建議用 radius_threshold 作為內(nèi)部參數(shù)避免在多個(gè)模塊間傳遞 alpha 造成倒數(shù)混淆。只保留單純形還不夠真正的 alpha shape 需要邊界面。邊界面的提取技巧對(duì)所有維度一致一個(gè)內(nèi)部面會(huì)被兩個(gè)相鄰單純形共享而邊界面只被一個(gè)單純形包含。所以用計(jì)數(shù)器統(tǒng)計(jì)每個(gè)面出現(xiàn)的次數(shù)出現(xiàn)一次的就是邊界from collections import Counter def extract_boundary_facets(simplices): facet_counter Counter() for s in simplices: for remove_idx in range(len(s)): face tuple(sorted(np.delete(s, remove_idx))) facet_counter[face] 1 return [f for f, cnt in facet_counter.items() if cnt 1]邏輯說(shuō)明一個(gè) d 維單純形有 d1 個(gè)面每個(gè)面是去掉一個(gè)頂點(diǎn)后得到的 d-1 維單純形。把面的頂點(diǎn)索引排序后作為字典鍵統(tǒng)計(jì)所有單純形里每個(gè)面出現(xiàn)的次數(shù)。出現(xiàn)一次的面位于整體邊界出現(xiàn)兩次的面在兩個(gè)剖分體之間是內(nèi)部共享面。這個(gè)邏輯與維度無(wú)關(guān)二維提取的是邊三維提取的是三角形四維提取的是四面體。參數(shù)說(shuō)明np.delete(s, remove_idx) 會(huì)返回去掉一個(gè)索引后的數(shù)組sorted 是為了保證同一個(gè)面無(wú)論從哪個(gè)方向枚舉都能對(duì)應(yīng)到同一個(gè)鍵。這個(gè)去重技巧看起來(lái)簡(jiǎn)單但它是 alpha shape 通用實(shí)現(xiàn)里最容易出錯(cuò)的地方如果忘記排序相鄰單純形枚舉出的面順序不同會(huì)被當(dāng)成兩個(gè)不同面邊界提取就會(huì)多出大量偽邊界。3.3 維度無(wú)關(guān)的數(shù)據(jù)結(jié)構(gòu)與索引技巧alpha shape 的通用實(shí)現(xiàn)里最不推薦直接存點(diǎn)坐標(biāo)。原因很簡(jiǎn)單過(guò)濾和邊界提取只關(guān)心“哪些點(diǎn)連成單純形”和“鄰接關(guān)系”坐標(biāo)只是用來(lái)算外接球半徑和最終輸出。正確的做法是全程使用整數(shù)索引Delaunay.simplices 本身就是頂點(diǎn)索引數(shù)組所有中間結(jié)果都以索引為主最后需要輸出幾何文件時(shí)再把索引映射到坐標(biāo)。我在自己的代碼里會(huì)把一個(gè)單純形表示成 tuple 或 numpy 數(shù)組具體每個(gè)元素是頂點(diǎn)的全局索引。這樣做有三個(gè)好處一是內(nèi)存占用固定且小不會(huì)因?yàn)榫S度變化導(dǎo)致結(jié)構(gòu)變化二是邊界提取時(shí)用 Counter 對(duì) tuple 做字典鍵非?？烊呛苋菀缀投嗑€程、內(nèi)存映射配合。代價(jià)是你得時(shí)刻記得每個(gè)元素是索引而不是坐標(biāo)調(diào)試時(shí)打印不夠直觀所以我建議寫一個(gè) debug 函數(shù)把索引轉(zhuǎn)回坐標(biāo)再輸出。另一個(gè)實(shí)用的索引技巧是“全局索引 局部索引”兩層。Delaunay.simplices 中的索引是全局點(diǎn)索引而構(gòu)建每個(gè)單純形后vertices points[s] 會(huì)得到一個(gè)局部坐標(biāo)數(shù)組。在計(jì)算外接球半徑和提取面時(shí)局部坐標(biāo)只用于數(shù)值計(jì)算面提取則用全局索引。這樣兩個(gè)職責(zé)分開(kāi)代碼可讀性好也不會(huì)在后續(xù)重建網(wǎng)格時(shí)弄混頂點(diǎn)。3.4 算法復(fù)雜度和內(nèi)存邊界復(fù)雜度要分兩塊看Delaunay 剖分是主要瓶頸二維在平均情況下接近 O(n log n)三維會(huì)在意外的高常數(shù)下退化最壞情況可能接近 O(n^2)四維以上幾乎只靠有限的經(jīng)驗(yàn)數(shù)據(jù)。過(guò)濾和邊界提取相對(duì)便宜每個(gè)單純形做一次半徑計(jì)算和幾次面統(tǒng)計(jì)整體接近 O(m)m 是單純形數(shù)量。所以你會(huì)發(fā)現(xiàn)數(shù)據(jù)量在十萬(wàn)級(jí)時(shí)二維可以輕松跑三維需要留意剖面超過(guò)百萬(wàn)點(diǎn)最好先降采樣。內(nèi)存邊界更現(xiàn)實(shí)。Delaunay 剖分的內(nèi)存消耗不僅來(lái)自點(diǎn)和邊還有 Qhull 內(nèi)部的臨時(shí)結(jié)構(gòu)。三維十萬(wàn)點(diǎn)時(shí)內(nèi)存幾百 MB 很常見(jiàn)四維只放幾千個(gè)點(diǎn)都可能把內(nèi)存撐爆。我的經(jīng)驗(yàn)法則是三維點(diǎn)集超過(guò)二十萬(wàn)就考慮先降采樣或分塊四維點(diǎn)集超過(guò)五千就強(qiáng)烈建議降維。alpha shape 的參數(shù)再準(zhǔn)也救不了剖分建不出來(lái)的數(shù)據(jù)。另外要注意 scipy.spatial.Delaunay 在三維以上依賴 Qhull它對(duì)退化輸入非常敏感會(huì)直接拋出錯(cuò)誤。這部分不是 alpha shape 本身的問(wèn)題而是底層剖分庫(kù)的數(shù)值穩(wěn)定性邊界。如果你真的需要高維穩(wěn)定剖分可能需要引入更專業(yè)的計(jì)算幾何庫(kù)但那已經(jīng)超出這篇筆記的范圍一般項(xiàng)目里遇到這種需求更合理的做法是減小維度。4. 用 Python 跑通二維和三維最小可復(fù)現(xiàn)示例4.1 二維點(diǎn)集生成一個(gè)凹形輪廓并取出邊界現(xiàn)在我們用第二、三章的函數(shù)組合出一個(gè)完整的 alpha_shape 調(diào)用作用在二維點(diǎn)上。為了看出凹形效果我生成一個(gè)三瓣星形輪廓并在輪廓上取點(diǎn)再添加少量噪聲。import numpy as np from scipy.spatial import Delaunay from collections import Counter def circumradius(vertices): p0 vertices[0] mat vertices[1:] - p0 b 0.5 * np.einsum(ij,ij-i, mat, mat) try: c np.linalg.solve(mat, b) except np.linalg.LinAlgError: return np.inf return np.linalg.norm(c) def alpha_shape(points, alpha): dela Delaunay(points) threshold 1.0 / alpha if alpha 0 else np.inf simplices [] for s in dela.simplices: if circumradius(points[s]) threshold: simplices.append(s) facet_counter Counter() for s in simplices: for remove_idx in range(len(s)): face tuple(sorted(np.delete(s, remove_idx))) facet_counter[face] 1 return [f for f, cnt in facet_counter.items() if cnt 1] # 在三瓣星形曲線上采樣 300 個(gè)點(diǎn) theta np.linspace(0, 2 * np.pi, 300) r 1.0 0.35 * np.cos(3 * theta) pts np.stack([r * np.cos(theta), r * np.sin(theta)], axis1) boundary alpha_shape(pts, alpha0.35) print(邊界邊數(shù)量, len(boundary)) print(前 5 條邊頂點(diǎn)索引, boundary[:5])邏輯說(shuō)明alpha_shape 函數(shù)在二維會(huì)保留部分三角形再?gòu)倪@些小三角形的邊里找出只出現(xiàn)一次的邊作為邊界。當(dāng) alpha 取 0.35 時(shí)三瓣星形中間的凹槽會(huì)被保留下來(lái)邊界邊數(shù)量通常在 300 條左右接近采樣點(diǎn)數(shù)。如果 alpha 取 0.03跑出來(lái)的邊界會(huì)更接近凸包凹槽變淺邊界邊數(shù)量也會(huì)相應(yīng)減少。你可以把 alpha 改成 1.2會(huì)發(fā)現(xiàn)邊界碎成很多短線段說(shuō)明參數(shù)太大導(dǎo)致保留的三角形太少。參數(shù)說(shuō)明示例里采樣點(diǎn)沒(méi)有加噪聲所以外接球半徑分布比較干凈。實(shí)際項(xiàng)目中點(diǎn)云帶噪聲alpha 閾值要略大于點(diǎn)云局部鄰域的真實(shí)尺度。判斷手段就是先打印一張半徑分布直方圖然后選一個(gè)處于 70% 到 90% 分位數(shù)之間的半徑閾值再換算成 alpha。我在二維輪廓提取中用這個(gè)經(jīng)驗(yàn)基本不用反復(fù)試。4.2 三維點(diǎn)云從散點(diǎn)到封閉表面網(wǎng)格三維的用法與二維幾乎一致只是 Delaunay 剖分生成的是四面體邊界提取得到的是三角形面。用環(huán)面點(diǎn)云做示例環(huán)的中心有洞凸包會(huì)把這個(gè)洞填滿alpha shape 應(yīng)該恢復(fù)中空形狀。def sample_torus(R2.0, r0.8, n1200, seed1): rng np.random.default_rng(seed) theta 2 * np.pi * rng.random(n) phi 2 * np.pi * rng.random(n) x (R r * np.cos(phi)) * np.cos(theta) y (R r * np.cos(phi)) * np.sin(theta) z r * np.sin(phi) return np.stack([x, y, z], axis1) pts3d sample_torus() boundary3d alpha_shape(pts3d, alpha0.35) print(三維邊界三角形數(shù)量, len(boundary3d))邏輯說(shuō)明代碼直接在環(huán)面上隨機(jī)采樣 1200 個(gè)點(diǎn)alpha shape 過(guò)濾后留下的四面體會(huì)覆蓋環(huán)面周圍的一層殼內(nèi)部大空洞對(duì)應(yīng)的四面體外接球半徑過(guò)大會(huì)被過(guò)濾掉。extract_boundary_facets 返回的每條邊界是一個(gè)三角形三角形的三維坐標(biāo)可以通過(guò) pts3d[list(face)] 取回。這里 alpha 取 0.35 只是一個(gè)例子不同環(huán)面半徑和采樣密度需要重選。參數(shù)說(shuō)明三維比二維更敏感。alpha 稍微調(diào)大 0.1就可能出現(xiàn)成片空洞調(diào)小 0.1邊界三角形會(huì)明顯變多甚至開(kāi)始出現(xiàn)內(nèi)部小碎塊。我通常以邊界三角形數(shù)量作為反饋理想的三維 alpha shape 邊界三角形數(shù)量應(yīng)該接近“預(yù)期表面積 / 平均三角形面積”的 1.2 到 1.5 倍。如果數(shù)量突然翻倍多半是出現(xiàn)了內(nèi)部碎片需要調(diào)大 alpha。4.3 高于三維用同一個(gè)類處理四維/五維數(shù)據(jù)如果你真的需要四維 alpha shape同一個(gè)函數(shù)可以直接跑但數(shù)據(jù)量要嚴(yán)格控制。下面示例生成一個(gè)四維超球面上的 800 個(gè)點(diǎn)然后提取邊界邊界面應(yīng)該是三維單純形也就是四面體。rng np.random.default_rng(7) pts4d rng.normal(size(800, 4)) pts4d / np.linalg.norm(pts4d, axis1, keepdimsTrue) boundary4d alpha_shape(pts4d, alpha1.0) print(四維邊界四面體數(shù)量, len(boundary4d))邏輯說(shuō)明四維超球面的 Delaunay 剖分元素?cái)?shù)量遠(yuǎn)多于三維800 個(gè)點(diǎn)已經(jīng)會(huì)讓剖分花費(fèi)幾秒到幾十秒。alpha 取 1.0 在這里意味著半徑閾值 1.0超球面的單位半徑會(huì)被完整保留邊界提取得到的是三維單純形。這些單純形無(wú)法直接三維可視化但可以用于后續(xù)拓?fù)浞治隼缬?jì)算 4D 超體積、統(tǒng)計(jì)邊界連通性。參數(shù)說(shuō)明四維數(shù)據(jù)的數(shù)值穩(wěn)定性比三維差很多我建議先對(duì)數(shù)據(jù)做中心化和歸一化否則外接球半徑計(jì)算可能因?yàn)閿?shù)值范圍差異出現(xiàn)大量 inf導(dǎo)致邊界為空。如果 alpha_shape 返回空列表不要急著調(diào) alpha先檢查數(shù)據(jù)是否退化或者把 alpha 改大試試。真實(shí)項(xiàng)目中五維數(shù)據(jù)基本只能跑幾十個(gè)點(diǎn)超過(guò)一百個(gè)點(diǎn)就可能內(nèi)存溢出。4.4 落成文件邊界邊、三角網(wǎng)格和中間量做完邊界提取最終要落盤才能交給下游。二維邊界可以保存成 CSV三維邊界是三角形可以直接寫成 OBJ 文件更高維邊界則保存為 npz 或二進(jìn)制數(shù)組。這里給一個(gè)最簡(jiǎn)的三維 OBJ 寫入函數(shù)def write_boundary_obj(path, points, boundary_facets): with open(path, w) as f: for p in points: f.write(fv {p[0]:.6f} {p[1]:.6f} {p[2]:.6f}\n) for face in boundary_facets: # OBJ 面索引從 1 開(kāi)始 f.write(ff {face[0]1} {face[1]1} {face[2]1}\n)邏輯說(shuō)明三維 boundary_facets 里每個(gè)元素是一個(gè)三角形包含三個(gè)頂點(diǎn)索引寫 OBJ 時(shí)把索引加一即可。如果 boundary_facets 中存在重復(fù)或退化三角形OBJ 也能寫出來(lái)但大多數(shù)三維軟件會(huì)顯示異常。所以寫文件前最好做一次去重和面積過(guò)濾去掉面積接近零的三角形。參數(shù)說(shuō)明對(duì)于二維邊界face 只有兩個(gè)頂點(diǎn)寫 CSV 更合適四維邊界的四面體如果要落盤我建議直接保存頂點(diǎn)索引矩陣后續(xù)分析時(shí)再按需轉(zhuǎn)成其他格式。不要用 OBJ 存四維數(shù)據(jù)會(huì)丟失維度語(yǔ)義。5. alpha shape 參數(shù)調(diào)優(yōu)與避坑常見(jiàn)問(wèn)題和排查思路5.1 alpha 值等于 0、無(wú)窮大或負(fù)數(shù)行為差異很大現(xiàn)象alpha 設(shè)置為 0我原本以為會(huì)得到最細(xì)碎的邊界結(jié)果返回了一個(gè)凸包設(shè)置為負(fù)數(shù)時(shí)直接報(bào)錯(cuò)設(shè)置為極大的數(shù)時(shí)邊界變成一堆破碎短邊。原因alpha 與半徑閾值是倒數(shù)關(guān)系。alpha 為 0 時(shí)閾值無(wú)窮大所有 Delaunay 單純形都會(huì)保留其最外層自然就是凸包alpha 為負(fù)數(shù)在幾何上對(duì)應(yīng)“空腔”的補(bǔ)集大多數(shù)實(shí)現(xiàn)沒(méi)有定義alpha 極大時(shí)閾值極小只有極少數(shù)小外接球單純形能保留邊界就會(huì)散架。解決把 alpha 視為正數(shù)參數(shù)默認(rèn)從點(diǎn)集邊長(zhǎng)尺度反推。想要凸包就用凸包算法不要通過(guò) alpha 置零來(lái)實(shí)現(xiàn)。代碼入口處對(duì) alpha 做斷言alpha 0 時(shí)直接拋異常省得下游數(shù)據(jù)源傳錯(cuò)參數(shù)導(dǎo)致邊界靜默錯(cuò)誤。5.2 數(shù)值精度引起空腔與孤立點(diǎn)邊界出現(xiàn)小洞現(xiàn)象同一個(gè)點(diǎn)云今天跑出完整性很好的邊界明天換成 float32 類型后中間出現(xiàn)許多小洞或孤立點(diǎn)邊界不再連續(xù)。原因外接球半徑計(jì)算依賴線性方程組求解浮點(diǎn)精度不足時(shí)接近退化的單純形會(huì)把半徑算成非常大或 inf被過(guò)濾掉形狀上就表現(xiàn)為空洞。更高維度下這個(gè)問(wèn)題更明顯。解決所有計(jì)算統(tǒng)一用 float64輸入數(shù)據(jù)如果是 float32 要顯式轉(zhuǎn)換。同時(shí)在剖分前做去重合并距離小于 1e-12 的重復(fù)點(diǎn)。如果還有空洞可以設(shè)定一個(gè)小的容差閾值將半徑小于 threshold 的 1.01 倍而不是 threshold 的單純形保留犧牲一點(diǎn)細(xì)節(jié)換取連通性。5.3 點(diǎn)密度不均時(shí)邊界斷裂稀疏區(qū)域被刪成斷層現(xiàn)象點(diǎn)云在角落附近采樣很稀疏在中間區(qū)域很密。alpha 取中等值時(shí)稀疏區(qū)域邊界一個(gè)大洞整個(gè)形狀被分成幾塊。原因alpha shape 的半徑閾值是全局的稀疏區(qū)域外接球半徑天然偏大按全局閾值過(guò)濾時(shí)這些單純形會(huì)被刪掉。解決先估計(jì)局部點(diǎn)距用中位數(shù)點(diǎn)距的 2 到 3 倍作為半徑閾值再換算成 alpha而不是直接拍腦袋。更徹底的方案是先用最近鄰插值或重采樣把密度拉勻再跑 alpha shape。不過(guò)在工程實(shí)踐中我經(jīng)常選擇保留“分塊”結(jié)果每個(gè)連通塊單獨(dú)輸出邊界而不是強(qiáng)行求一個(gè)完整邊界。5.4 大規(guī)模點(diǎn)集內(nèi)存爆炸Delaunay 剖分吃光內(nèi)存現(xiàn)象五十萬(wàn)點(diǎn)三維點(diǎn)云跑剖分程序進(jìn)程在幾秒內(nèi)內(nèi)存占用突破幾個(gè) GB然后被系統(tǒng)殺掉。原因Delaunay 剖分在三維的復(fù)雜度雖然平均接近線性但常數(shù)非常大尤其是表面點(diǎn)云Qhull 會(huì)產(chǎn)生大量四面體。alpha shape 的過(guò)濾本身并不重重的是剖分階段。解決先用 voxel 降采樣把點(diǎn)云降到十萬(wàn)以內(nèi)或者用 alpha 的大尺度初篩把明顯內(nèi)部的點(diǎn)去掉。如果業(yè)務(wù)必須全量點(diǎn)云考慮分塊處理把空間切成若干個(gè)重疊塊每塊做 alpha shape再按重疊區(qū)合并邊界。別指望調(diào)一調(diào) alpha 能讓內(nèi)存降下來(lái)內(nèi)存瓶頸在剖分不在過(guò)濾。5.5 和凸包、凹包、滾球法混用時(shí)的誤區(qū)以為是同一個(gè)東西現(xiàn)象看到“凹包”工具 docstring 里寫著 concave hull就把 alpha 參數(shù)填進(jìn)去結(jié)果結(jié)果完全不可控還有人拿滾球法的半徑參數(shù)直接當(dāng) alpha 用。原因凹包算法有兩派基于 Delaunay 的 alpha shape以及基于 k 近鄰的滾球法。滾球法里的球半徑就是外接圓的物理半徑等于 alpha shape 的 1/alpha有的人把這兩個(gè)名字混填導(dǎo)致結(jié)果完全違背預(yù)期。解決先確認(rèn)你用的庫(kù)里參數(shù)是 alpha 還是 radius。如果是 radius內(nèi)部換算通常是alpha 1.0 / radius。接到自己的代碼里統(tǒng)一暴露 radius 參數(shù)內(nèi)部轉(zhuǎn)成 alpha 再用本文的實(shí)現(xiàn)計(jì)算。這樣下游調(diào)用的人不會(huì)因?yàn)榈箶?shù)關(guān)系翻車。6. 進(jìn)階如何用 alpha shape 做體積估算和質(zhì)量檢查alpha shape 不僅能畫邊界還能當(dāng)度量工具。三維點(diǎn)云體積估算可以跳過(guò)表面重建直接用保留下來(lái)的四面體求有符號(hào)體積之和。這個(gè)做法比先重建表面再求積分更穩(wěn)因?yàn)樗粫?huì)因?yàn)楸砻媪芽p產(chǎn)生體積丟失。以下是一個(gè)對(duì)第 3 章 keep_simplices 結(jié)果的體積計(jì)算def alpha_volume(points, retained_simplices): vol 0.0 for s in retained_simplices: tet points[s] # 以第一個(gè)頂點(diǎn)為原點(diǎn)另外三個(gè)頂點(diǎn)構(gòu)成矩陣 mat tet[1:] - tet[0] vol abs(np.linalg.det(mat)) / 6.0 return vol邏輯說(shuō)明一個(gè)四面體的體積 行列式絕對(duì)值除以 6。把所有被 alpha 過(guò)濾保留的四面體體積加起來(lái)就是這個(gè) alpha 值對(duì)應(yīng)的多面體體積。alpha 很小的時(shí)候體積接近凸包體積alpha 慢慢變大但還沒(méi)撕裂點(diǎn)云時(shí)體積會(huì)略小于凸包如果實(shí)際物體是中空的體積會(huì)明顯下降這個(gè)差值可以作為空心度指標(biāo)。我用這個(gè)體積做質(zhì)量檢查的思路很簡(jiǎn)單對(duì)同一份點(diǎn)云跑兩個(gè) alpha 值一個(gè)給出近凸包的粗糙體積一個(gè)給出細(xì)節(jié)體積。如果兩者差異超過(guò) 20%說(shuō)明點(diǎn)云形狀里存在大量凹形結(jié)構(gòu)可能是物體本身復(fù)雜也可能是采集時(shí)遮擋導(dǎo)致。配合連通塊數(shù)量能快速判斷哪些掃描片段出了問(wèn)題。多尺度 alpha 的取值習(xí)慣我在生產(chǎn)環(huán)境里是這樣做的先取 alpha 等于 0.5 倍中位數(shù)點(diǎn)距的倒數(shù)得到保守邊界再把 alpha 乘 2 得到精細(xì)邊界最后比較兩個(gè)邊界的體積和三角形數(shù)量。如果精細(xì)邊界的三角形數(shù)量暴增但體積變化很小說(shuō)明你只是在逼近噪聲而不是逼近真實(shí)表面這時(shí)取保守值就好。這個(gè)“三角數(shù)量暴增、體積變化小”的現(xiàn)象是 alpha shape 里最常見(jiàn)的過(guò)擬合信號(hào)。最后說(shuō)一個(gè)我自己的教訓(xùn)別迷信一個(gè) alpha 走天下。同一個(gè)數(shù)據(jù)集換了掃描設(shè)備或者采樣密度最優(yōu) alpha 一定變。最讓我后悔的一次是把一套點(diǎn)云的 alpha 調(diào)得很漂亮然后直接套到另一套數(shù)據(jù)上輸出一堆廢片。后來(lái)我養(yǎng)成了一個(gè)習(xí)慣任何新數(shù)據(jù)都先跑一遍半徑分布直方圖再看一眼連通塊數(shù)量再?zèng)Q定 alpha整個(gè)過(guò)程不到兩分鐘。這個(gè)習(xí)慣幫我省掉的返工時(shí)間遠(yuǎn)遠(yuǎn)超過(guò)最初學(xué) alpha shape 的時(shí)間希望也能幫到你。本文還有配套的精品資源點(diǎn)擊獲取