簡(jiǎn)介基于耳切法Ear Clipping的多邊形三角化 C 實(shí)現(xiàn)核心源自 mapbox 的 earcut 庫(kù)并通過(guò) z 階曲線散列優(yōu)化頂點(diǎn)訪問(wèn)順序能夠處理無(wú)序頂點(diǎn)并輸出三角形頂點(diǎn)索引。算法在經(jīng)典耳切法基礎(chǔ)上吸收了 FISTFast Industrial-Strength Triangulation與 David Eberly 的改進(jìn)思路對(duì)孔洞、扭曲多邊形、退化與自相交等復(fù)雜輸入有較好支持適合圖形學(xué)、WebGIS 或幾何算法方向的開(kāi)發(fā)者學(xué)習(xí)與復(fù)用。壓縮包共 33 個(gè)文件體積約 4.29MB除頭文件與源文件外還附帶多份 CSV 測(cè)試數(shù)據(jù)如道路區(qū)域、頂點(diǎn)坐標(biāo)與索引表以及 Visual Studio 解決方案和工程文件可在 Windows 下直接打開(kāi)構(gòu)建調(diào)試。已有 453 人學(xué)習(xí)下載。對(duì)想理解耳切法工程實(shí)現(xiàn)、快速搭建三角化測(cè)試環(huán)境的讀者而言這份資源提供了可運(yùn)行的完整示例既能對(duì)照源碼剖析關(guān)鍵優(yōu)化也可以將核心邏輯抽取到自有項(xiàng)目中使用。 很多時(shí)候你以為從某個(gè)項(xiàng)目里扒下來(lái)的zip包只是個(gè)普通的資源壓縮包結(jié)果解壓開(kāi)一看里面躺著一個(gè)改變你處理圖形數(shù)據(jù)方式的小東西。Earcut-Triangulation.zip就是我在做地圖可視化項(xiàng)目時(shí)遇到過(guò)的一個(gè)典型包里面其實(shí)就是Earcut這個(gè)三角剖分庫(kù)的源碼和示例。工程上三角剖分就是把一個(gè)多邊形拆成三角形集合任何圖形引擎、渲染管線最后處理的基本單位都是三角形。Earcut解決的正是如何快速、穩(wěn)定地把任意二維多邊形拆成三角形這一基礎(chǔ)問(wèn)題。如果你做WebGL、Canvas繪圖、GIS數(shù)據(jù)渲染、游戲碰撞體生成或者凡是涉及多邊形轉(zhuǎn)網(wǎng)格的需求這篇文章都有參考價(jià)值。我會(huì)從它的核心原理、API使用、驗(yàn)證鏈路、選型對(duì)比到真實(shí)項(xiàng)目中的坑一條線講清楚。不繞彎子直接進(jìn)入正題。1. 解壓zip包之后Earcut到底是干嘛的第一次接觸Earcut這個(gè)庫(kù)的時(shí)候我正被一個(gè)多邊形填充問(wèn)題折磨得夠嗆。項(xiàng)目里有一段來(lái)自GIS系統(tǒng)的地塊邊界數(shù)據(jù)多邊形輪廓?jiǎng)虞m上百個(gè)頂點(diǎn)而且中間還帶著幾個(gè)洞比如地塊中間有個(gè)湖泊或綠化帶。我要在Canvas上做紋理填充底層是WebGL。WebGL不會(huì)認(rèn)多邊形它只認(rèn)三角形。也就是說(shuō)我必須先把這些復(fù)雜的多邊形數(shù)據(jù)切成一堆小三角形然后才能繪制。當(dāng)時(shí)試過(guò)幾種笨辦法手動(dòng)把多邊形區(qū)域做網(wǎng)格劃分或者用耳朵切法自己寫(xiě)一個(gè)。前者效率低后者邊界情況多比如凹多邊形、帶洞多邊形、頂點(diǎn)重復(fù)、浮點(diǎn)精度誤差隨便一個(gè)都能讓網(wǎng)格出現(xiàn)裂縫或重疊。Earcut就是在這個(gè)場(chǎng)景下進(jìn)入視線的。它是一個(gè)基于耳切法Ear Clipping的輕量級(jí)三角剖分庫(kù)由Mapbox團(tuán)隊(duì)維護(hù)。它的核心能力是給定一個(gè)多邊形及其內(nèi)洞的頂點(diǎn)數(shù)據(jù)返回一串三角形頂點(diǎn)索引。整個(gè)過(guò)程沒(méi)有任何依賴一個(gè)文件就能跑而且實(shí)測(cè)速度在同類庫(kù)里常年排在前面。一個(gè)很有意思的細(xì)節(jié)是它的名字。Earcut從字面拆開(kāi)是耳朵切割對(duì)應(yīng)的是計(jì)算幾何里的經(jīng)典算法每次在多邊形上尋找一個(gè)凸的耳朵把它切下來(lái)再用剩余頂點(diǎn)構(gòu)造新的多邊形重復(fù)這個(gè)過(guò)程直到所有頂點(diǎn)都被吃掉。Earcut把所有精力都放在讓這個(gè)基本算法更快、更穩(wěn)上。從我這個(gè)搞前端可視化的人的角度看Earcut有幾點(diǎn)在當(dāng)時(shí)特別打動(dòng)我。第一數(shù)據(jù)結(jié)構(gòu)極簡(jiǎn)輸入是一個(gè)扁平的坐標(biāo)數(shù)組輸出是一個(gè)整數(shù)索引數(shù)組沒(méi)有繁瑣的對(duì)象包裝拷貝成本低存到GPU緩沖里也方便。第二它不只是處理簡(jiǎn)單多邊形對(duì)帶洞多邊形、退化點(diǎn)都做了處理。第三它在算法層面做了優(yōu)化平均復(fù)雜度接近O(n)雖然最壞情況仍然是O(n2)但實(shí)際處理幾萬(wàn)個(gè)頂點(diǎn)也基本不卡頓。2. 從耳朵到三角形的全部秘密耳切法的原理與邊界處理理解了Earcut解決了什么問(wèn)題之后有必要拆開(kāi)看看它內(nèi)部是怎么干的。這不是為了重復(fù)造輪子而是只有真正理解它的工作原理才能在我們自己的項(xiàng)目里把它用到刀刃上。2.1 耳朵是怎么定義的要理解耳切法第一步是搞清楚耳朵的數(shù)學(xué)定義。給定一個(gè)多邊形的連續(xù)三個(gè)頂點(diǎn)A、B、C如果角ABC是一個(gè)凸角內(nèi)角小于180度并且以頂點(diǎn)B為頂點(diǎn)的這個(gè)小三角形內(nèi)部不包含當(dāng)前多邊形集合里的任何其他頂點(diǎn)那么三角形ABC就是一個(gè)耳朵。這個(gè)定義看起來(lái)簡(jiǎn)單但在程序里判斷卻要注意幾個(gè)邊界情況。首先是凸點(diǎn)的判斷取A、B、C三點(diǎn)通過(guò)向量叉積計(jì)算方向。叉積大于零說(shuō)明是凸角小于零說(shuō)明是凹角等于零說(shuō)明三點(diǎn)共線這是一個(gè)需要單獨(dú)處理的退化情況。Earcut對(duì)共線點(diǎn)的處理策略比較明確共線的點(diǎn)不會(huì)形成有效耳朵通常會(huì)被跳過(guò)或者在前置處理階段剔除。其次要判斷三角形內(nèi)部不包含其他頂點(diǎn)這一步。Earcut直接用了一個(gè)點(diǎn)在三角形內(nèi)的判斷函數(shù)對(duì)當(dāng)前剩余的所有頂點(diǎn)做一次遍歷。這也是耳切法最耗時(shí)的部分暴力遍歷會(huì)讓復(fù)雜度逼近O(n2)。Earcut在這里做了一項(xiàng)關(guān)鍵優(yōu)化利用一個(gè)哈希網(wǎng)格hash grid來(lái)縮小哪些點(diǎn)可能需要檢查的范圍而不是每次都對(duì)全部頂點(diǎn)做包含判斷。這一步直接決定了它面對(duì)大數(shù)據(jù)量時(shí)的性能上限。2.2 一個(gè)被忽略的前置步驟三角化前的排序與索引重排Earcut的輸入允許你傳入洞的索引數(shù)組它會(huì)先把外輪廓與洞統(tǒng)一處理成一個(gè)帶洞多邊形集合然后做一次預(yù)處理排序。這一步做的事情是通過(guò)比較所有環(huán)的某一點(diǎn)坐標(biāo)找到一個(gè)絕佳的起始點(diǎn)然后對(duì)環(huán)的頂點(diǎn)順序做一致性檢查。為什么要做這個(gè)因?yàn)槎蟹ㄒ蠖噙呅雾旤c(diǎn)按固定方向Earcut內(nèi)部統(tǒng)一為逆時(shí)針排列才能保證叉積符號(hào)判斷正確。用戶給的頂點(diǎn)順序未必規(guī)范特別是GIS數(shù)據(jù)里的輪廓順序經(jīng)常是亂的。Earcut會(huì)自動(dòng)把外輪廓和洞統(tǒng)一到正確方向外輪廓逆時(shí)針洞順時(shí)針。這樣處理完之后算法內(nèi)部的所有符號(hào)判斷才能統(tǒng)一。這也是我一開(kāi)始用Earcut經(jīng)常理解錯(cuò)的地方。我總以為輸入數(shù)據(jù)的頂點(diǎn)順序會(huì)影響剖分結(jié)果其實(shí)Earcut在內(nèi)部已經(jīng)做了方向重排。它對(duì)輸入的唯一硬性要求是每個(gè)環(huán)內(nèi)的頂點(diǎn)順序要保持連續(xù)不能穿插并且數(shù)據(jù)格式是二維或三維坐標(biāo)的扁平數(shù)組。2.3 洞口的處理思路帶洞多邊形的三角剖分是很多自寫(xiě)方案望而卻步的地方。直觀上耳朵不能穿過(guò)洞否則三角形會(huì)跨越空洞區(qū)域。Earcut的做法比較巧妙它在主輪廓上找一個(gè)合適的頂點(diǎn)把洞橋接到主輪廓上讓主輪廓和洞合并成單個(gè)多邊形的頂點(diǎn)序列。這個(gè)橋接點(diǎn)選擇很重要Earcut會(huì)找當(dāng)前輪廓上視覺(jué)上最接近洞的一點(diǎn)然后在兩個(gè)環(huán)上各自切開(kāi)交叉連接相當(dāng)于給形狀開(kāi)了一條割線繞洞走一圈再回來(lái)這樣就把原本帶洞的問(wèn)題轉(zhuǎn)化為無(wú)洞的耳切問(wèn)題接下來(lái)交給同一套耳切流程處理。這個(gè)橋接思路本身不算新鮮但Earcut的聰明之處在于選擇橋接點(diǎn)時(shí)用了可見(jiàn)性判斷——只有主輪廓和洞之間的連線完全落在形狀內(nèi)部時(shí)才采納否則換個(gè)點(diǎn)嘗試。如果沒(méi)有合適的連接點(diǎn)它會(huì)保守地認(rèn)為這個(gè)洞無(wú)法處理。實(shí)際項(xiàng)目里遇到這種情況不多但一旦出現(xiàn)結(jié)果往往是剖分輸出異常或直接報(bào)錯(cuò)下一篇踩坑部分會(huì)展開(kāi)說(shuō)。3. 上手實(shí)操?gòu)哪玫絲ip到跑通第一個(gè)三角剖分理論部分講完該動(dòng)手了。下面這套流程完全基于Earcut-Triangulation.zip包里提供的內(nèi)容來(lái)走我當(dāng)初跑通的時(shí)候還沒(méi)有這些理解現(xiàn)在回頭看有幾個(gè)步驟確實(shí)是可以直接抄作業(yè)的。3.1 解壓包和引入庫(kù)Earcut是零依賴的源碼就是一個(gè)JavaScript文件。在Node.js環(huán)境里直接require就行在瀏覽器里也可以script標(biāo)簽引入后調(diào)用全局方法。const earcut require(./earcut.js); // 正方形四個(gè)頂點(diǎn)左上開(kāi)始順時(shí)針 const vertices [0, 0, 100, 0, 100, 100, 0, 100]; const triangles earcut(vertices); console.log(triangles); // 輸出類似 [1, 0, 3, 3, 2, 1]表示兩個(gè)三角形這里值得解釋一下返回值這是一個(gè)扁平數(shù)組每三個(gè)數(shù)構(gòu)成一個(gè)三角形的三個(gè)頂點(diǎn)索引。上面的輸出表示第一個(gè)三角形由索引1、0、3對(duì)應(yīng)的三個(gè)點(diǎn)構(gòu)成第二個(gè)三角形由3、2、1對(duì)應(yīng)的三個(gè)點(diǎn)構(gòu)成。索引從輸入坐標(biāo)數(shù)組的第0個(gè)元素開(kāi)始按第幾個(gè)頂點(diǎn)計(jì)數(shù)而不是按數(shù)組下標(biāo)計(jì)數(shù)。也就是說(shuō)X坐標(biāo)是第0個(gè)頂點(diǎn)Y坐標(biāo)也是第0個(gè)頂點(diǎn)兩者共同占用數(shù)組里的兩個(gè)元素但索引只算頂點(diǎn)序號(hào)。3.2 帶洞多邊形的輸入格式很多人在這一步栽過(guò)跟頭。帶洞多邊形的調(diào)用多了一個(gè)參數(shù)holeIndices。它表示每個(gè)內(nèi)洞的起始頂點(diǎn)在整體頂點(diǎn)列表里的序號(hào)。const outer [0, 0, 200, 0, 200, 200, 0, 200]; // 外框 const hole [50, 50, 150, 50, 150, 150, 50, 150]; // 洞 const allVertices outer.concat(hole); const holeIndices [4]; // 洞從第4個(gè)頂點(diǎn)開(kāi)始 const triangles earcut(allVertices, holeIndices);關(guān)鍵點(diǎn)在于外輪廓和洞的頂點(diǎn)是拼接在同一個(gè)數(shù)組里的holeIndices里的值就是洞的起始頂點(diǎn)序號(hào)。如果外輪廓有4個(gè)頂點(diǎn)那么第一個(gè)洞的起始序號(hào)就是4第二個(gè)洞如果繼續(xù)追加起始序號(hào)要重新計(jì)算。另外外輪廓和每個(gè)洞的頂點(diǎn)環(huán)都必須按環(huán)內(nèi)順序自然連續(xù)不能把不同環(huán)的頂點(diǎn)穿插存儲(chǔ)。3.3 三維坐標(biāo)怎么處理Earcut的第三個(gè)參數(shù)是維度默認(rèn)值是2。如果你傳入的是三維坐標(biāo)數(shù)據(jù)比如帶高度的地理坐標(biāo)第三個(gè)參數(shù)傳3Earcut會(huì)自動(dòng)按照前兩個(gè)維度做剖分第三個(gè)維度直接忽略但索引計(jì)算時(shí)仍然按三維坐標(biāo)的步長(zhǎng)跳過(guò)。const coords3d [0, 0, 10, 100, 0, 10, 100, 100, 10, 0, 100, 10]; const triangles earcut(coords3d, null, 3);這個(gè)特性在做3D地形、建筑模型墻面投影、或WebGL渲染高度圖時(shí)特別實(shí)用。不用額外把數(shù)據(jù)降維直接傳完整坐標(biāo)Earcut自己知道取前兩維做平面剖分輸出索引依然對(duì)得上整個(gè)三維坐標(biāo)數(shù)組。3.4 用Canvas驗(yàn)證剖分結(jié)果光有索引數(shù)組不渲染出來(lái)其實(shí)很難確認(rèn)剖分是否正確。一個(gè)非常簡(jiǎn)單的驗(yàn)證方式是創(chuàng)建一個(gè)離屏Canvas畫(huà)到頁(yè)面上看效果。function drawTriangles(canvas, coords, triangles) { const ctx canvas.getContext(2d); ctx.fillStyle #f0f0f0; ctx.fillRect(0, 0, canvas.width, canvas.height); ctx.strokeStyle #333; for (let i 0; i triangles.length; i 3) { ctx.beginPath(); ctx.moveTo(coords[triangles[i] * 2], coords[triangles[i] * 2 1]); ctx.lineTo(coords[triangles[i 1] * 2], coords[triangles[i 1] * 2 1]); ctx.lineTo(coords[triangles[i 2] * 2], coords[triangles[i 2] * 2 1]); ctx.closePath(); ctx.stroke(); } }渲染出來(lái)如果三角形之間有重疊或者覆蓋住了洞的區(qū)域說(shuō)明剖分結(jié)果有問(wèn)題。這里要特別強(qiáng)調(diào)一個(gè)很多人忽略的事項(xiàng)三角形重疊并不一定說(shuō)明Earcut出錯(cuò)。我遇到過(guò)一種情況是洞的方向是反的導(dǎo)致Earcut橋接失敗或者輸入多邊形本身是自相交的這類多邊形屬于不可三角剖分的幾何范圍Earcut的文檔里明確說(shuō)了它不支持自相交多邊形。后面我會(huì)專門(mén)說(shuō)這個(gè)坑。4. 實(shí)戰(zhàn)場(chǎng)景對(duì)照Earcut在哪些環(huán)節(jié)能派上大用場(chǎng)講了原理和用法接下來(lái)分享幾個(gè)我自己實(shí)際用到Earcut的場(chǎng)景幫助你把它能做什么落在更具體的位置上。4.1 WebGL地圖地塊渲染這是Earcut的主場(chǎng)。地圖上的國(guó)家邊界、省市區(qū)邊界、建筑物輪廓?jiǎng)虞m上萬(wàn)頂點(diǎn)。這些數(shù)據(jù)傳入WebGL之前必須變成三角形。Earcut在地圖領(lǐng)域有非常成熟的應(yīng)用案例Mapbox Vector Tile的渲染就大量依賴它。它的性能優(yōu)勢(shì)和極低的內(nèi)存占用在這種每一幀都要重新三角剖分或者一次性剖分大量多邊形的場(chǎng)景里會(huì)被放大到極致。實(shí)際操作中需要注意一個(gè)細(xì)節(jié)地理坐標(biāo)系的經(jīng)緯度數(shù)據(jù)不適合直接當(dāng)平面坐標(biāo)做剖分。因?yàn)榻?jīng)緯度在不同緯度上的實(shí)際距離不同如果直接把經(jīng)緯度當(dāng)成平面坐標(biāo)輸入剖分結(jié)果在高緯度地區(qū)會(huì)出現(xiàn)肉眼可見(jiàn)的變形。我一般的處理方式是先把經(jīng)緯度投影到平面坐標(biāo)系如Web Mercator投影再做剖分。Earcut本身不關(guān)心你的坐標(biāo)單位它只對(duì)平面坐標(biāo)負(fù)責(zé)。4.2 Canvas 2D復(fù)雜路徑填充如果你只是想在Canvas 2D里填充一個(gè)帶洞的多邊形是不是不需要Earcut大部分情況下確實(shí)不需要Canvas自身的Path2D就能處理。但如果你的場(chǎng)景是把任意多邊形拆成三角形集合再對(duì)每個(gè)三角形單獨(dú)做漸變填充或者紋理映射Earcut就是不可替代的。我做過(guò)一個(gè)地塊染色工具需求是每個(gè)地塊內(nèi)部按不同屬性分區(qū)做斜向紋理填充。直接Canvas填充只能整塊填無(wú)法逐三角形做材質(zhì)變化。用Earcut把地塊剖分后每個(gè)小三角形都能獨(dú)立控制紋理角度和顏色視覺(jué)效果細(xì)膩很多渲染性能也穩(wěn)定。4.3 游戲碰撞體和物理引擎游戲開(kāi)發(fā)中很多碰撞體形狀是凸多邊形但關(guān)卡設(shè)計(jì)里的障礙物常常是凹的。大多數(shù)2D物理引擎如Box2D只支持凸多邊形碰撞體復(fù)雜的凹形狀需要拆成多個(gè)凸多邊形的組合。Earcut雖然不是專門(mén)做凸分解的但可以先通過(guò)Earcut把凹多邊形三角剖分再把相鄰三角形合并成凸多邊形或者直接把三角形網(wǎng)格作為碰撞體集合交給物理引擎。這在做2D橫版關(guān)卡時(shí)是一條實(shí)用的管線。嚴(yán)格來(lái)說(shuō)凸分解有更專門(mén)的庫(kù)比如poly2tri配合貝塞爾曲線預(yù)處理但Earcut勝在集成成本低、結(jié)果穩(wěn)定適合對(duì)碰撞精度要求不是物理級(jí)苛刻的中小型項(xiàng)目。5. 同場(chǎng)競(jìng)技Earcut和其他三角剖分方案怎么選在做項(xiàng)目選型的時(shí)候Earcut不是唯一選擇。下面把常見(jiàn)的幾個(gè)方案放在一張表里對(duì)比一下方便你按需選擇。方案核心優(yōu)勢(shì)適用場(chǎng)景局限Earcut輕量、極快、零依賴帶洞多邊形支持好WebGL渲染、地圖數(shù)據(jù)、Canvas大批量三角化不支持自相交多邊形poly2tri支持約束邊處理帶洞能力強(qiáng)需要精確約束特定邊的場(chǎng)景性能一般依賴相對(duì)多l(xiāng)ibtess.js強(qiáng)大的健壯性處理自相交和復(fù)雜退化情形復(fù)雜CAD類多邊形、渲染引擎容錯(cuò)要求高體積大API復(fù)雜three.js ShapeUtils與Three.js生態(tài)無(wú)縫集成Three.js用戶快速做形狀三角化沒(méi)有獨(dú)立維護(hù)性能優(yōu)化有限如果你已經(jīng)引入Three.jsShapeUtils先用起來(lái)也不是不行但它是為通用形狀設(shè)計(jì)的標(biāo)準(zhǔn)多邊形的處理足夠復(fù)雜大頂點(diǎn)量的場(chǎng)景性能不如Earcut。反過(guò)來(lái)如果你做的是CAD類工具輸入多邊形可能蘊(yùn)含大量不規(guī)范數(shù)據(jù)如自相交那Earcut的直接拋錯(cuò)或者異常輸出會(huì)讓你崩潰這種情況建議直接上libtess.js。選Earcut還有一個(gè)很實(shí)際的考量——它集成極簡(jiǎn)。我在一個(gè)老項(xiàng)目里試過(guò)換掉自寫(xiě)的三角化邏輯改動(dòng)量只有幾十行沒(méi)有引入任何新依賴因?yàn)镋arcut本身就是一個(gè)文件。這種低成本無(wú)疑增加了我們做技術(shù)升級(jí)時(shí)的試錯(cuò)空間。6. 繞不開(kāi)的坑真實(shí)項(xiàng)目里Earcut踩過(guò)的雷這部分是全文的重點(diǎn)。Earcut雖然強(qiáng)大但在真實(shí)業(yè)務(wù)數(shù)據(jù)上邊界情況遠(yuǎn)比單元測(cè)試復(fù)雜得多。以下這些坑我從實(shí)戰(zhàn)中一個(gè)個(gè)踩過(guò)來(lái)。6.1 自相交多邊形文檔里寫(xiě)得很清楚踩的時(shí)候才長(zhǎng)記性Earcut官網(wǎng)文檔有一句話This library does not work with self-intersecting polygons。我當(dāng)初不以為意覺(jué)得真實(shí)業(yè)務(wù)數(shù)據(jù)怎么會(huì)有自相交結(jié)果第一次接入GIS數(shù)據(jù)就撞上了。多邊形自相交指的是多邊形的邊與邊之間有交叉這種形狀嚴(yán)格意義上不是一個(gè)合法的簡(jiǎn)單多邊形。Earcut對(duì)它不保證任何輸出——可能返回奇怪索引可能直接卡住也可能在耳切時(shí)把交叉區(qū)域錯(cuò)誤填充。問(wèn)題的根因在于耳切法本身依賴點(diǎn)在三角形內(nèi)部的判斷自相交會(huì)破壞這個(gè)判斷的正確性。我的排查思路如下第一步在調(diào)用eacut之前先用一條低成本的掃描線判斷多邊形是否自相交如果自相交就進(jìn)入容錯(cuò)分支第二步容錯(cuò)分支里使用一個(gè)多邊形拆分方法在自相交點(diǎn)處把多邊形切成多個(gè)合法多邊形再分別調(diào)用Earcut完成剖分。這段代碼是通用性質(zhì)的關(guān)鍵是找到自相交點(diǎn)并切割多邊形業(yè)內(nèi)常稱為多邊形正則化。不建議自己造輪子推薦使用turf.js里的polygon_self_intersection來(lái)處理或者如果必須在一個(gè)文件里搞定也可以直接用polygon-clipping庫(kù)來(lái)做多邊形歸一化。總之不要心存僥幸業(yè)務(wù)數(shù)據(jù)一旦來(lái)源不可控自相交一定會(huì)出現(xiàn)。6.2 重復(fù)點(diǎn)與共線退化不報(bào)錯(cuò)但結(jié)果詭異有時(shí)候你的輸入頂點(diǎn)里包含完全重復(fù)的坐標(biāo)點(diǎn)或者三個(gè)連續(xù)頂點(diǎn)在同一水平線上。Earcut內(nèi)部有去重和退化點(diǎn)剔除機(jī)制大多數(shù)情況它會(huì)自動(dòng)處理。但處理結(jié)果可能不是你想的那樣典型的特征是輸出三角形數(shù)量少于預(yù)期。比如你要給一個(gè)形狀做面積估算期望剖分出來(lái)50個(gè)三角形結(jié)果只出來(lái)40個(gè)一部分三角形面積被Earcut默認(rèn)合并了。它之所以會(huì)這么做是因?yàn)橥嘶切蚊娣e接近0對(duì)渲染沒(méi)有任何幫助它的去重邏輯會(huì)優(yōu)先犧牲這部分頂點(diǎn)換來(lái)的是更穩(wěn)定的索引輸出。這個(gè)行為在渲染上是優(yōu)點(diǎn)但在需要嚴(yán)格三角形計(jì)數(shù)或頂點(diǎn)一一對(duì)應(yīng)的場(chǎng)景里需要特別注意。如果你必須保持所有頂點(diǎn)都被使用需要把共線點(diǎn)提前做偏移微調(diào)或者改用其他允許約束的方案。我的處理方式是在進(jìn)入Earcut之前對(duì)數(shù)據(jù)做一輪頂點(diǎn)清洗把距離小于某個(gè)容差的點(diǎn)合并并記錄合并映射。這樣既保證了Earcut內(nèi)部的穩(wěn)定性又能讓我們拿到準(zhǔn)確的頂點(diǎn)與三角形的對(duì)應(yīng)關(guān)系。6.3 坐標(biāo)數(shù)值過(guò)大帶來(lái)的精度問(wèn)題地圖數(shù)據(jù)經(jīng)常使用帶6位以上小數(shù)位的經(jīng)緯度或者超大范圍的投影坐標(biāo)系數(shù)值比如X坐標(biāo)在百萬(wàn)級(jí)別。這種情況下浮點(diǎn)誤差會(huì)被耳切法內(nèi)部的叉積計(jì)算放大典型表現(xiàn)是三角形之間出現(xiàn)細(xì)小的裂縫這在渲染時(shí)表現(xiàn)為多邊形邊緣有鋸齒或半透明縫隙。Earcut雖然對(duì)數(shù)值精度有處理但遇到極端跨度一個(gè)多邊形橫跨幾百公里時(shí)還是會(huì)遇到精度問(wèn)題。我的實(shí)踐是做一個(gè)歸一化預(yù)處理把多邊形的所有坐標(biāo)先減去包圍盒的最小X和最小Y讓數(shù)值落在相對(duì)較小的范圍內(nèi)三角剖分完成后再把頂點(diǎn)索引映射回原坐標(biāo)值。這樣做的代價(jià)很小能明顯提升剖分穩(wěn)定性。如果你同時(shí)還要做碰撞檢測(cè)歸一化后的坐標(biāo)反而更容易做浮點(diǎn)運(yùn)算。6.4 帶洞多邊形橋接失敗無(wú)報(bào)錯(cuò)的異常輸出前面說(shuō)Earcut在處理洞的時(shí)候做橋接橋接需要主輪廓和洞之間有可見(jiàn)連接線。如果洞過(guò)度遠(yuǎn)離主輪廓或者主輪廓太狹窄復(fù)雜橋接可能失敗。Earcut采用了一種緩存退避策略如果找不到理想的橋接點(diǎn)它可能會(huì)把洞當(dāng)作獨(dú)立的多邊形單獨(dú)剖分而不是作為一個(gè)空洞排除。這種異常的可怕之處在于它不報(bào)錯(cuò)也不返回異常值只是三角形穿過(guò)了洞的區(qū)域直觀表現(xiàn)為紋理把洞填上了。排查方法是三角剖分結(jié)束后做一個(gè)面積校驗(yàn)。從輸入多邊形算出外輪廓面積和洞面積再?gòu)钠史纸Y(jié)果算出所有三角形的總面積帶符號(hào)面積或絕對(duì)值面積都行對(duì)比兩者是否接近。如果差出一個(gè)洞的面積量級(jí)就可以斷定橋接失敗。修復(fù)橋接失敗沒(méi)有通用銀彈一個(gè)比較穩(wěn)的做法是在調(diào)用Earcut前手動(dòng)擴(kuò)大洞的邊緣讓洞與主輪廓保持一個(gè)合理的間隙或者把洞的位置做一次微小平移讓橋接點(diǎn)更容易找到實(shí)在不行就把帶洞多邊形拆成多個(gè)無(wú)洞的多邊形分別處理。工程上我認(rèn)為第三招最靠譜畢竟拆分后的結(jié)果是確定的、可控的。7. 讓Earcut更快性能調(diào)優(yōu)的幾個(gè)實(shí)測(cè)方向前面提到Earcut本身夠快但在大頂點(diǎn)量數(shù)據(jù)場(chǎng)景還是可以通過(guò)一些手段壓榨出更多性能。7.1 預(yù)處理頂點(diǎn)合并幾千個(gè)頂點(diǎn)的多邊形往往包含大量視覺(jué)上不敏感、但數(shù)值上存在微小抖動(dòng)的點(diǎn)。在一次渲染場(chǎng)景里這些點(diǎn)沒(méi)有影響但在每幀都需要三角剖分的場(chǎng)景里它們會(huì)顯著拖慢速度。對(duì)我常用的地塊數(shù)據(jù)一個(gè)簡(jiǎn)單的Douglas-Peucker抽稀算法能把頂點(diǎn)數(shù)減少40%以上而形狀誤差肉眼幾乎不可見(jiàn)。Earcut的剖分時(shí)間跟頂點(diǎn)數(shù)強(qiáng)相關(guān)所以抽稀是性價(jià)比最高的優(yōu)化。7.2 避免頻繁創(chuàng)建大數(shù)組Earcut的輸入輸出都是數(shù)組JS引擎在GC時(shí)對(duì)超大數(shù)組的回收是有代價(jià)的。如果你在動(dòng)畫(huà)循環(huán)里頻繁調(diào)用Earcut建議復(fù)用輸入數(shù)組而不是每次new一個(gè)新數(shù)組同時(shí)緩存輸出的索引數(shù)組以便復(fù)用。這一點(diǎn)在移動(dòng)端WebGL場(chǎng)景下尤其敏感我做過(guò)一次對(duì)比試驗(yàn)復(fù)用數(shù)組的方案比每次新建數(shù)組的方案在長(zhǎng)時(shí)間幀序列里能減少約30%的明顯卡頓。7.3 把Earcut放Web Worker里跑如果你的多邊形數(shù)據(jù)量極大十萬(wàn)級(jí)頂點(diǎn)Earcut的計(jì)算耗時(shí)可能超過(guò)16ms這會(huì)導(dǎo)致動(dòng)畫(huà)掉幀。把Earcut丟到Web Worker里做剖分主線程只負(fù)責(zé)接收索引并上傳GPU渲染和剖分流水線并行體感流暢度會(huì)有質(zhì)的提升。Earcut本身沒(méi)有環(huán)境依賴Worker里直接跑完全沒(méi)問(wèn)題這也是它輕量屬性帶來(lái)的隱形福利。8. 驗(yàn)證剖分正確性的標(biāo)準(zhǔn)化流程最后分享一套我自己整理的驗(yàn)證清單。每當(dāng)我改完三角剖分管線都會(huì)按這套流程自測(cè)一遍能攔截絕大多數(shù)隱藏問(wèn)題。面積一致性校驗(yàn)計(jì)算輸入多邊形的有符號(hào)面積總和外輪廓正、洞負(fù)和剖分結(jié)果所有三角形的帶符號(hào)面積之和做對(duì)比誤差超過(guò)0.1%視為剖分異常。索引合法性校驗(yàn)所有三角形索引必須在[0, 頂點(diǎn)數(shù))這個(gè)區(qū)間內(nèi)出現(xiàn)負(fù)數(shù)或越界基本都是數(shù)據(jù)錯(cuò)誤。邊界完整性校驗(yàn)把剖分結(jié)果所有三角形的邊收集起來(lái)外輪廓的邊界邊出現(xiàn)次數(shù)必須是1洞邊界的邊界邊出現(xiàn)次數(shù)也必須是1內(nèi)部共享邊出現(xiàn)次數(shù)必須是2。不滿足說(shuō)明剖分有裂縫或重疊。洞區(qū)域校驗(yàn)在帶洞多邊形場(chǎng)景中隨機(jī)采樣洞內(nèi)部幾個(gè)點(diǎn)確認(rèn)這些點(diǎn)沒(méi)有被任何三角形覆蓋。這套校驗(yàn)流程不用每次都跑全量的數(shù)學(xué)計(jì)算但在數(shù)據(jù)源切換、Earcut版本升級(jí)、算法參數(shù)修改這三個(gè)節(jié)點(diǎn)上最好都執(zhí)行一遍。跑一次也就幾毫秒但能免去很多查半天查不出原因的渲染Bug。做好這些前置校驗(yàn)Earcut在絕大多數(shù)業(yè)務(wù)場(chǎng)景里都能穩(wěn)定發(fā)揮。它雖然是個(gè)輕量到不能再輕量的庫(kù)但深入進(jìn)去會(huì)發(fā)現(xiàn)圖形學(xué)里那些基礎(chǔ)問(wèn)題真的到了工程落地上處處都是細(xì)節(jié)。本文還有配套的精品資源點(diǎn)擊獲取