我们将地图引擎的多边形三角化器以小型库 earstrip 发布，采用与 earcut 相同的 ISC 许可证（ISC license）；它仅有一个 C++ 头文件，npm 上还有 WebAssembly 构建，参数同 earcut。C++ 下比 earcut.hpp 快 14%，浏览器中速度是 earcut.js 的 1.4 到 2.1 倍。GPU 只填三角形，地图却多是建筑、公园、停车场等多边形；华沙（Warsaw）的几个街区有 331 个多边形、5151 个顶点，会切成 4514 个三角形。马佐夫舍省（Masovian Voivodeship）的离线地图缩放级别 13 有 3,740,425 个多边形，M4 Pro 单核上引擎的约束德劳内（Delaunay）三角化器需 2.93 秒切完。

我们把地图引擎中的多边形三角化器以小型库 earstrip 的形式发布，采用 ISC 许可证（与 earcut 相同）。它只有一个 C++ 头文件，并在 npm 上提供 WebAssembly 构建，参数与 earcut 相同。在 C++ 中它比 earcut.hpp 快 14%，在浏览器中比 earcut.js 快 1.4 到 2.1 倍，文末附近有对比。接下来的内容讲的是我们如何做到这一点的。

GPU 只填充三角形，别的什么都不做。而地图主要由多边形组成：建筑、公园、停车场、两条有轨电车轨道之间的草带。下面是华沙 Śródmieście 的几个街区，这是我们的渲染器从地图文件中读取它们的方式。在任何一个轮廓被填充之前，每条轮廓都必须被切分成三角形。把鼠标悬停在多边形上，或点击它，就能看到它变成了什么。这些街区包含 331 个多边形、5,151 个顶点，最终变成 4,514 个三角形。

我们离线地图中马佐夫舍省（华沙周边地区）的缩放级别 13 有 3,740,425 个多边形。在 M4 Pro 的一个核心上，我们引擎中带约束的 Delaunay 三角化器切分所有多边形需要 2.93 秒。今年 10 月，我用耳切法（ear clipping）替换了它。为了写这篇帖子，我逐个想法地重建了耳切器，每个想法一个提交，并在同样的 370 万个多边形上给每个提交计时，因此下面每一节最后都有一个数字。

Delaunay

当没有任何点位于任意三角形三个顶点所确定的圆内时，一组点的三角剖分就是 Delaunay。共享一条边的两个三角形足以说明这条规则如何工作。拖动点 D 可以看到：最小角为 45°；若换成 BD，则会是 37°。

只要 D 保持在过 A、B、C 的虚线圆之外，共享边就是 AC。当 D 进入圆内，边会翻转成 BD；再移出去又会翻回 AC。每次翻转都是一次局部修复，而没有任何边想要翻转的三角剖分就是 Delaunay。在同样这些点的所有三角剖分方式中，它拥有最大的最小角。橙色弧标记了两个三角形的最小角，图下方的线显示了另一条对角线会给出的结果：无论你把 D 放在哪里，圆规则选中的那条边都会胜出。

“带约束”是指多边形自身的边必须保留为三角剖分的边，即使在圆规则会把它们翻转掉的地方也是如此。我们的三角化器逐个插入顶点。对于每个新点，它会遍历目前已构建的三角形，直到找到该点落入的那个三角形，将其拆分，并围绕新点翻转边，直到圆规则重新成立。它还会强制把多边形的边加入，最后只保留位于多边形内部、且在其孔洞外部的三角形。

当你需要在三角形上插值或跑模拟时，形状良好的三角形很重要。但纯色填充并不在乎：GPU 填充一个针尖般的细三角形和填充一个胖三角形一样正确。而且大部分工作花在几乎不需要处理的多边形上。马佐夫舍的多边形中近一半（180 万个）顶点数不超过四个。三角形根本不需要切分，凸四边形就是两个三角形，但 Delaunay 代码却在它们上面花了 419 ms，每次都从头构建三角剖分。

耳朵

多边形的“耳朵”是可以用一条直线切掉的一个角。取三个连续顶点 a、b、c。如果 b 处的角是凸的，且多边形没有其它部分伸入三角形 abc，那么这个三角形就是一只耳朵。把它切掉，剩下的就是一个顶点少一个的多边形。1975 年，Gary Meisters 证明：每个顶点数多于三的简单多边形至少有两只互不重叠的耳朵。因此总是还有下一只耳朵可切，一个有 n 个顶点的多边形会分解成 n − 2 个三角形。

上面街区中的一栋建筑就是例子。移动滑块可以逐个切掉它的耳朵（进度 0 / 25）。绿色三角形是下一个要被切掉的耳朵。算法需要一个测试：“这个角是耳朵吗？”最简单版本先检查该角，然后检查边界上的所有其它顶点。cross 是每个几何代码库中都有的 2×2 行列式；当 c 位于从 a 到 b 的直线左侧时它为正，因此对于逆时针方向的边界，cross(a, b, c) > 0 表示凸角。isEar 先检查角的方向，若不向左转就直接返回 false；然后遍历边界上除 a、b、c 外的每个顶点 p，只要 p 不在三角形 abc 外的任何一侧（即三个 cross 都不小于 0），且 p 不与 a、b、c 重合，就说明有其它部分伸入三角形，该角不是耳朵。

位于三角形边上的点也算在内部：如果耳朵碰到了边界的其余部分，切掉它会留下一个自接触的多边形。唯一的例外是恰好位于 a、b 或 c 位置的点，这发生在某条轮廓在单个顶点处自交时。孔洞让这种情况变得常见。

孔洞

耳切法只能作用于一条闭合边界，而马佐夫舍的多边形中有 11,345 个带孔洞，比如庭院和林间空地。处理办法是把每个孔洞切开，用一条“桥”把它缝到外环上：桥是从孔洞的一个顶点到边界的一个顶点的边，来回各走一次。边界于是绕外圈走，跨过桥，以相反方向绕孔洞一圈再回来。桥的两份副本之间没有面积，所以多边形保持不变，但现在它是一条环。

桥不能穿过任何东西。David Eberly 的耳切法说明有一个巧妙的找桥方法。取孔洞最右的顶点 m，向右投射一条射线。射线命中的第一条边（交于 I）有一个更靠右的端点 P。如果三角形 m、I、P 内没有边界顶点，那么桥 m–P 就是安全的。拖动孔洞可以看到两种情况：如果凹点的尖端位于三角形 m、I、P 内，那么连到 P 的桥会穿过边界，于是桥改连到该凹点。若三角形为空，桥就连到 P；若某个凹点的尖端位于三角形内，桥就改连到该凹点。对于三角形内的多个凹点，Eberly 会选与射线夹角最接近的那个。孔洞按最右优先连接，因此更左侧的孔洞可以连到已经属于边界的另一个孔洞。

地图数据本身还带来两种情况。我们的坐标是瓦片网格上的整数，因此沿网格线的射线会一直延伸；相交测试会跨过这样的顶点，而我的第一个版本正好弄错了这种情况。另外，制图者常画出一个在某点与外环共享顶点的庭院。这样的孔洞不需要桥：两条环在共享顶点处已经相连。

朴素裁剪器（−1,812 ms）

孔洞接上桥之后，第一个完整版本绕边界走，用上面的 isEar 测试各个角，切掉找到的每一只耳朵，并把每个三角形写成三个索引。在马佐夫舍的多边形上它耗时 1.12 秒，比 Delaunay 快 2.6 倍。图表按多边形大小拆分了每次耗时；下面是按大小类别排列的时间：

• Delaunay：2,931 ms
• 1. 朴素耳切：1,119 ms
• 2. 只测凹点：882 ms
• 3. 凸多边形捷径：880 ms
• 4. 锯齿状三角带：762 ms
• 5. 分桶：697 ms
• 6. 无分支：519 ms
• 7. 标记命中：489 ms

大小类别为：最多 4 个顶点、5–8 个顶点、9–32 个顶点、33–256 个顶点、257 个及以上顶点。

除了最后一类，朴素耳切在每个大小类别上都比 Delaunay 短。最大的 1,123 个多边形（顶点数 257 及以上）用耳切需要 199 ms，而 Delaunay 只要 90 ms。那里的每次耳朵测试要遍历数百个顶点，而一个多边形需要数百次测试，因此成本随大小的平方增长。后面的内容讲的是如何让耳朵测试更便宜、且更少被用到。

只测试凹点（−237 ms）

看看哪些顶点真正能阻止一个凸角成为耳朵。假设有一些顶点落在它的三角形内，取离该角最近的那个。它的两条边不可能穿过三角形的两条边，因此都朝离开该角的方向往回走，多边形从该角的一侧绕过了这个顶点。这让它成为一个反射顶点，即凹点。因此，如果三角形内有任何东西，里面一定也有一个凹点，测试只需检查凹点。

引擎维护一个凹点列表。当切掉相邻耳朵使某个凹点变凸时，它就离开列表；而凸角永远不会变成凹点，所以列表只会缩短。测试变成先检查 b.reflex（若是凹点直接返回 false），然后只遍历 _items 中的凹点，跳过 a 和 c，做与之前相同的三角形内外判断；若凹点与 a、b、c 不重合且位于三角形内，则返回 false。

2810 万次耳朵测试现在只查看 1.85 亿个点，而不是 3.53 亿个，总时间降到 882 ms。这比预期要少，因为建筑轮廓有很多凹点。上面那栋带拱门的建筑在 27 个顶点中有 15 个凹点。最小的多边形反而变慢了，从 34 ms 增加到 54 ms：对于三角形或四边形，把角分成凹点和非凹点的开销超过了它省下的遍历开销。

凸多边形跳过测试（−2 ms）

没有凹点的多边形是凸的，而凸多边形的每个角都是耳朵，因此可以一次测试都不做就切完。但检查这一点需要小心。“每个角都向左转”还不够：五个角都向左转（5/5），但 x 方向变化了 4 次，因此不是凸多边形。

这个星形在五个角上都向左转，因为它绕中心转了两次。引擎增加了一个条件：沿着凸环绕行时，边在底部向右、在顶部向左，因此 x 方向恰好在最左和最右点改变两次。星形在四个圈出的角上改变了方向四次，于是交给普通的耳朵测试。这两个计数都来自标记凹点的同一个循环，因此检查几乎不花代价。三角形和四边形在循环之前还有自己的捷径。

这个捷径去掉了 2810 万次耳朵测试中的 440 万次，但这些本来就是最便宜的：没有凹点的环没有东西可扫描。单靠它几乎不改变总时间（降到 880 ms），尽管顶点数不超过四的多边形赢回了凹点带来的部分损失，从 54 ms 回到 48 ms。它在下一步更重要，因为凸环会变成一条三角带。

写入三角带（−118 ms）

到目前为止每个三角形要花三个索引。GPU 也可以绘制三角带（triangle strip），其中每个新索引都会与前面两个索引组成一个新三角形。如果以锯齿形穿过凸环，它就能形成一条带：0 1 7 2 6 3 5 4。

耳切器也能写三角带。切掉一只耳朵会让相邻两个角变得更尖，因此它们是下一只耳朵的好候选；切掉其中一个只需增加一个索引就能延长三角带。引擎优先尝试这两个邻居，并在两端之间交替，直到没有耳朵为止。在代码中，被切顶点的邻居是 a 和 b，循环交替从 a 的前端或 b 的后端取下一个索引并解除链接。当下一个角不是耳朵时，三角带结束，遍历从停下的地方继续。

2150 万个三角形现在只需要 3580 万个索引，而不是 6450 万个。耳朵测试次数并没有减少：朴素的遍历本来就在切完后走到下一个角，而现在每条三角带还会以一次失败的测试结束，测试数从 2370 万增加到 2500 万。尽管如此，总时间降到 762 ms，最大的一类多边形从 146 ms 降到 103 ms。

把凹点分到桶里（−65 ms）

森林或湖泊可能有数千个顶点和数百个凹点，而每次耳朵测试仍要读取每一个凹点。当多边形有超过 32 个凹点时，引擎会沿包围盒较长的一侧把凹点分到桶里，每个桶约两个凹点。耳朵测试只看它的三角形所跨越的那些桶。随着凹点变凸并离开，索引会在一半桶消失后重建。

扫描的点数从 1.81 亿降到 1.01 亿，几乎全部收益都来自大多边形：顶点数 257 及以上的多边形从 103 ms 降到 57 ms。总时间：697 ms。

无分支计数（−178 ms）

凹点测试的循环会在三角形内第一个凹点处退出。但大多数时候三角形内并没有凹点：测试读完所有凹点后返回“是”。这时提前退出毫无收益，而每个点的三次比较都是 CPU 需要预测的分支。引擎先跑一遍完全无分支的计数，只统计三角形内的凹点数量：取三个行列式的最小值，若非负则命中加一；只有当计数不为零时，才运行之前的精确循环，以排除正好落在角上的凹点。分桶版本用包围盒测试做同样的事，一次把 64 个点压入一个位掩码。

三个行列式中最小的一个非负，恰好说明点位于闭合三角形内。总时间降到 519 ms，中等大小的多边形受益最大：顶点数 33 到 256 的多边形从 327 ms 降到 216 ms。

只测试已标记的凹点（−30 ms）

当计数不为零时，精确循环会再次读取所有凹点，尽管第一遍已经知道哪些在里面。分桶版本把这些信息保留在位掩码里。最多 32 个凹点的短列表也可以这样做：第一遍为每个命中设置一个比特而不是计数，精确测试只查看这些被标记的凹点。读取的点数从 1.28 亿降到 1.20 亿。这是最后一步，也就是已发布的 earstrip 的代码：489 ms，在同一批多边形上耗时只有 Delaunay 的六分之一（快 6.0 倍）。

当没有耳朵时

Meisters 定理针对的是简单多边形。地图数据会被舍入到瓦片网格，而舍入可能破坏简单多边形。下面是Warszawa Śródmieście（距离上面那片街区不到一公里的一个火车站）的轮廓，按不同大小的网格舍入后的结果。橙色环标记的是与相邻顶点落到同一点的顶点：网格步长 73 cm，154 个顶点中有 68 个与相邻顶点重合，84 个三角形。

每瓦片边 12 位时，也就是我们地图文件使用的网格，网格步长是 18 cm。即便如此，154 个顶点中仍有 31 个与相邻顶点合并，因为制图者常把点放在相隔几厘米的位置，而轮廓仍能存活。（某一位数下）近一半顶点合并，裁剪器仍能切分它。舍入后的轮廓以某种方式自接触，导致完全没有耳朵；而在 10 位时它又碰巧能工作了。

当裁剪器绕边界走完一圈都没找到耳朵时，它会丢掉没有面积的角，再走一圈。如果还是失败，它就放弃，引擎会改用仍保留的 Delaunay 代码来三角化该多边形。在马佐夫舍的数据中有 76 个多边形走到这一步。它们来自另一端上次改动之前构建的地图：我们的地图生成器现在会用 GEOS 的 snap rounding 把每个多边形舍入到最终网格，并检查耳切能切分它。在马佐夫舍地图的一次全新构建中，这修复了 273 个多边形，于是文件中每个多边形都能被耳切切分。

Delaunay 还有一项工作。每个孔洞都需要自己的桥，而找桥要扫描整个边界，因此有数千个孔洞的多边形要付出数千次扫描的代价。我们的世界地图中有一个带 11,675 个孔洞的多边形：耳切在它上面要 606 ms，Delaunay 只要 17 ms。引擎现在把每个有 128 个及以上孔洞的多边形交给 Delaunay。在马佐夫舍的数据中，这样的多边形有两个。

库把这两种回退都保留在里面。当耳朵用尽、当留下的三角形覆盖了错误的面积、以及当环数超过 128 时，earstrip 会对环边做带约束的 Delaunay 三角剖分；C++ 中的 run() 和 JavaScript 中的 lastStatus() 会说明某个多边形走了哪条路径。在我们世界地图瓦片的 56,472 个多边形上（其中一个有多达 11,675 个孔洞），earstrip 耗时 459 ms，earcut.hpp 耗时 2,892 ms。在耳朵无法精确切分的缩放级别 13 多边形上，earcut 的三角形与环的 even-odd 填充平均在 31% 的像素上不同，earstrip 只有 0.15%。

在浏览器中

在新型裁剪器进入应用之前，我把它和 earcut（MapLibre 和 Mapbox GL 背后的耳切器）的 C++ 版本 earcut.hpp 3.2.4 做了对比。原生情况下两者很接近，本来可能到此为止。但我们正在做一个 web 渲染器，运行的是编译成 WebAssembly 的同一个 C++ 引擎，所以我进一步比较了浏览器端：两个裁剪器都编译成 WebAssembly，以及 earcut.js 3.2.4（当今 web 地图运行的 JavaScript 原版）。为此我把裁剪器从引擎里抽出来做成了 earstrip。在我们测试集的 580 万个多边形上，它写出的三角带与引擎完全一致，其仓库里有这些多边形以及本节每个数字背后的代码。它的原生基准就是上面图表背后的那一个，下面的原生行是最后一步与 earcut.hpp 的对比。每个 WebAssembly 构建在缩放级别 13 和 9 的 440 万个多边形上，都与原生版本给出完全相同的三角形。下面是缩放 13 的 374 万个多边形的毫秒数（取 7 次中最好，单线程，Node 中的 V8 和 Bun 中的 JavaScriptCore）：

| | earstrip | earcut | | --- | --- | --- | | 原生 C++ | 489 | 557 | | WebAssembly，循环在模块内，V8 / JSC | 601 / 566 | 930 / 843 | | WebAssembly，每个多边形一次从 JS 调用，V8 / JSC | 688 / 688 | 1,007 / 950 | | npm 包，每个多边形一次调用，V8 / JSC | 766 / 807 | 1,103 / 1,290 | | npm 包，直接调用，所有多边形一次调用，V8 / JSC | 635 / 619 | |

原生情况下，earcut.hpp 比 earstrip 慢 14%。编译成 WebAssembly 并在 V8 中运行时，earstrip 损失 23%，earcut.hpp 损失 67%，几乎全都损失在它搜索耳朵的主循环里。这不是分配器的问题：用 mimalloc 和 emmalloc 构建的时间相同。我没有继续深挖。在 V8 中，WebAssembly 版的 earcut.hpp 最终只比纯 earcut.js 快 19%，而如果每个多边形都从 JavaScript 单独调用，则只快 10%。

npm 包那几行是网页实际得到的结果，其中的 earcut 列就是 earcut.js。用来替代 earcut 的调用以 JavaScript 数字接收坐标，并每次返回一个新的三角形索引数组：在 V8 中比 earcut.js 快 1.4 倍，在 JavaScriptCore 中快 1.6 倍。相比模块内循环，它损失的性能约一半花在把坐标复制进去、把三角带转成列表，其余花在每个多边形调用一次 WebAssembly。直接调用跳过了所有这些：多边形直接进入模块内存，并以一个用于 WebGL 2 或 WebGPU 的三角带索引缓冲区返回，比 earcut.js 快 1.7 到 2.1 倍。

上面的一些思路 earcut 也有。它也依赖“只有凹点会挡住耳朵”这一点，但它是最后才检查这一条，对每个通过包围盒和三角形测试的顶点都查一遍，而不是维护凹点列表。超过 80 个顶点时，它会按 z 序把它们链接起来，只扫描三角形包围盒覆盖的那段曲线，这起到了分桶的作用。它没有的是凸多边形捷径、三角带和无分支计数：它每个三角形写三个索引，并在内部第一个点处停止。

earstrip 已在 GitHub 和 npm 上发布，包含这篇文章中的多边形，以及在你自己机器上对它和 earcut 计时的代码。

多数人在肯定 Earstrip 性能提升和文章质量的同时，追问它与其他三角化库/覆盖引擎的基准对比，并担心狭长或“暴力”三角网会影响渲染。少数人（Earcut 作者）则提醒为控制打包体积应主动放弃部分优化，实际场景够用即可；此外还有少数声音质疑对三角形的执念，认为只求面积或点位置时不必三角化，并追问 LLM 与人类在优化步骤中的分工。

称赞性能提升和文章质量，并想借用优化思路

• 多位评论者认为优化后的性能提升很惊艳，文章本身也写得很好；Earcut 作者还表示想看看有没有能借给 JS 版的技巧。（较多人） > 文章写得很棒，库也很酷，我想看看有没有能借给 Earcut JS 版的技巧。（@mourner）

想看它与其他三角化库或覆盖引擎的基准对比

• 有人提到 CMU 的 Triangle 库，也有人希望它和 GeoRust 的 iShape-rust 覆盖引擎做基准测试；Delaunay32 作者则好奇自己的分治式约束 Delaunay 三角化器与本文 Delaunay 基线相比如何，并感谢公开数据集。（较多人） > 不知道它和 GeoRust 的 iShape-rust 覆盖引擎相比基准表现如何。（@willtemperley）

为控制体积应放弃部分优化，实际够用即可

• Earcut 作者表示，为了不让打包体积膨胀，他故意拒绝了一些潜在优化；对 Mapbox GL JS 等大多数实际应用来说，压缩后约 4.1k 的 Earcut 已经足够快，小库不必追极限性能。（少数人） > 我故意拒绝了一些潜在优化，以控制库体积、避免打包体积膨胀——对大多数实际应用来说它已经够快了。（@mourner）

担心三角化结果太“暴力”或狭长，影响渲染

• 有人觉得产出的拓扑有些“暴力”，想知道对渲染到底有多大影响；也有人问挑出又长又窄的三角形会不会有问题，因为人来做通常会尽量选更均衡的三角形。（较多人） > 它挑出又长又窄的三角形时会有问题吧？人来做通常会尽量选更均衡的。（@Gravityloss）

想知道哪些优化来自 LLM、哪些必须有人类辅助

• 有评论者很好奇作者是否愿意透露，各个优化步骤里哪些是 LLM 自己想出来的，哪些需要人类协助才能完成。（少数人） > 很好奇你愿不愿意透露哪些优化是 LLM 想出来的、哪些必须有人类辅助。（@swiftcoder）

认为只求面积或点在多边形内外时不必执着于三角化

• 有评论者质疑对三角形的执念：若只是算面积或判断点是否在形状内，用顶点坐标的行列式（鞋带公式）直接求有向面积即可，反向环还能表示空洞，不必先做三角化。（少数人） > 要是只想知道面积或点是否在形状内，其实有更好的办法，不必非得三角化。（@airbreather）

有价值的补充

• Mapbox 在 C++ 侧改用混合方案：小多边形继续用 earcut.hpp，大而复杂的多边形则切换到基于单调分解（monotone decomposition）的算法；后者虽然算法复杂度常数更高，但随输入规模增大扩展性更好。（@mourner）
• 鞋带公式的具体做法：把多边形顶点按顺序连成环（如 a,b,c,d,a），对相邻顶点做 Ax×by − ay×bx 这类行列式并累加，结果除以 -2 即得有向面积；正数表示顺时针、负数表示逆时针，把内圈写成相反方向即可表示甜甜圈（带洞多边形）。（@airbreather）
• CMU 的 Triangle 项目被称作“所有三角化器之母”，是三角化领域常被引用的经典库。（@amelius）
• Delaunay32 是支持多边形和洞的约束 Delaunay 三角化器，采用分治而非增量插入；其当前 API 要求简单环且洞之间不接触，作者尚未在本文数据集上基准测试，但认为公开数据集对后续对比很有用。（@morishuz）