企业官网建设流程全解析

简介：基于耳切法（Ear Clipping）的多边形三角化 C++ 实现，核心源自 mapbox 的 earcut 库，并通过 z 阶曲线散列优化顶点访问顺序，能够处理无序顶点并输出三角形顶点索引。算法在经典耳切法基础上吸收了 FIST（Fast Industrial-Strength Triangulation）与 David Eberly 的改进思路，对孔洞、扭曲多边形、退化与自相交等复杂输入有较好支持，适合图形学、WebGIS 或几何算法方向的开发者学习与复用。压缩包共 33 个文件，体积约 4.29MB，除头文件与源文件外，还附带多份 CSV 测试数据（如道路区域、顶点坐标与索引表），以及 Visual Studio 解决方案和工程文件，可在 Windows 下直接打开构建调试。已有 453 人学习下载。对想理解耳切法工程实现、快速搭建三角化测试环境的读者而言，这份资源提供了可运行的完整示例，既能对照源码剖析关键优化，也可以将核心逻辑抽取到自有项目中使用。 很多时候，你以为从某个项目里扒下来的zip包只是个普通的资源压缩包，结果解压开一看，里面躺着一个改变你处理图形数据方式的小东西。Earcut-Triangulation.zip就是我在做地图可视化项目时遇到过的一个典型包，里面其实就是Earcut这个三角剖分库的源码和示例。工程上，三角剖分就是把一个多边形拆成三角形集合，任何图形引擎、渲染管线最后处理的基本单位都是三角形。Earcut解决的正是"如何快速、稳定地把任意二维多边形拆成三角形"这一基础问题。

如果你做WebGL、Canvas绘图、GIS数据渲染、游戏碰撞体生成，或者凡是涉及"多边形转网格"的需求，这篇文章都有参考价值。我会从它的核心原理、API使用、验证链路、选型对比到真实项目中的坑，一条线讲清楚。不绕弯子，直接进入正题。

1. 解压zip包之后：Earcut到底是干嘛的

第一次接触Earcut这个库的时候，我正被一个多边形填充问题折磨得够呛。项目里有一段来自GIS系统的地块边界数据，多边形轮廓动辄上百个顶点，而且中间还带着几个洞（比如地块中间有个湖泊或绿化带）。我要在Canvas上做纹理填充，底层是WebGL。WebGL不会认多边形，它只认三角形。也就是说，我必须先把这些复杂的多边形数据切成一堆小三角形，然后才能绘制。

当时试过几种笨办法：手动把多边形区域做网格划分，或者用耳朵切法自己写一个。前者效率低，后者边界情况多，比如凹多边形、带洞多边形、顶点重复、浮点精度误差，随便一个都能让网格出现裂缝或重叠。

Earcut就是在这个场景下进入视线的。它是一个基于耳切法（Ear Clipping）的轻量级三角剖分库，由Mapbox团队维护。它的核心能力是：给定一个多边形及其内洞的顶点数据，返回一串三角形顶点索引。整个过程没有任何依赖，一个文件就能跑，而且实测速度在同类库里常年排在前面。

一个很有意思的细节是它的名字。Earcut从字面拆开是"耳朵切割"，对应的是计算几何里的经典算法：每次在多边形上寻找一个凸的"耳朵"，把它切下来，再用剩余顶点构造新的多边形，重复这个过程，直到所有顶点都被吃掉。Earcut把所有精力都放在让这个基本算法更快、更稳上。

从我这个搞前端可视化的人的角度看，Earcut有几点在当时特别打动我。第一，数据结构极简，输入是一个扁平的坐标数组，输出是一个整数索引数组，没有繁琐的对象包装，拷贝成本低，存到GPU缓冲里也方便。第二，它不只是处理简单多边形，对带洞多边形、退化点都做了处理。第三，它在算法层面做了优化，平均复杂度接近O(n)，虽然最坏情况仍然是O(n²)，但实际处理几万个顶点也基本不卡顿。

2. 从耳朵到三角形的全部秘密：耳切法的原理与边界处理

理解了Earcut解决了什么问题之后，有必要拆开看看它内部是怎么干的。这不是为了重复造轮子，而是只有真正理解它的工作原理，才能在我们自己的项目里把它用到刀刃上。

2.1 耳朵是怎么定义的

要理解耳切法，第一步是搞清楚"耳朵"的数学定义。给定一个多边形的连续三个顶点A、B、C，如果角ABC是一个凸角（内角小于180度），并且以顶点B为顶点的这个小三角形内部，不包含当前多边形集合里的任何其他顶点，那么三角形ABC就是一个"耳朵"。

这个定义看起来简单，但在程序里判断却要注意几个边界情况。首先是凸点的判断：取A、B、C三点，通过向量叉积计算方向。叉积大于零，说明是凸角；小于零，说明是凹角；等于零，说明三点共线，这是一个需要单独处理的退化情况。Earcut对共线点的处理策略比较明确：共线的点不会形成有效耳朵，通常会被跳过或者在前置处理阶段剔除。

其次要判断"三角形内部不包含其他顶点"这一步。Earcut直接用了一个点在三角形内的判断函数，对当前剩余的所有顶点做一次遍历。这也是耳切法最耗时的部分，暴力遍历会让复杂度逼近O(n²)。Earcut在这里做了一项关键优化，利用一个哈希网格（hash grid）来缩小"哪些点可能需要检查"的范围，而不是每次都对全部顶点做包含判断。这一步直接决定了它面对大数据量时的性能上限。

2.2 一个被忽略的前置步骤：三角化前的排序与索引重排

Earcut的输入允许你传入洞的索引数组，它会先把外轮廓与洞统一处理成一个"带洞多边形集合"，然后做一次预处理排序。这一步做的事情是：通过比较所有环的某一点坐标，找到一个绝佳的起始点，然后对环的顶点顺序做一致性检查。

为什么要做这个？因为耳切法要求多边形顶点按固定方向（Earcut内部统一为逆时针）排列才能保证叉积符号判断正确。用户给的顶点顺序未必规范，特别是GIS数据里的轮廓顺序经常是乱的。Earcut会自动把外轮廓和洞统一到正确方向：外轮廓逆时针，洞顺时针。这样处理完之后，算法内部的所有符号判断才能统一。

这也是我一开始用Earcut经常理解错的地方。我总以为输入数据的顶点顺序会影响剖分结果，其实Earcut在内部已经做了方向重排。它对输入的唯一硬性要求是：每个环内的顶点顺序要保持连续（不能穿插），并且数据格式是二维或三维坐标的扁平数组。

2.3 洞口的处理思路

带洞多边形的三角剖分是很多自写方案望而却步的地方。直观上，耳朵不能穿过洞，否则三角形会跨越空洞区域。Earcut的做法比较巧妙：它在主轮廓上找一个合适的顶点，把洞"桥接"到主轮廓上，让主轮廓和洞合并成单个多边形的顶点序列。这个桥接点选择很重要，Earcut会找当前轮廓上视觉上最接近洞的一点，然后在两个环上各自切开，交叉连接，相当于给形状开了一条"割线"，绕洞走一圈再回来，这样就把原本带洞的问题转化为无洞的耳切问题，接下来交给同一套耳切流程处理。

这个桥接思路本身不算新鲜，但Earcut的聪明之处在于选择桥接点时用了可见性判断——只有主轮廓和洞之间的连线完全落在形状内部时才采纳，否则换个点尝试。如果没有合适的连接点，它会保守地认为这个洞无法处理。实际项目里遇到这种情况不多，但一旦出现，结果往往是剖分输出异常或直接报错，下一篇踩坑部分会展开说。

3. 上手实操：从拿到zip到跑通第一个三角剖分

理论部分讲完，该动手了。下面这套流程完全基于Earcut-Triangulation.zip包里提供的内容来走，我当初跑通的时候还没有这些理解，现在回头看，有几个步骤确实是可以直接"抄作业"的。

3.1 解压包和引入库

Earcut是零依赖的，源码就是一个JavaScript文件。在Node.js环境里直接require就行，在浏览器里也可以script标签引入后调用全局方法。

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]，表示两个三角形

这里值得解释一下返回值：这是一个扁平数组，每三个数构成一个三角形的三个顶点索引。上面的输出表示第一个三角形由索引1、0、3对应的三个点构成，第二个三角形由3、2、1对应的三个点构成。索引从输入坐标数组的第0个元素开始，按"第几个顶点"计数，而不是按数组下标计数。也就是说，X坐标是第0个顶点，Y坐标也是第0个顶点，两者共同占用数组里的两个元素，但索引只算顶点序号。

3.2 带洞多边形的输入格式

很多人在这一步栽过跟头。带洞多边形的调用多了一个参数：holeIndices。它表示每个内洞的起始顶点在整体顶点列表里的序号。

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);

关键点在于：外轮廓和洞的顶点是拼接在同一个数组里的，holeIndices里的值就是洞的起始顶点序号。如果外轮廓有4个顶点，那么第一个洞的起始序号就是4，第二个洞如果继续追加，起始序号要重新计算。另外，外轮廓和每个洞的顶点环都必须按环内顺序自然连续，不能把不同环的顶点穿插存储。

3.3 三维坐标怎么处理

Earcut的第三个参数是维度，默认值是2。如果你传入的是三维坐标数据（比如带高度的地理坐标），第三个参数传3，Earcut会自动按照前两个维度做剖分，第三个维度直接忽略，但索引计算时仍然按三维坐标的步长跳过。

const coords3d = [0, 0, 10, 100, 0, 10, 100, 100, 10, 0, 100, 10]; const triangles = earcut(coords3d, null, 3);

这个特性在做3D地形、建筑模型墙面投影、或WebGL渲染高度图时特别实用。不用额外把数据降维，直接传完整坐标，Earcut自己知道取前两维做平面剖分，输出索引依然对得上整个三维坐标数组。

3.4 用Canvas验证剖分结果

光有索引数组，不渲染出来，其实很难确认剖分是否正确。一个非常简单的验证方式是创建一个离屏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(); } }

渲染出来如果三角形之间有重叠或者覆盖住了洞的区域，说明剖分结果有问题。这里要特别强调一个很多人忽略的事项：三角形重叠并不一定说明Earcut出错。我遇到过一种情况是洞的方向是反的，导致Earcut桥接失败；或者输入多边形本身是自相交的，这类多边形属于"不可三角剖分"的几何范围，Earcut的文档里明确说了它不支持自相交多边形。后面我会专门说这个坑。

4. 实战场景对照：Earcut在哪些环节能派上大用场

讲了原理和用法，接下来分享几个我自己实际用到Earcut的场景，帮助你把"它能做什么"落在更具体的位置上。

4.1 WebGL地图地块渲染

这是Earcut的主场。地图上的国家边界、省市区边界、建筑物轮廓，动辄上万顶点。这些数据传入WebGL之前，必须变成三角形。Earcut在地图领域有非常成熟的应用案例，Mapbox Vector Tile的渲染就大量依赖它。它的性能优势和极低的内存占用，在这种"每一帧都要重新三角剖分"或者"一次性剖分大量多边形"的场景里会被放大到极致。

实际操作中需要注意一个细节：地理坐标系的经纬度数据不适合直接当平面坐标做剖分。因为经纬度在不同纬度上的实际距离不同，如果直接把经纬度当成平面坐标输入，剖分结果在高纬度地区会出现肉眼可见的变形。我一般的处理方式是先把经纬度投影到平面坐标系（如Web Mercator投影），再做剖分。Earcut本身不关心你的坐标单位，它只对平面坐标负责。

4.2 Canvas 2D复杂路径填充

如果你只是想在Canvas 2D里填充一个带洞的多边形，是不是不需要Earcut？大部分情况下确实不需要，Canvas自身的Path2D就能处理。但如果你的场景是"把任意多边形拆成三角形集合，再对每个三角形单独做渐变填充或者纹理映射"，Earcut就是不可替代的。

我做过一个地块染色工具，需求是每个地块内部按不同属性分区做斜向纹理填充。直接Canvas填充只能整块填，无法逐三角形做材质变化。用Earcut把地块剖分后，每个小三角形都能独立控制纹理角度和颜色，视觉效果细腻很多，渲染性能也稳定。

4.3 游戏碰撞体和物理引擎

游戏开发中，很多碰撞体形状是凸多边形，但关卡设计里的障碍物常常是凹的。大多数2D物理引擎（如Box2D）只支持凸多边形碰撞体，复杂的凹形状需要拆成多个凸多边形的组合。Earcut虽然不是专门做凸分解的，但可以先通过Earcut把凹多边形三角剖分，再把相邻三角形合并成凸多边形，或者直接把三角形网格作为碰撞体集合交给物理引擎。这在做2D横版关卡时是一条实用的管线。

严格来说，凸分解有更专门的库（比如poly2tri配合贝塞尔曲线预处理），但Earcut胜在集成成本低、结果稳定，适合对碰撞精度要求不是物理级苛刻的中小型项目。

5. 同场竞技：Earcut和其他三角剖分方案怎么选

在做项目选型的时候，Earcut不是唯一选择。下面把常见的几个方案放在一张表里对比一下，方便你按需选择。

如果你已经引入Three.js，ShapeUtils先用起来也不是不行，但它是为通用形状设计的，标准多边形的处理足够，复杂大顶点量的场景性能不如Earcut。反过来，如果你做的是CAD类工具，输入多边形可能蕴含大量不规范数据（如自相交），那Earcut的直接抛错或者异常输出会让你崩溃，这种情况建议直接上libtess.js。

选Earcut还有一个很实际的考量——它集成极简。我在一个老项目里试过换掉自写的三角化逻辑，改动量只有几十行，没有引入任何新依赖，因为Earcut本身就是一个文件。这种低成本无疑增加了我们做技术升级时的试错空间。

6. 绕不开的坑：真实项目里Earcut踩过的雷

这部分是全文的重点。Earcut虽然强大，但在真实业务数据上，边界情况远比单元测试复杂得多。以下这些坑，我从实战中一个个踩过来。

6.1 自相交多边形：文档里写得很清楚，踩的时候才长记性

Earcut官网文档有一句话：This library does not work with self-intersecting polygons。我当初不以为意，觉得真实业务数据怎么会有自相交，结果第一次接入GIS数据就撞上了。

多边形自相交指的是多边形的边与边之间有交叉，这种形状严格意义上不是一个合法的简单多边形。Earcut对它不保证任何输出——可能返回奇怪索引，可能直接卡住，也可能在耳切时把交叉区域错误填充。问题的根因在于耳切法本身依赖"点在三角形内部"的判断，自相交会破坏这个判断的正确性。

我的排查思路如下：

第一步，在调用eacut之前先用一条低成本的扫描线判断多边形是否自相交，如果自相交就进入容错分支；

第二步，容错分支里使用一个多边形拆分方法，在自相交点处把多边形切成多个合法多边形，再分别调用Earcut完成剖分。

这段代码是通用性质的，关键是找到自相交点并切割多边形，业内常称为"多边形正则化"。不建议自己造轮子，推荐使用turf.js里的polygon_self_intersection来处理，或者如果必须在一个文件里搞定，也可以直接用polygon-clipping库来做多边形归一化。总之不要心存侥幸，业务数据一旦来源不可控，自相交一定会出现。

6.2 重复点与共线退化：不报错但结果诡异

有时候你的输入顶点里包含完全重复的坐标点，或者三个连续顶点在同一水平线上。Earcut内部有去重和退化点剔除机制，大多数情况它会自动处理。但处理结果可能不是你想的那样，典型的特征是输出三角形数量少于预期。

比如你要给一个形状做面积估算，期望剖分出来50个三角形，结果只出来40个，一部分三角形面积被Earcut默认合并了。它之所以会这么做，是因为退化三角形（面积接近0）对渲染没有任何帮助，它的去重逻辑会优先牺牲这部分顶点，换来的是更稳定的索引输出。

这个行为在渲染上是优点，但在需要严格三角形计数或顶点一一对应的场景里，需要特别注意。如果你必须保持所有顶点都被使用，需要把共线点提前做偏移微调，或者改用其他允许约束的方案。我的处理方式是：在进入Earcut之前，对数据做一轮顶点清洗，把距离小于某个容差的点合并，并记录合并映射。这样既保证了Earcut内部的稳定性，又能让我们拿到准确的顶点与三角形的对应关系。

6.3 坐标数值过大带来的精度问题

地图数据经常使用带6位以上小数位的经纬度，或者超大范围的投影坐标系数值（比如X坐标在百万级别）。这种情况下浮点误差会被耳切法内部的叉积计算放大，典型表现是三角形之间出现细小的裂缝，这在渲染时表现为多边形边缘有锯齿或半透明缝隙。

Earcut虽然对数值精度有处理，但遇到极端跨度（一个多边形横跨几百公里）时，还是会遇到精度问题。我的实践是做一个"归一化预处理"：把多边形的所有坐标先减去包围盒的最小X和最小Y，让数值落在相对较小的范围内，三角剖分完成后再把顶点索引映射回原坐标值。这样做的代价很小，能明显提升剖分稳定性。如果你同时还要做碰撞检测，归一化后的坐标反而更容易做浮点运算。

6.4 带洞多边形桥接失败：无报错的异常输出

前面说Earcut在处理洞的时候做桥接，桥接需要主轮廓和洞之间有可见连接线。如果洞过度远离主轮廓，或者主轮廓太狭窄复杂，桥接可能失败。Earcut采用了一种缓存退避策略，如果找不到理想的桥接点，它可能会把洞当作独立的多边形单独剖分，而不是作为一个空洞排除。

这种异常的可怕之处在于：它不报错，也不返回异常值，只是三角形穿过了洞的区域，直观表现为纹理把洞填上了。排查方法是：三角剖分结束后做一个面积校验。从输入多边形算出外轮廓面积和洞面积，再从剖分结果算出所有三角形的总面积（带符号面积或绝对值面积都行），对比两者是否接近。如果差出一个洞的面积量级，就可以断定桥接失败。

修复桥接失败没有通用银弹，一个比较稳的做法是：在调用Earcut前，手动扩大洞的边缘，让洞与主轮廓保持一个合理的间隙；或者把洞的位置做一次微小平移，让桥接点更容易找到；实在不行，就把带洞多边形拆成多个无洞的多边形分别处理。工程上我认为第三招最靠谱，毕竟拆分后的结果是确定的、可控的。

7. 让Earcut更快：性能调优的几个实测方向

前面提到Earcut本身够快，但在大顶点量数据场景，还是可以通过一些手段压榨出更多性能。

7.1 预处理顶点合并

几千个顶点的多边形往往包含大量视觉上不敏感、但数值上存在微小抖动的点。在一次渲染场景里这些点没有影响，但在每帧都需要三角剖分的场景里，它们会显著拖慢速度。对我常用的地块数据，一个简单的Douglas-Peucker抽稀算法能把顶点数减少40%以上，而形状误差肉眼几乎不可见。Earcut的剖分时间跟顶点数强相关，所以抽稀是性价比最高的优化。

7.2 避免频繁创建大数组

Earcut的输入输出都是数组，JS引擎在GC时对超大数组的回收是有代价的。如果你在动画循环里频繁调用Earcut，建议复用输入数组而不是每次new一个新数组，同时缓存输出的索引数组以便复用。这一点在移动端WebGL场景下尤其敏感，我做过一次对比试验，复用数组的方案比每次新建数组的方案在长时间帧序列里能减少约30%的明显卡顿。

7.3 把Earcut放Web Worker里跑

如果你的多边形数据量极大（十万级顶点），Earcut的计算耗时可能超过16ms，这会导致动画掉帧。把Earcut丢到Web Worker里做剖分，主线程只负责接收索引并上传GPU，渲染和剖分流水线并行，体感流畅度会有质的提升。Earcut本身没有环境依赖，Worker里直接跑完全没问题，这也是它轻量属性带来的隐形福利。

8. 验证剖分正确性的标准化流程

最后分享一套我自己整理的验证清单。每当我改完三角剖分管线，都会按这套流程自测一遍，能拦截绝大多数隐藏问题。

• 面积一致性校验：计算输入多边形的有符号面积总和（外轮廓正、洞负），和剖分结果所有三角形的带符号面积之和做对比，误差超过0.1%视为剖分异常。
• 索引合法性校验：所有三角形索引必须在[0, 顶点数)这个区间内，出现负数或越界基本都是数据错误。
• 边界完整性校验：把剖分结果所有三角形的边收集起来，外轮廓的边界边出现次数必须是1，洞边界的边界边出现次数也必须是1；内部共享边出现次数必须是2。不满足说明剖分有裂缝或重叠。
• 洞区域校验：在带洞多边形场景中，随机采样洞内部几个点，确认这些点没有被任何三角形覆盖。

这套校验流程不用每次都跑全量的数学计算，但在数据源切换、Earcut版本升级、算法参数修改这三个节点上，最好都执行一遍。跑一次也就几毫秒，但能免去很多查半天查不出原因的渲染Bug。

做好这些前置校验，Earcut在绝大多数业务场景里都能稳定发挥。它虽然是个轻量到不能再轻量的库，但深入进去会发现，图形学里那些基础问题，真的到了工程落地上，处处都是细节。

本文还有配套的精品资源，点击获取