我们以ISC许可证发布了earstrip，这是我们地图引擎中的多边形三角剖分器，作为一个小型开源库，使用的许可证与earcut相同。它由一个C++头文件和一个发布在npm上的WebAssembly版本组成，接受与earcut相同的参数。在C++中，它比earcut.hpp快14%，在浏览器中，它的速度是earcut.js的1.4至2.1倍。
GPU只能填充三角形，而地图主要由多边形组成：建筑物、公园、停车场以及有轨电车轨道之间的草地条带。在填充任何多边形之前，必须先将其轮廓切割成三角形。我们的马佐夫斯基省（华沙周边地区）离线地图在缩放级别13下有3,740,425个多边形。在M4 Pro的单个核心上，我们引擎中的约束Delaunay三角剖分器处理它们全部耗时2.93秒。
今年10月，我们用耳切法替换了它。Delaunay三角剖分可以避免细长三角形，对插值和模拟很有用，但平面填充并不需要这种质量，而且大部分工作都耗费在简单形状上。马佐夫斯基的多边形中近一半，即180万个，顶点数为四个或更少，但Delaunay代码仍花费419毫秒从头构建它们的三角剖分。耳切法每次移除一个角，而每个顶点数超过三个的简单多边形至少有两个互不重叠的耳，因此总有另一个可切割的地方。
为了记录这项工作，我们逐个提交地重建了耳切器，并在相同的370万个多边形上对每个步骤计时。最终版本在489毫秒内处理完整数据集，这也是标题中的数字。
来源: Hacker News · 由HeadlinesBriefing整理摘要