比 earcut 更快:489 毫秒完成 370 万地图多边形三角化
Delaunay
如果任意三角形的三个顶点所构成圆的内部不包含其他点,则一组点的三角化即为 Delaunay 三角化。观察两个共享一条边的三角形,即可理解该规则。拖动点 D 查看效果:
只要 D 点位于经过 A、B、C 三点的虚线圆外,公共边就是 AC。将 D 推入圆内,边便翻转为 BD;拉回圆外,又翻回 AC。每次翻转都是一种局部修复,当没有边想要再翻转时,该三角剖分即为 Delaunay 剖分。在所有对同组点进行的三角剖分方式中,Delaunay 剖分的最小角最大。图中橙色弧线标记了两个三角形中较小的那个角,图下方的折线展示了对角线 BD 的效果:无论 D 放在哪里,圆判定规则选出的边总是更优。
“带约束”是指多边形自身的边在三角剖分中必须保留,即便圆判定规则倾向于翻转它们。我们的三角剖分器逐个插入顶点。每插入一个新点,它都会遍历已构建的三角形,找到新点落入的那一个,将其分割,并围绕新点翻转边,直到圆判定规则再次成立。算法还强制保留多边形的边,最终仅保留位于多边形内部(且在其孔洞外部)的三角形。
三角形形状良好在进行插值或模拟运算时至关重要,但平面填充并不挑形状:GPU 填充细如针尖的三角形与肥厚三角形一样准确。大部分计算工作量其实集中在那些几乎无需剖分的多边形上。马佐夫省 180 万个多边形中,近半数顶点数不超过 4 个。三角形根本无需切割,凸四边形也不过是剖分成两个三角形,但 Delaunay 代码却花了 419 ms,从零开始构建每个剖分。
耳朵算法
多边形的“耳朵”是指可用一刀直线切掉的一个角。取连续三个顶点 a、b、c,若 b 处的角为凸角,且多边形其余部分不伸入三角形 abc,该三角形即为一耳。切掉它,剩余部分便是一个顶点数少一的多边形。1975 年 Gary Meisters 证明了每个顶点数超过 3 的简单多边形至少有两朵互不重叠的耳朵。因此总存在另一朵可切的耳朵,一个含 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; // 转向错误,或没有转向
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; // 在三角形外
if (!samePos(p, a) && !samePos(p, b) &&
!samePos(p, c))
return false;
}
return true;
}
位于三角形边上的点也算在内部:如果耳朵与边界的其他部分相接触,切掉它就会得到一个自相接触的多边形。唯一的例外是恰好落在 a、b 或 c 位置上的点,这种情况出现在轮廓在单个顶点处与自身相交时——带洞的多边形里这很常见。
洞(Holes)
切耳法只能处理单个闭合边界,而马佐夫舍省有 11,345 个多边形带洞,比如庭院和森林中的空地。处理办法是把每个洞剪开,用一条"桥"把它缝到外环上——桥是从洞的某个顶点连到边界某个顶点的一条边,正反各走一遍。这样边界就先沿外侧绕行,跨过桥,反向绕洞一圈,再跨桥回来。桥的两个副本之间没有面积,所以多边形不变,但现在它只是一个环了。
桥接不能穿过任何几何体。David Eberly 关于耳切法的技术文档提供了一种巧妙的查找方法。取孔洞最右侧顶点 m,向其右侧发射一条射线。射线首先命中的边在 I 点处,该边的右端点为 P。如果没有边界顶点位于三角形 m、I、P 内部,则桥接 m–P 就是安全的。你可以拖动孔洞来查看:
位置较高时,三角形区域为空,桥接指向 P;位置较低时,凹陷尖端位于三角形内部,桥接改向凹陷尖端:在三角形内的多个凹陷中,Eberly 会选择与射线角度差最小的一个。孔洞按从右到左的顺序桥接,因此更靠左侧的孔洞可以桥接到已经并入边界的另一个孔洞。
地图数据带来了两种特殊情况。我们的坐标是瓦片网格上的整数,因此沿网格线发射的射线会经常直接穿过顶点;相交测试会跳过这类顶点,我最初版本正是错在这一点上。此外,制图员经常在某个点画一个紧贴外墙的庭院。这样的孔洞不需要桥接:两个环在共享顶点处已经相连。
朴素裁剪器(−1,812 毫秒)
完成孔洞桥接后,第一个完整版本沿边界遍历,用上述 isEar 函数测试角点,切下找到的每个耳并写入三角形的三个索引。在 Masovian 多边形上耗时 1.12 秒,比 Delaunay 快 2.6 倍。图表按多边形大小拆分每次耗时;悬停条形图的某一部分可查看数量,点击某一行可筛选:
除了最大一档,朴素耳切在所有尺寸类别上耗时都短于 Delaunay。最大的 1,123 个多边形(顶点数 257 及以上)裁剪耗时 199 毫秒,而 Delaunay 只需 90 毫秒。在那里,每次耳切测试都要遍历数百个顶点,而一个多边形又需要数百次测试,因此成本随尺寸平方增长。本文后续内容致力于降低耳切测试成本并减少其调用频率。
只测试凹陷点(−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;
}
原本 2810 万次耳部测试现在只检查 1.85 亿个点位,而非 3.53 亿个,总耗时降至 882 ms。这比预期要快,因为建筑物轮廓含有大量凹陷点。上面带拱门的建筑物在 27 个顶点中有 15 个是凹陷点。最小的多边形处理速度反而变慢,从 34 ms 增加到 54 ms:对于三角形或四边形,将角点分类为凹陷点与其他点的开销超过了节省的遍历成本。
跳过凸多边形的测试(−2 ms)
没有凹陷点的多边形是凸多边形,凸多边形的每个角都是耳部,因此可以不经任何测试直接切割。判断这一点需要谨慎处理。“每个角都向左转”是不够的:
这颗星在全部五个角上都左转,因为它绕中心转了两圈。引擎还会再加一个条件:沿凸多边形环走一圈,边在底部向右、顶部向左,x 方向应该恰好变化两次,即在最左点和最右点。五边形通过了这项检查;星形在画圈的角上变了四次方向,于是转入普通的耳朵测试。这两项计数都在标记凹陷的同一个循环里完成,几乎不增加开销。三角形和四边形则在这个循环之前就有自己的捷径。
这个捷径砍掉了 2810 万次耳朵测试中的 440 万次,但那些本来是最便宜的测试:没有凹陷的环根本不需要扫描。单靠这一点对总耗时(880 ms)影响甚微,不过四个顶点以下的多边形挽回了一部分凹陷检查的成本,从 54 ms 降到 48 ms。真正的价值在下一步:凸环可以直接变成一条 strip。
写入 strip(−118 ms)
到目前为止,每个三角形要花三个索引。GPU 还能绘制三角形 strip(triangle strip),即每新增一个索引,就与前面两个索引构成一个三角形。凸环可以通过之字形遍历变成一条 strip:
0 1 7 2 6 3 5 4 切耳算法同样能输出 strip。切掉一只耳朵会让它两个相邻的角变得更尖,因此它们是下一只耳朵的好候选;切掉其中之一只需向 strip 追加一个索引。引擎会优先尝试这两个候选,只要耳朵还在就不断在两端之间交替。代码里被切顶点的两个邻居是 a 和 b:
// 下一只耳朵在被切顶点的两端之间交替。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 毫秒,中等规模的收益最大:顶点数为 33 到 256 的多边形从 327 毫秒缩短至 216 毫秒。
仅测试标记的凹点(减少 30 毫秒)
当计数不为零时,精确循环会再次读取所有凹点,尽管第一轮已经识别出哪些点在内部。分桶版本将这一信息保留在位掩码中。对于最多 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;
// 之前的精确测试
}
读取的点数从 1.28 亿降至 1.2 亿。这是最后一步,生成的代码与已发布的 earstrip 完全一致:489 毫秒,比在同一组多边形上运行的 Delaunay 快 6.0 倍。
当不存在“耳朵”时
Meisters 定理适用于简单多边形。地图数据会舍入到瓦片网格,而舍入可能破坏简单多边形。下图展示了Warszawa Śródmieście(一个距上方街区不到一公里的火车站)在不同网格大小下舍入后的轮廓。橙色圆圈标记了与相邻顶点落在同一点的顶点:
在我们地图文件使用的每瓦片侧边 14 位精度下,网格步长为 18 厘米。即便如此,154 个顶点中仍有 31 个与相邻顶点合并,因为制图者常将点放置得仅相隔几厘米,但轮廓依然完好。在 12 位精度下,近半数顶点发生合并,但裁剪器仍能正常切割。到了 11 位精度,舍入后的轮廓自相交,导致完全无法形成“耳朵”;而在 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。在耳切法无法精确切分的 zoom 13 多边形上,earcut 的三角形与环的 even-odd 填充结果平均在 31% 的像素上存在差异,earstrip 则只有 0.15%。
In the browser
在将新 clipper 集成进应用之前,我把它和 earcut 做了对比。earcut 是 MapLibre 和 Mapbox GL 背后的耳切算法,这里用的是其 C++ 版本 earcut.hpp 3.2.4。原生环境下两者性能接近,故事本来可以到此为止。但我们的网页渲染器运行的是同一套 C++ 引擎编译成的 WebAssembly,所以我又对比了浏览器端的情况:两款 clipper 都编译成了 WebAssembly,以及耳切 3.2.4 的原始 JavaScript 版本 earcut.js——也就是当前 Web 地图正在运行的那套。为此我把 clipper 从引擎中剥离出来,做成了 earstrip。在我们所有测试集的 580 万块多边形上,它生成的三角形条带与引擎的输出完全一致;其代码仓库中包含了这些多边形以及本章节中每个数字背后的生成代码。上文图表对应的就是它的原生基准测试;下表中“原生”一行是最后一步针对 earcut.hpp 的运行结果。在所有 WebAssembly 构建中,对于第 13 级和第 9 级共 440 万块多边形,WebAssembly 版本生成的三角形与其原生版本完全相同。以下是第 13 级 374 万块多边形所用毫秒数,取 7 次运行中的最佳值,单线程,V8 跑在 Node 中、JavaScriptCore 跑在 Bun 中:
| earstrip | earcut | |
|---|---|---|
| Native C++ | 489 | 557 |
| WebAssembly, loop inside the module, V8 / JSC | 601 / 566 | 930 / 843 |
| WebAssembly, one call from JS per polygon, V8 / JSC | 688 / 688 | 1,007 / 950 |
| npm package, one call per polygon, V8 / JSC | 766 / 807 | 1,103 / 1,290 |
| npm package, direct calls, all polygons in one call, V8 / JSC | 635 / 619 |
原生环境下,earcut.hpp 比 earstrip 慢 14%。编译为 WebAssembly 并在 V8 中运行时,earstrip 性能下降 23%,而 earcut.hpp 下降 67%,几乎全部损耗在搜索耳朵的主循环里。问题不出在分配器上:换用 mimalloc 和 emmalloc 构建后耗时不变。我没有继续深究。在 V8 中,earcut.hpp 的 WebAssembly 版本只比纯 earcut.js 快 19%;而一旦每个多边形都通过 JavaScript 单独调用,优势缩小到仅 10%。
表格中的“包”列展示的是网页端调用方式,其中 earcut 列对应 earcut.js。用直接调用来替代 earcut 时,该调用接收 JavaScript 数字类型的坐标,并每次返回一个新的三角形索引数组:在 V8 引擎中比 earcut.js 快 1.4 倍,在 JavaScriptCore 中快 1.6 倍。与模块内部循环相比,性能损失约有一半来自坐标拷贝和将条带转换为列表,另一半则来自每次多边形都调用一次 WebAssembly。而直接调用可以跳过这些开销:多边形数据直接写入模块内存,并作为单个索引条带缓冲区返回,供 WebGL 2 或 WebGPU 使用,分别比 earcut.js 快 1.7 倍和 2.1 倍。
上述部分思路在 earcut 中也有体现。它同样利用“只有凹点才会阻挡耳朵”这一特性,但检查方式不同:earcut 对通过包围盒和三角形测试的每个顶点最后才检查凹点,而非维护一个凹点列表。当顶点数超过 80 个时,earcut 按 z 序链接它们,并只扫描该曲线中三角形包围盒所覆盖的区间,起到了类似分桶的作用。然而,earcut 缺少凸多边形的快捷路径、条带输出以及无分支计数:它每个三角形写入三个索引,并在遇到第一个内部点时停止。
earstrip 已发布在 GitHub 和 npm 上,附带本文章使用的多边形数据,以及在自己机器上将其与 earcut 进行耗时对比的代码。