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