比 earcut 更快：374 万个地图多边形，489 毫秒切完

我们把地图引擎里的多边形三角化器抽出来，做成了一个小型库，叫 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 秒才能把它们全部切分完。今年十月，我用耳切法替换了它。为了写这篇文章，我把耳切器按一个个思路重新搭了一遍，每个思路对应一次提交，并在同样的 370 万个多边形上为每次提交计时，因此下面每一节的结尾都会给出一个数字。

Delaunay

当没有任何点落在任意三角形三个顶点所确定的圆内时，这组点的一个三角化就是 Delaunay 三角化。只要看两个共边的三角形，就能明白这条规则是怎么起作用的。

当 D 位于经过 A、B、C 的虚线圆之外时，共享边是 AC。把 D 推进圆内，边就翻转为 BD；再拉出来，又翻回去。每次翻转都是一次局部修复，而没有任何一条边想要翻转的三角剖分，就是 Delaunay 三角剖分。在把同一组点三角剖分的所有方式中，它的最小角最大。橙色圆弧标出的是两个三角形的最小角，图下方的文字给出另一条对角线会得到的结果：无论你把 D 放在哪里，圆规则选中的那条边都更优。

“受约束”意味着多边形自身的边必须保留在三角剖分中，即使圆规则想把它们翻转掉。我们的三角剖分器逐个插入顶点。对每个新点，它先沿着目前已构建的三角形行走，找到该点落入的那个三角形，将其拆分，再围绕新点翻转边，直到圆规则重新成立。它还会强制把多边形的边纳入进来，最后只保留位于多边形内部、且在其孔洞之外的三角形。

当你跨三角形做插值或在上面跑模拟时，形状良好的三角形很重要。纯色填充不在乎这些：GPU 填充一个针一样细的三角形和一个胖三角形一样准确。而大部分工作量都花在几乎不需要剖分的多边形上。马佐夫舍的多边形中将近一半（180 万个）只有四个或更少的顶点。三角形根本不需要切割，凸四边形就是两个三角形，可 Delaunay 代码却在它们身上花了 419 ms，每个都从头构建三角剖分。

耳

多边形的耳是能用一刀直线切掉的一个角。取三个连续的顶点 a、b、c。如果 b 处的角是凸角，且多边形的其他部分都不伸进三角形 abc 内，那么这个三角形就是一只耳。把它切掉，剩下的就是一个少了一个顶点的多边形。1975 年，Gary Meisters 证明了每个顶点数大于三的简单多边形至少有两个互不重叠的耳。所以总有下一只耳可切，一个 n 顶点的多边形最终会拆成 n − 2 个三角形。

这是上面那些街区里的一栋建筑。

绿色三角形是下一个被切掉的耳。算法只需要回答一个问题（“这个角是耳吗？”），最简单的版本会检查该角，再检查边界上的其他每个顶点。cross 是每个几何代码库里都能见到的 2×2 行列式；当 c 位于 a 到 b 这条直线的左侧时它为正，所以对于逆时针走向的边界，cross(a, b, c) 为正就意味着这是一个凸角：

static double cross(double ax, double ay, double bx,
                    double by, double cx, double cy)
{
    return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax);
}

bool isEar(uint32_t v) const
{
    const Node &b = _nodes[v];
    const Node &a = _nodes[b.prev], &c = _nodes[b.next];
    if (cross(a, b, c) <= 0)
        return false; // turns the wrong way, or not at all
    for (uint32_t w = c.next; w != b.prev;
         w = _nodes[w].next) {
        const Node &p = _nodes[w];
        if (cross(a.x, a.y, b.x, b.y, p.x, p.y) < 0 ||
            cross(b.x, b.y, c.x, c.y, p.x, p.y) < 0 ||
            cross(c.x, c.y, a.x, a.y, p.x, p.y) < 0)
            continue; // outside the triangle
        if (!samePos(p, a) && !samePos(p, b) &&
            !samePos(p, c))
            return false;
    }
    return true;
}

落在三角形边上的点算作内部：如果耳朵碰到了边界的其余部分，切掉它就会留下一个自接触的多边形。唯一的例外是恰好位于 a、b 或 c 位置上的点，这出现在轮廓在单个顶点处与自身相接的地方。有洞时这种情况很常见。

洞

耳切法只处理一条闭合边界，而马佐夫舍的多边形中有 11,345 个带洞，比如庭院和林中空地。处理办法是把每个洞切开，用一座桥把它缝到外环上。桥是从洞的一个顶点连到边界一个顶点的边，正反各走一次。这样边界先绕外圈走，过桥，反向绕洞一圈，再回来。桥的两份副本之间没有面积，所以多边形本身没变，只是现在成了单环。

桥不能与任何东西相交。David Eberly 的耳切法文章给出了一个找桥的巧妙办法。取洞最右侧的顶点 m，向右投射一条射线。射线碰到的第一条边在 I 处，该边有一个端点 P 更靠右。如果没有边界顶点落在三角形 m、I、P 内部，那么桥 m–P 就是安全的。

三角形靠上的部分为空，桥就连到 P。靠下时凹口的尖端落在三角形里，桥就改连到凹口上：三角形内若有多个凹口，Eberly 取角度上最接近射线的那一个。桥接从最右侧的孔开始，因此更靠左的孔可以桥接到已经并入边界的孔上。

地图数据还带来两种自身特有的情况。我们的坐标是瓦片网格上的整数，沿网格线走的射线会不断正好穿过顶点；交点测试会直接跨过这样的顶点，我最初的版本恰恰在这个情况上出了错。另外，制图者经常画出只在外墙上一点相接的庭院。这样的孔洞不需要桥：两个环在共享顶点处已经相连。

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

孔洞桥接完成后，第一个完整版本沿边界走一圈，用上面的 isEar 测试各个角，每找到一个耳就切掉，并把每个三角形写成三个索引。在马佐夫舍的多边形上耗时 1.12 秒，比 Delaunay 快 2.6 倍。下图按多边形大小拆分每次的耗时：

朴素那一行在除最后一档外的每个尺寸档上都比 Delaunay 短。最大的 1,123 个多边形有 257 个或更多顶点，裁剪耗时 199 ms，用 Delaunay 则是 90 ms。在这里，每次耳测试都要遍历数百个顶点，而一个多边形需要数百次测试，因此开销随其规模的平方增长。本文余下的部分讲的是如何让耳测试更便宜、也更少被用到。

只测试凹点（−237 ms）

先看看哪些顶点才真正能阻止一个凸角成为耳。假设有一些顶点落在它的三角形内，取其中离该角本身最近的那个。它的两条边不可能穿过三角形的边，所以两条边都朝回延伸、背离该角，多边形从该角这一侧绕过那个顶点。这就使它成为一个凹顶点，也就是一个凹点。因此，只要三角形内有任何东西，其中就一定有凹点，测试只需检查凹点即可。

引擎维护着一份凹点列表。当切掉某个凹点的邻居使它变成凸点时，它就离开列表；而凸角永远不会变成凹点，所以这份列表只会缩短。测试变成：

bool isEar(uint32_t v) const
{
    const Node &b = _nodes[v];
    if (b.reflex)
        return false;
    const Node &a = _nodes[b.prev], &c = _nodes[b.next];
    for (uint32_t i = 0; i < _live; ++i) {
        const Item &p = _items[i]; // a dent
        if (p.node == b.prev || p.node == b.next)
            continue;
        if (cross(a.x, a.y, b.x, b.y, p.x, p.y) < 0 ||
            cross(b.x, b.y, c.x, c.y, p.x, p.y) < 0 ||
            cross(c.x, c.y, a.x, a.y, p.x, p.y) < 0)
            continue;
        if ((p.x != a.x || p.y != a.y) &&
            (p.x != b.x || p.y != b.y) &&
            (p.x != c.x || p.y != c.y))
            return false;
    }
    return true;
}

这 2,810 万次耳测试现在只需检查 1.85 亿个点，而不是 3.53 亿个，总耗时降到 882 ms。这比你预期的要少，因为建筑轮廓有很多凹点。上面带拱门的那个建筑，27 个顶点里有 15 个是凹点。而最小的多边形反而变慢了，从 34 ms 升到 54 ms：对于三角形或四边形，把角分成凹点和其余部分，比省下的那次遍历开销更大。

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

没有凹点的多边形就是凸的，而凸多边形的每个角都是耳，因此可以不做任何测试就切掉。检查这一点需要小心。“每个角都向左转”并不够：

五角星的五个角都在向左转，因为它绕自身中心转了两圈。引擎又加了一个条件。沿凸环走一圈，底边方向朝右，顶边方向朝左，因此 x 方向恰好变化两次，分别在最左端和最右端的点上。五边形通过；五角星在有圆圈的角上变了四次方向，于是进入普通的耳测试。这两个计数都出自标记凹角的同一个循环，所以这项检查几乎不花代价。三角形和四边形在那个循环之前走自己的捷径。

这条捷径省掉了 2810 万次耳测试中的 440 万次，但那些是最便宜的：没有凹角的环没什么可扫的。单靠它，总时间几乎不变，880 ms；不过顶点数不超过四的多边形把凹角带来的开销补回了一部分，从 54 ms 降到 48 ms。它在下一步更要紧，那一步把凸环变成一条条带。

写成条带（−118 ms）

到目前为止，每个三角形要花三个索引。GPU 也能画 triangle strip（三角带）：每加一个新索引，就多出一个由它和前两个索引构成的三角形。凸环只要来回折着走，就能写成一条 strip：

耳切法也能生成条带。切掉一只耳会让相邻两个角的夹角变尖，它们因此成为下一只耳的好候选；切掉其中之一，又能把条带延长一个索引。引擎会优先尝试它们，并在两端之间来回交替，直到耳朵用尽。代码里，被切顶点的两个邻居是 a 和 b：

// The next ear alternates between the ends of the cut.
while (true) {
    if (sideA) {
        const uint32_t z = n[a].prev;
        _strips.push_back(n[z].index);
        unlink(a);
        a = z;
    } else {
        const uint32_t z = n[b].next;
        _strips.push_back(n[z].index);
        unlink(b);
        b = z;
    }
    count--;
    sideA = !sideA;
    if (count < 3 || !isEar(sideA ? a : b))
        break;
}

下一个角不是耳朵时，条带结束，遍历从停下的地方继续。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 必须预测的分支。引擎先跑一遍只统计三角形内凹点数量、完全无分支的流程：

const double abx = b.x - a.x, aby = b.y - a.y;
const double bcx = c.x - b.x, bcy = c.y - b.y;
const double cax = a.x - c.x, cay = a.y - c.y;
uint32_t hits = 0;
for (uint32_t i = begin; i < end; ++i) {
    const Item &p = items[i];
    const double side = std::min(
        std::min(abx * (p.y - a.y) - aby * (p.x - a.x),
                 bcx * (p.y - b.y) - bcy * (p.x - b.x)),
        cax * (p.y - c.y) - cay * (p.x - c.x));
    hits += (uint32_t)(side >= 0) & (uint32_t)(p.node != ia)
          & (uint32_t)(p.node != ic);
}
if (hits == 0)
    return true;

三个行列式中的最小值非负，当且仅当该点落在闭三角形内。只有计数不为零时，才运行之前那个精确循环，排除恰好落在角上的凹点。分桶版本用包围盒测试做同样的事，一次把 64 个点读进一个位掩码。总耗时降到 519 ms，中等规模收益最大：33 到 256 个顶点的多边形从 327 ms 降到 216 ms。

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

当计数不为零时，精确循环会重新读取所有凹点，尽管第一遍已经看过哪些凹点落在内部。分桶版本把这一信息保存在位掩码里。短列表（最多 32 个凹点）也能这么做：第一遍每命中一个凹点就置一位，而不是计数，精确测试只看这些凹点：

    hits |= ((uint32_t)(side >= 0) & (uint32_t)(p.node != ia)
             & (uint32_t)(p.node != ic)) << (i - begin);
}
while (hits) {
    const Item &p = items[begin + lowestBit(hits)];
    hits &= hits - 1;
    // the exact test from before
}

读取的点数从 1.28 亿降到 1.2 亿。这是最后一步，也正是 earstrip 已发布版本的代码：489 ms，比同样多边形上的 Delaunay 快 6.0 倍。

没有耳的时候

Meisters 定理针对的是简单多边形。地图数据会被舍入到瓦片网格上，而舍入可能破坏简单多边形。下图是 Warszawa Śródmieście 的轮廓，一座距上面那些街区不到一公里的火车站，分别舍入到不同大小的网格。橙色圆圈标出的是与相邻顶点落在同一点的顶点：

地图文件每块瓦片边长为 14 位时，一个网格步长是 18 厘米。即便在这个精度下，154 个顶点中仍有 31 个与相邻顶点合并，因为制图者常把点放在相距几厘米的位置，而轮廓依然能保留下来。到 12 位时近一半顶点合并，裁剪器仍能切出结果。到 11 位时，取整后的轮廓以某种方式自接触，完全留不出耳朵；到 10 位时又碰巧能用了。

当裁剪器沿边界走完一整圈都找不到耳朵时，它会丢掉那些没有面积的角点，再走一遍。如果还是失败，它就放弃，由引擎改用 Delaunay 代码对这个多边形做三角剖分，这段代码就是为此保留的。在 Masovian 数据中有 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 的三角形与环的奇偶填充平均有 31% 的像素不一致，earstrip 则是 0.15%。

浏览器端

在新的裁剪器进应用之前，我把它和 earcut 比了一轮，就是 MapLibre 和 Mapbox GL 背后用的那个耳切器，用的是它的 C++ 版本 earcut.hpp 3.2.4。原生环境下两者差距不大，本来可以到此为止。但我们在做一个 Web 渲染器，跑的是同一套编译成 WebAssembly 的 C++ 引擎，所以我又往下比了浏览器这一侧：两个裁剪器都编译成 WebAssembly，再加上 earcut.js 3.2.4，也就是现在网页地图在用的 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-order 把这些顶点串起来，只扫描三角形包围盒覆盖的那一段曲线，起到了桶的作用。它没有的是凸多边形的捷径、条带，以及无分支的计数：每个三角形写三个索引，遇到第一个落在内部的点就停。

earstrip 在 GitHub 和 npm 上，附带了本文用到的多边形，以及在你自己的机器上与 earcut 对比计时的代码。