社媒话题
earstrip库宣称浏览器中三角化地图多边形最快达earcut两倍多
地图引擎团队以ISC许可发布单C++头文件三角化库earstrip,并提供与earcut参数兼容的npm WebAssembly版本。基准称其C++比earcut.hpp快14%,浏览器中为earcut.js的1.4至2.1倍。
文章解释,GPU填充的基本图形是三角形,而地图由建筑、公园、停车场和绿地等大量多边形组成,因此渲染前需要把轮廓切分成三角形。作者展示华沙希鲁德梅希切区若干街区:331个多边形、5151个顶点会被切成4514个三角形。
离线地图中华沙周边马佐夫舍省第13缩放级共有3740425个多边形。在M4 Pro单核上,引擎原有约束Delaunay三角化器处理全部数据需2.93秒;今年10月作者改用耳切法,并通过逐次提交和同一批370多万个多边形计时来比较优化。
文章介绍,Delaunay三角化要求任一三角形三点外接圆内不含其他点,“约束”则意味着多边形自身边必须保留。该方法会插入顶点、分裂三角形并翻转边,最后只保留多边形内部和孔洞外部的三角形。
作者认为,平面填充并不苛求三角形形状,而大量地图多边形非常简单:近180万个多边形不超过四个顶点,旧Delaunay代码却在这些图形上花费419毫秒。耳切法利用多边形可连续剪下“耳”三角形的原理降低开销。发布的earstrip为一个C++头文件,WebAssembly版在npm上提供。