簡(jiǎn)介基于C實(shí)現(xiàn)的增量Delaunay三角剖分算法工程包面向計(jì)算幾何學(xué)習(xí)者與需要處理三角網(wǎng)格的C開(kāi)發(fā)者。算法逐點(diǎn)插入并局部翻邊使剖分中所有三角形的最小角盡量最大化項(xiàng)目采用石溪大學(xué)顧賢峰教授提出的“半邊”數(shù)據(jù)結(jié)構(gòu)組織網(wǎng)格適合想深入理解幾何拓?fù)鋵?shí)現(xiàn)的人群。壓縮包共89個(gè)文件、4.17MB包含13個(gè)h頭文件、1個(gè)cpp主實(shí)現(xiàn)位于GaussCurvature_Sample/GaussCurvature/main.cpp、Visual Studio解決方案與工程文件、已編譯的exe及構(gòu)建日志可直接打開(kāi)工程運(yùn)行或按需拆解調(diào)用。已有1003人瀏覽/學(xué)習(xí)。讀者可拿到完整可編譯的Delaunay三角剖分示例厘清增量插入、局部邊翻轉(zhuǎn)與半邊結(jié)構(gòu)維護(hù)的配合關(guān)系還可參考其網(wǎng)格類(lèi)封裝方式遷移到其他幾何算法項(xiàng)目中。1. Delaunay三角剖分為什么“最不尖銳”的網(wǎng)格要靠局部操作來(lái)維護(hù)給一堆散點(diǎn)Delaunay三角剖分能生成一張“盡可能勻稱(chēng)”的三角形網(wǎng)格任何三角形的外接圓內(nèi)都不允許出現(xiàn)第四個(gè)點(diǎn)。這個(gè)空?qǐng)A準(zhǔn)則聽(tīng)起來(lái)是全局約束——每一圈網(wǎng)格都要滿足它。但真正讓增量算法工程可用的是一條反直覺(jué)的性質(zhì)往一張幾十萬(wàn)個(gè)三角形的網(wǎng)格里插入一個(gè)新點(diǎn)需要修改的只是和它相鄰的一小片區(qū)域。把其中不合法的那條邊翻一下整個(gè)網(wǎng)格的空?qǐng)A條件便自動(dòng)恢復(fù)。于是插入一個(gè)點(diǎn)的過(guò)程可以被拆成定位、拆分、翻邊三步每一步都只圍繞新點(diǎn)的局部鄰域做文章。搞懂這三步背后的幾何機(jī)制和C實(shí)現(xiàn)取舍才算真正明白這個(gè)算法為什么能work又為什么在某些輸入上會(huì)翻車(chē)。2. 增量插入機(jī)制一點(diǎn)擾動(dòng)為什么不會(huì)波及整張網(wǎng)格2.1 局部 Delaunay 邊與空?qǐng)A條件的等價(jià)關(guān)系增量算法的正確性基石是“局部 Delaunay 邊”這個(gè)概念。取一條共享邊 AB兩側(cè)分別是三角形 ABC 和 ABD。如果 D 落在三角形 ABC 的外接圓內(nèi)部邊 AB 就是非法的反之如果四邊形 ACBD 是凸的且 D 在 ABC 外接圓外部AB 就是合法的。這個(gè)判定與全局空?qǐng)A條件之間有一個(gè)重要等價(jià)當(dāng)網(wǎng)格中所有內(nèi)部邊都滿足局部 Delaunay 條件時(shí)整張網(wǎng)格就是全局 Delaunay 的。這意味著修復(fù)可以完全局部化。插入一個(gè)點(diǎn)之后受影響的非法邊一定與包含新點(diǎn)的三角形相鄰不存在隔空被破壞的邊。因?yàn)榭請(qǐng)A條件和局部判定等價(jià)所以只要逐條處理非法邊就能恢復(fù)全局性質(zhì)不需要掃描全圖。增量算法里那句口頭禪可以這么記誰(shuí)碰了新點(diǎn)就查誰(shuí)的外接圓。這個(gè)結(jié)論也解釋了算法偽代碼為什么那么短。初始化超級(jí)三角形然后逐個(gè)插入點(diǎn)每插一個(gè)點(diǎn)只做局部修復(fù)最后刪掉超級(jí)三角形——主循環(huán)就這么幾行。真正的工作量全部藏在“如何快速定位”“如何判斷一條邊是否合法”和“如何翻邊而不弄錯(cuò)鄰居關(guān)系”里。2.2 步行法定位點(diǎn)與三角形的包含關(guān)系插入新點(diǎn)后的第一件事是找到它落在哪個(gè)現(xiàn)有三角形內(nèi)部。最樸素的做法是遍歷全部三角形做包含測(cè)試每次 O(n)在幾十萬(wàn)點(diǎn)的規(guī)模下完全不可接受。工程實(shí)現(xiàn)里更常用的是步行法walking algorithm從某個(gè)已知三角形出發(fā)逐步向目標(biāo)點(diǎn)移動(dòng)。每一步檢查目標(biāo)點(diǎn) p 相對(duì)當(dāng)前三角形三條邊的位置。三角形按逆時(shí)針存儲(chǔ)頂點(diǎn)如果 p 在某條有向邊的右側(cè)就說(shuō)明應(yīng)該從這條邊跨到對(duì)面的鄰居三角形去。直到 p 位于三條邊的同一側(cè)也就是落在當(dāng)前三角形內(nèi)部定位結(jié)束。int locatePoint(const vectorPoint pts, const vectorTri tris, const Point p, int start) { int t start; for (int guard 0; guard (int)tris.size() * 4; guard) { bool inside true; for (int i 0; i 3; i) { int a tris[t].v[i]; int b tris[t].v[(i 1) % 3]; double o orient2d(p, pts[a], pts[b]); if (o 0) { // p 在邊 (a,b) 的右側(cè) int next tris[t].n[i]; if (next 0) return t; // 理論上不會(huì)走到邊界 t next; inside false; break; } } if (inside) return t; } return t; // 保護(hù)性退出正常不會(huì)執(zhí)行到這里 }這里的orient2d(p, a, b)是計(jì)算幾何里的方向測(cè)試返回正值表示 p 在從 a 到 b 的有向邊左側(cè)負(fù)值表示右側(cè)。三角形頂點(diǎn)按逆時(shí)針存儲(chǔ)時(shí)如果 p 在三條邊的左側(cè)就說(shuō)明它在三角形內(nèi)部。每跨一步離目標(biāo)三角形都更近一點(diǎn)只要網(wǎng)格拓?fù)湔_這個(gè)過(guò)程必然收斂。代碼里的 guard 循環(huán)上限是必須的。步行法理論上最壞走 O(n) 步但浮點(diǎn)誤差可能讓判斷在兩條邊的臨界處來(lái)回振蕩不加保護(hù)會(huì)死循環(huán)。生產(chǎn)實(shí)現(xiàn)里還有一種常見(jiàn)優(yōu)化把 forbreak 展開(kāi)成三次順序判斷省掉分支跳轉(zhuǎn)。在幾十萬(wàn)點(diǎn)的規(guī)模下這個(gè)細(xì)節(jié)能帶來(lái)可感知的定位速度差異。2.3 三角形拆分與級(jí)聯(lián)翻邊定位完成后新點(diǎn) p 落在三角形 ABC 內(nèi)。先把 ABC 從網(wǎng)格中摘除再用 p 與 A、B、C 生成三個(gè)新三角形 ABp、BCp、CAp。幾何上這一步等于把舊三角形劈成三塊開(kāi)銷(xiāo)很小。但劈完之后新三角形可能與它的鄰居構(gòu)成共邊四邊形比如三角形 ABp 與鄰居 ABD 共享邊 AB如果 D 落在三角形 ABp 的外接圓內(nèi)AB 就不再是合法邊。這時(shí)需要翻邊f(xié)lip把共享邊 AB 換成 Dp兩個(gè)三角形變成 ADp 和 DBp。翻邊之后新的 ADp 邊或 DBp 邊可能又讓更外圈的三角形不合法于是翻邊必須遞歸進(jìn)行。這個(gè)遞歸過(guò)程像漣漪一樣向外擴(kuò)散但因?yàn)榉欠ㄟ呏荒苎刂曼c(diǎn)的區(qū)域傳播擴(kuò)散范圍被限制在鄰域內(nèi)。翻邊必然會(huì)終止原因在于它等價(jià)于“選擇正確的對(duì)角線”。對(duì)一個(gè)凸四邊形兩條對(duì)角線中恰好有一條滿足局部 Delaunay 條件。每翻一次邊四邊形內(nèi)的最小角嚴(yán)格變大而網(wǎng)格三角形總數(shù)不變所以遞歸深度存在上界。隨機(jī)順序插入時(shí)這個(gè)深度的期望值接近常數(shù)這也正是增量算法平均效率的關(guān)鍵所在。2.4 一個(gè)完整插入序列的動(dòng)線把定位、拆分、翻邊串起來(lái)一次插入完整流程可以概括為int t locatePoint(pts, tris, newPt, lastTriangle); int a tris[t].v[0], b tris[t].v[1], c tris[t].v[2]; // 創(chuàng)建三個(gè)新三角形手工維護(hù)鄰居關(guān)系 // 刪除舊三角形 t // 對(duì)三個(gè)新三角形分別執(zhí)行 legalize legalizeTriangle(ta, 1); legalizeTriangle(tb, 1); legalizeTriangle(tc, 1);每個(gè)legalizeTriangle處理一塊共享邊如果是內(nèi)部邊且不滿足局部 Delaunay 條件就翻邊然后對(duì)新形成的兩條邊繼續(xù)遞歸。每次插入的“動(dòng)線”都完全一致先定位到包含新點(diǎn)的三角形把它拆開(kāi)再把新點(diǎn)帶來(lái)的非法邊一條條修好。整個(gè)增量算法的骨架到這里就清楚了剩下的難點(diǎn)全在數(shù)據(jù)結(jié)構(gòu)——鄰居關(guān)系怎么存、翻邊時(shí)如何精準(zhǔn)地改寫(xiě)四個(gè)三角形的連接信息。這部分放到下一章展開(kāi)。3. C 實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)、幾何謂詞與翻邊的源碼級(jí)拆解3.1 三角形的數(shù)據(jù)表示頂點(diǎn)數(shù)組加鄰居數(shù)組增量算法里最常用的三角形結(jié)構(gòu)是頂點(diǎn)數(shù)組加鄰居數(shù)組struct Tri { int v[3]; // 頂點(diǎn)索引按逆時(shí)針排列 int n[3]; // 鄰居索引n[i] 是邊 (v[i], v[(i1)%3]) 對(duì)面的三角形 };例如n[0]表示與邊(v[0], v[1])共享的鄰居三角形。如果某條邊沒(méi)有鄰居說(shuō)明它是當(dāng)前網(wǎng)格的邊界邊用 -1 表示。為什么用 int 索引而不是指針第一個(gè)原因是 vector 擴(kuò)容時(shí)元素地址會(huì)移動(dòng)裸指針全部失效索引不會(huì)。第二個(gè)原因是內(nèi)存局部性一個(gè) Tri 占 24 字節(jié)存放在連續(xù)數(shù)組里幾十萬(wàn)個(gè)三角形遍歷時(shí)緩存命中率遠(yuǎn)高于用 new 逐個(gè)分配的散落對(duì)象。第三個(gè)原因是翻邊時(shí)要頻繁改寫(xiě)鄰居指向索引賦值就是一次 int 拷貝比指針更簡(jiǎn)單也更安全。這個(gè)結(jié)構(gòu)有一個(gè)隱藏約定v 數(shù)組的排列順序必須始終是逆時(shí)針。所有幾何謂詞和鄰居關(guān)系都依賴(lài)這個(gè)約定。一旦某個(gè)三角形變成順時(shí)針后面的翻邊條件會(huì)整體取反產(chǎn)生難以排查的鏡像網(wǎng)格。3.2 orient2d 與 inCircle兩個(gè)決定正確性的幾何謂詞方向測(cè)試orient2d是全部幾何判斷的地基。它計(jì)算的是向量 AB 和 AC 的叉積double orient2d(const Point a, const Point b, const Point c) { return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); }返回值大于零表示 c 在 b 的左側(cè)即三角形 (a,b,c) 為逆時(shí)針。定位、翻邊前的凸四邊形檢查、超三角形頂點(diǎn)選擇都依賴(lài)這個(gè)函數(shù)的符號(hào)。外接圓判斷inCircle是另一個(gè)核心謂詞。它判斷第四個(gè)點(diǎn) d 落在三角形 abc 的外接圓內(nèi)還是圓外。直接計(jì)算圓心半徑再比較距離當(dāng)然可行但更高效的做法是構(gòu)造一個(gè)四階行列式double inCircle(const Point a, const Point b, const Point c, const Point d) { double adx a.x - d.x, ady a.y - d.y; double bdx b.x - d.x, bdy b.y - d.y; double cdx c.x - d.x, cdy c.y - d.y; double abd adx * bdy - ady * bdx; double bcd bdx * cdy - bdy * cdx; double cad cdx * ady - cdy * adx; double alift adx * adx ady * ady; double blift bdx * bdx bdy * bdy; double clift cdx * cdx cdy * cdy; return alift * bcd blift * cad clift * abd; }先做坐標(biāo)平移把 d 作為原點(diǎn)能有效減小坐標(biāo)值的絕對(duì)大小從而降低浮點(diǎn)誤差。符號(hào)約定是a、b、c 逆時(shí)針排列時(shí)返回正表示 d 在圓外返回負(fù)表示在圓內(nèi)。這兩個(gè)謂詞的實(shí)現(xiàn)都不復(fù)雜但它們共同決定了算法會(huì)不會(huì)在某個(gè)角落靜默地生成非法三角形。3.3 拆分三角形時(shí)的鄰居接線插入新點(diǎn) p 到三角形 ABC 內(nèi)部時(shí)舊三角形被替換成三個(gè)新三角形。最清晰的實(shí)現(xiàn)方式是先算出舊三角形三個(gè)頂點(diǎn)的索引再按固定模式創(chuàng)建新三角形void insertPoint(int pi) { int t0 locatePoint(pts, tris, pts[pi], lastTriangle); const Tri old tris[t0]; int a old.v[0], b old.v[1], c old.v[2]; // 新三角形 tA 的頂點(diǎn)順序?yàn)?(a, b, pi) // 新三角形 tB 的頂點(diǎn)順序?yàn)?(b, c, pi) // 新三角形 tC 的頂點(diǎn)順序?yàn)?(c, a, pi) // 每個(gè)新三角形的鄰居需要同時(shí)連接舊鄰居和另外兩個(gè)新三角形 }創(chuàng)建時(shí)最需要注意的是內(nèi)部接線三個(gè)新三角形之間互連形成一個(gè)小環(huán)。例如 tA 的邊 (b, pi) 對(duì)面是 tB邊 (pi, a) 對(duì)面是 tC。手工寫(xiě)這三個(gè)三角形的鄰居數(shù)組極易出錯(cuò)一個(gè)常見(jiàn)的做法是先統(tǒng)一置 -1再用一個(gè)輔助函數(shù)linkTri把兩個(gè)三角形在指定邊上互相指向?qū)Ψ絭oid linkTri(int t1, int e1, int t2, int e2) { tris[t1].n[e1] t2; tris[t2].n[e2] t1; }然后把拆分時(shí)的所有鄰居關(guān)系寫(xiě)成一行行的linkTri調(diào)用。代碼雖然長(zhǎng)但每行只做一件事出錯(cuò)了也容易定位。這類(lèi)“接線錯(cuò)誤”不會(huì)立刻報(bào)錯(cuò)而是會(huì)在后續(xù)翻邊或輸出網(wǎng)格時(shí)以拓?fù)鋽嗔训男问匠霈F(xiàn)排查起來(lái)非常耗時(shí)。3.4 legalize 與 flip 的源碼實(shí)現(xiàn)legalize負(fù)責(zé)檢查和修復(fù)一條共享邊。它的輸入是一個(gè)三角形索引和一條邊的索引int thirdVertex(const Tri tri, int u, int v) { for (int i 0; i 3; i) { if (tri.v[i] ! u tri.v[i] ! v) return tri.v[i]; } return -1; } void legalize(int t, int e) { int nb tris[t].n[e]; if (nb 0) return; // 邊界邊直接返回 int u tris[t].v[e]; int v tris[t].v[(e 1) % 3]; int w tris[t].v[(e 2) % 3]; int z thirdVertex(tris[nb], u, v); if (inCircle(pts[u], pts[v], pts[w], pts[z]) 0) { flip(t, e, nb, u, v, w, z); // 需要翻邊 } }flip把共享邊為 uv 的兩個(gè)三角形第三頂點(diǎn)分別是 w 和 z替換成共享邊為 wz 的兩個(gè)新三角形。實(shí)現(xiàn)時(shí)要特別注意新三角形的頂點(diǎn)必須重新排成逆時(shí)針并且四個(gè)鄰居關(guān)系要整體重接。另一種更穩(wěn)妥的寫(xiě)法是“先斷后連”先把四個(gè)相關(guān)三角形的鄰居索引清零再按新拓?fù)渲匦耹inkTri。少做一步殘留的舊鄰居索引就會(huì)讓下一次legalize讀到錯(cuò)誤的三角形。翻邊之后新形成的兩條邊可能又和它們的鄰居發(fā)生沖突所以flip內(nèi)部還需要對(duì)兩條新邊遞歸調(diào)用legalize。這與 2.3 節(jié)說(shuō)的級(jí)聯(lián)翻邊是對(duì)應(yīng)的。遞歸深度由最小角增大性質(zhì)保證有界不會(huì)棧溢出。3.5 超級(jí)三角形與收尾清理增量算法需要一塊初始地盤(pán)作為定位起點(diǎn)這就是超級(jí)三角形。它要覆蓋所有輸入點(diǎn)最常用的構(gòu)造方式是先算輸入點(diǎn)集的包圍盒把中心作為三角形重心再向外擴(kuò)到對(duì)角線長(zhǎng)度的兩倍左右。Point minP pts[0], maxP pts[0]; for (auto p : pts) { minP.x std::min(minP.x, p.x); minP.y std::min(minP.y, p.y); maxP.x std::max(maxP.x, p.x); maxP.y std::max(maxP.y, p.y); } double d std::sqrt((maxP.x - minP.x) * (maxP.x - minP.x) (maxP.y - minP.y) * (maxP.y - minP.y)); Point c { (minP.x maxP.x) / 2.0, (minP.y maxP.y) / 2.0 }; // 三個(gè)頂點(diǎn)圍繞 c半徑取 2d 左右超級(jí)三角形的頂點(diǎn)索引一般從 n 開(kāi)始保存n 是原始輸入點(diǎn)數(shù)。當(dāng)所有點(diǎn)都插入完畢后任何包含超級(jí)三角形頂點(diǎn)的三角形都必須刪除剩下的就是最終 Delaunay 網(wǎng)格。int n pts.size(); for (auto it tris.begin(); it ! tris.end(); ) { if (it-v[0] n || it-v[1] n || it-v[2] n) { it tris.erase(it); } else { it; } }這一步看似簡(jiǎn)單但它隱藏了一個(gè)細(xì)節(jié)刪除超級(jí)三角形后原來(lái)與超級(jí)三角形相接的邊界邊會(huì)暴露出來(lái)成為凸包邊界。如果插入順序或翻邊過(guò)程有過(guò)任何輕微錯(cuò)誤這里往往會(huì)出現(xiàn)外掛的碎片三角形一眼就能看出網(wǎng)格不對(duì)。4. 避坑指南增量 Delaunay 最容易翻車(chē)的五個(gè)細(xì)節(jié)4.1 inCircle 符號(hào)約定與頂點(diǎn)繞序不一致現(xiàn)象網(wǎng)格生成過(guò)程幾乎正常但輸出結(jié)果像是被鏡像了部分三角形重疊或者某些內(nèi)部邊缺失。原因inCircle返回值的符號(hào)依賴(lài)三角形頂點(diǎn)的繞序。三角形按逆時(shí)針存儲(chǔ)時(shí)返回負(fù)表示第四點(diǎn)在圓內(nèi)如果某個(gè)三角形的頂點(diǎn)被存成順時(shí)針?lè)?hào)恰好互換翻邊條件整體取反等于一直在維護(hù)“局部非 Delaunay”網(wǎng)格。解決在每次創(chuàng)建三角形后加一個(gè) debug 斷言檢查orient2d(pts[v0], pts[v1], pts[v2]) 0。只要有一個(gè)三角形違反逆時(shí)針約定立刻終止程序。這種斷言只在排查時(shí)開(kāi)release 里可以關(guān)閉但它能攔截掉一大類(lèi)隱蔽的接線錯(cuò)誤。4.2 共圓點(diǎn)inCircle 恰好等于零現(xiàn)象某個(gè)局部區(qū)域在兩種對(duì)角線之間反復(fù)橫跳legalize遞歸不停止或者同一份輸入在不同優(yōu)化等級(jí)下得到不同結(jié)果。原因四個(gè)點(diǎn)精確共圓時(shí)inCircle 行列式值為零翻邊邏輯沒(méi)有定義。真實(shí)數(shù)據(jù)中完全共圓很少見(jiàn)但對(duì)稱(chēng)的柵格點(diǎn)、人工生成的測(cè)試點(diǎn)很容易觸發(fā)。零值本身不可怕可怕的是它在不同編譯器或優(yōu)化設(shè)置下的浮點(diǎn)表現(xiàn)不一致。解決最常見(jiàn)的是引入符號(hào)擾動(dòng)symbolic perturbation給每個(gè)點(diǎn)一個(gè)與坐標(biāo)相關(guān)的微小虛擬偏移打破共圓對(duì)稱(chēng)性。工程上更省事的做法是對(duì)輸入做輕量去對(duì)稱(chēng)化并在inCircle返回絕對(duì)值小于某個(gè)極小閾值時(shí)默認(rèn)不翻邊。對(duì)正確性要求高的場(chǎng)景應(yīng)該換用精確自適應(yīng)精度謂詞而不是依賴(lài) double 的運(yùn)氣。4.3 重復(fù)點(diǎn)與共線點(diǎn)沒(méi)預(yù)處理現(xiàn)象剖分過(guò)程中出現(xiàn) NaN定位死循環(huán)甚至數(shù)組越界訪問(wèn)。原因重復(fù)點(diǎn)會(huì)讓兩個(gè)頂點(diǎn)在幾何上完全重合inCircle 距離項(xiàng)退化行列式信息丟失共線點(diǎn)則讓“點(diǎn)在三角形內(nèi)部”的判定退化為“點(diǎn)在線上”orient 值反復(fù)為零步行法在相鄰三角形之間不停擺動(dòng)無(wú)法收斂。解決插入前先按坐標(biāo)排序再去重。排序可以用std::sort配合自定義比較器去重后用唯一序列重新建點(diǎn)集。共線點(diǎn)屬于另一種退化不能硬塞進(jìn)同一個(gè)剖分流程需要根據(jù)業(yè)務(wù)規(guī)則做降維處理或單獨(dú)分段。數(shù)據(jù)清洗是這一步的硬要求僥幸心理基本都會(huì)以神秘崩潰收?qǐng)觥?.4 超級(jí)三角形選太大現(xiàn)象靠近超級(jí)三角形的三角形面積異常大整體質(zhì)量統(tǒng)計(jì)被拉低某些翻邊操作產(chǎn)生極細(xì)長(zhǎng)三角形。原因超級(jí)三角形頂點(diǎn)坐標(biāo)比輸入點(diǎn)大幾個(gè)數(shù)量級(jí)時(shí)大三角形上的外接圓半徑也成倍放大。inCircle 里坐標(biāo)差的平方項(xiàng)變成“大數(shù)減大數(shù)”浮點(diǎn)有效位數(shù)被大量消耗翻邊判斷變得不可靠。解決超三角形的半徑取包圍盒對(duì)角線長(zhǎng)度的兩倍左右而不是拍腦袋取一個(gè) 1000 或 10000。另一個(gè)有效的補(bǔ)充手段是在插入前把所有點(diǎn)平移到以包圍盒中心為原點(diǎn)降低絕對(duì)坐標(biāo)數(shù)值。幾何變換不改變拓?fù)浣Y(jié)構(gòu)平移對(duì)整個(gè)剖分結(jié)果零影響卻能讓浮點(diǎn)誤差明顯變小。4.5 步行法在邊界點(diǎn)上的振蕩現(xiàn)象定位函數(shù)觸發(fā) guard 退出返回一個(gè)錯(cuò)誤的三角形索引后續(xù)翻邊全部跑偏。原因目標(biāo)點(diǎn)恰好在兩個(gè)三角形的公共邊上時(shí)orient 結(jié)果在兩個(gè)微小正負(fù)之間搖擺兩次判斷分別選中不同的跨越方向于是步行法在相鄰三角形之間來(lái)回跳動(dòng)無(wú)法收斂。解決對(duì) orient 的結(jié)果做鉗制當(dāng)絕對(duì)值小于極小閾值時(shí)直接置為零并把“點(diǎn)在邊上”按“點(diǎn)在三角形內(nèi)”處理。閾值不能定得太大否則會(huì)把本應(yīng)通過(guò)跨越離開(kāi)的鄰居點(diǎn)誤判成內(nèi)部點(diǎn)。一個(gè)實(shí)用的經(jīng)驗(yàn)值是按輸入坐標(biāo)量級(jí)的 1e-12 到 1e-10 來(lái)做鉗制。5. 設(shè)計(jì)取舍增量翻邊、Bowyer-Watson 與分治法的路線選擇增量翻邊并不是唯一的 Delaunay 構(gòu)建路線。另一種思路 Bowyer-Watson 算法會(huì)先找出所有外接圓包含新點(diǎn)的三角形把它們批量刪除再把留下的空洞與新點(diǎn)連成新三角形。它比增量翻邊更直觀但每次插入都需要維護(hù)一個(gè)候選集合刪除和重建的數(shù)量更多常數(shù)更大。分治法能在最壞情況下穩(wěn)定做到 O(n log n)但合并兩個(gè)子剖分時(shí)要處理復(fù)雜的凸包邊界縫合實(shí)現(xiàn)量遠(yuǎn)大于增量法而且完全無(wú)法支持動(dòng)態(tài)加點(diǎn)。增量法最大的工程優(yōu)勢(shì)在于局部性和動(dòng)態(tài)性。局部性體現(xiàn)在每次插入只需處理與新點(diǎn)相鄰的少量三角形動(dòng)態(tài)性體現(xiàn)在它天然支持流式添加點(diǎn)后續(xù)任意時(shí)刻都能繼續(xù)插入。代價(jià)是復(fù)雜度對(duì)輸入順序敏感隨機(jī)順序插入時(shí)步行法定位和翻邊次數(shù)的期望都很友好整體期望 O(n log n)如果輸入點(diǎn)按某種特定順序排列定位可能要穿越大半個(gè)網(wǎng)格退回 O(n^2)。所以很多實(shí)現(xiàn)會(huì)強(qiáng)制對(duì)點(diǎn)集做隨機(jī)打亂犧牲輸出順序的確定性來(lái)?yè)Q取穩(wěn)定的性能。有一次我處理某公司提供的逐行掃描地形數(shù)據(jù)數(shù)十萬(wàn)個(gè)點(diǎn)按柵格順序排列直接喂進(jìn)增量實(shí)現(xiàn)生成時(shí)間從預(yù)期的幾秒膨脹到兩分多鐘。排查了很久才意識(shí)到不是算法寫(xiě)錯(cuò)了而是輸入順序太規(guī)整規(guī)整到每次插入的定位都要從上一個(gè)點(diǎn)所在的三角形跨過(guò)大半個(gè)網(wǎng)格。從那以后我每次跑增量 Delaunay 之前都會(huì)先檢查輸入點(diǎn)的排列習(xí)慣必要時(shí)加一次 shuffle同時(shí)把 inCircle 和 orient2d 的符號(hào)約定用斷言鎖死杜絕繞序問(wèn)題在半夜偷襲。三角剖分本身不難難的是讓每一次局部修復(fù)始終聰明地工作。希望這篇拆解能幫到你把這套增量機(jī)制的底層邏輯理順。本文還有配套的精品資源點(diǎn)擊獲取