GLOBUS 把内部三角化器开源这件事,大部分讨论停在「又有一个更快的 earcut 出现」这个层面。但公告里有个细节被略过了:许可证是 ISC,跟 earcut 一模一样;接口参数也跟 earcut 保持一致。这当然不是巧合。一个商用地图引擎把自己的内部算法拿出来开源,本来可以是任何许可证、任何接口设计,它偏偏选了「跟 earcut 完全一致」——这是在明说一件事:我不是来另立门派的,我是来替换现有标准的。
真正让我停下来的是公告里正确性那一节的一个数字。在耳切无法精确处理的退化多边形上,earcut 生成的三角形跟 even-odd 填充平均有 31% 的像素不一致;earstrip 的对应比例是 0.15%。31% 对 0.15%。这不是速度差距,是正确性差距。earcut 在这些数据上不止是慢,是错。而它被当作标准用了十年,没人拿它跟实际填充结果做过像素级对比。这笔账,比所有性能数字都更有意思。
为什么一个被用了十年的三角化库,会在真实地图数据上出错?答案不在算法,在数据。地图坐标是要圆整到瓦片网格的,圆整之后顶点会合并,合并之后产生零面积角、重复边、以及各种退化结构。公告里有一个例子:华沙 Śródmieście 一个车站轮廓,154 个顶点,在 18 厘米网格下(14 位)有 31 个顶点跟邻点合并;在 13 位下合并 68 个顶点,产生 84 个三角形;在 11 位下耳切干脆找不到耳;到了 10 位又突然能切了。顶点合并之后,多边形的几何结构本身在变,不是简单的「精度损失」,是「结构退化」——而耳切这个算法对结构退化天生脆弱,因为它的核心操作是「找到一个耳,切掉,再找下一个」。一旦没有耳了呢?算法卡死。
earcut 不是没意识到这个问题。它内部也利用「只有凹点能阻挡耳」这个性质,但把检查放在包围盒和三角形测试之后,而且对每个顶点执行。它的优化是通用的,针对的是「大多数多边形」的分布。问题在于,地图引擎面对的不是「大多数多边形」,是「全部多边形」——包括那些被坐标圆整折磨过的退化结构。GLOBUS 自己在地图引擎里踩过这个坑,所以他们做了七层逐级优化,从 1.12 秒一路压到 489 毫秒。这七层优化的每一层,拆开看都不算什么惊天发明:只检测凹点、凸多边形跳过耳测试、输出三角带、按包围盒长边分桶、无分支计数、只对标记凹点做精确测试。这些优化单独拎出来,有些看起来甚至很寒酸——凸多边形跳过耳测试那一项,报告自己只带来了约 2 毫秒改进。一个人如果只看这个数字,会觉得这是在浪费时间。但你把它放到整体优化的链条里看,它移除了 2,810 万次耳测试里的 440 万次,后面的分桶优化之所以能产生更大效果,是因为它站在了「凸多边形已经快速通过」这个前提上。这种优化不是天才一拍脑袋想出来的,是不断测量、不断调整、每压一步都对着真实数据分布比对出来的苦活。我上一次看到这么细致的优化过程,还是在数据库查询引擎的论文里。
这段算得有点碎,但账不细算不清。结论放在这里:earstrip 的性能优势,来源不是算法创新,是数据分布判断。它知道自己在处理什么——地图瓦片数据,绝大多数多边形顶点数不超过 4 个(马佐夫舍数据里约一半),真正的大多边形屈指可数。所以它的优化路径是「让简单形状以最快速度通过,把复杂计算留给少数大洞、大环」。翻译成工程术语就是「为真实分布设计的分支预测」。earcut 不是不会这个,是它要兼顾的场景太宽。一个「通用」的库和一个「为地图数据调优」的库,在退化数据上的差距就是这么拉开的。31% 的像素不一致,不是 earcut 写错了什么,是它从来没被要求在这些数据上保证正确。
GLOBUS 没有把耳切当成万能药,这是整个项目最诚实、也最容易被忽略的部分。耳切算法在「孔洞很多」的多边形上会退化,因为桥接孔洞需要扫描边界,孔越多成本越高。世界地图瓦片里有一个含 11,675 个孔的多边形,耳切耗时 606 毫秒,Delaunay 只要 17 毫秒。面对这种数据,再快的耳切也白搭。所以 earstrip 内置了回退:当耳切耗尽、三角形面积覆盖错误、或者环数超过 128 时,直接改走约束 Delaunay。在马佐夫舍 374 万个多边形里,76 个走了 Delaunay 回退。这不是「我们全面碾压」式的开源宣称,这是「该快的时候快,该稳的时候稳」的工程分层。我读到这里的时候,对「14% 的性能提升」这个宣传数字反而没太大感觉了——真正有价值的是它背后的判断逻辑:用什么算法,由数据的真实结构决定,不由宣传口径决定。这条通则,比一个具体库的 benchmark 更能迁移。
把格局摆开。这件事里有四方。第一方是 GLOBUS,它开源的是自己地图引擎里用了多年的内部工具,付出的代价是「独门算法不再独门」,换回来的是行业标准制定权——如果 earstrip 被广泛采用,以后每个用 earstrip 的团队,实际上都在依赖 GLOBUS 曾经踩过的坑和做过的优化,这是一种很便宜的信任建立。第二方是 earcut 及其生态,ISC 许可证和接口一致性意味着替换成本几乎为零,唯一能留住用户的,是那些「只用 earcut 标准接口、从没出过问题」的普通场景;在退化数据和极端孔洞场景,earcut 正在被公开地、有数据地挑战。第三方是下游的地图库、GIS 工具、WebGL 渲染引擎,它们是这轮开源的纯受益方——免费拿性能和正确性,不用动一行接口代码。第四方是那些「觉得 earcut 不够好、正在自己改或者自己搞一套」的团队,他们被绕开了;之前自研的动机是「现有库在退化数据上不对、在极端数据上太慢」,现在这个动机的根基被动摇了。
我的判断摆在这儿:earstrip 的核心价值不是「快 14%」,是它把「地图三角化必须处理退化数据」这个被 earcut 生态长期回避的问题摆到了台面上,并且给出了一个可替代的实现。它开源策略的实质是用 earcut 的生态位做分发,用正确性做差异化——ISC 和接口一致是「降低你的替换成本」,31% 对 0.15% 是「给你一个换的理由」。这两步凑在一起,套进去的是 earcut 过去十年没被追问的那部分用户,就是那些真的在渲染地图瓦片、真的需要 every-polygon 正确性的人。性能只是果,不是因。
这个判断可能会错。证伪条件很具体:如果 earcut 在下一个版本中修复了退化数据上的正确性问题,并且给出同样可验证的像素级对比结果,那么 earstrip 的核心竞争力就只剩性能,而性能优势在非地图场景(比如通用 CAD 数据、随机测试集)上会大幅缩水——公告自己也报告说,在原生 C++ 下 earstrip 只比 earcut.hpp 快 14%,远没有浏览器端 1.4 至 2.1 倍那么明显。什么时候 earcut 把正确性这个窟窿补上,我这套「这是一次标准替换、不是一个新轮子」的判断就失效。到那天我会改口。但在 earcut 公开给出退化数据的正确性承诺之前,我坚持这个判断:这是冲着替换来的,不是冲着「me too」来的。
