我们已经将我们的地图引擎的多边形三角剖分器作为一个小型库 earstrip 发布，采用 ISC 许可证，与 earcut 相同。它是一个 C++ 头文件，以及一个在 npm 上构建的 WebAssembly 版本，接受与 earcut 相同的参数。在 C++ 中，它比 earcut.hpp 快 14%，在浏览器中比 earcut.js 快 1.4 到 2.1 倍，且比较在文章末尾。本文讲述我们是如何做到的。一个 GPU 只填充三角形而别无其他。而地图则主要是多边形：建筑物、公园、停车场、两条电车轨道之间的草带。以下是我们渲染器从地图文件读取的华沙市中心的一些街区的样子：在任何填充之前，每个轮廓必须被切割成。将鼠标悬停在多边形上或轻触它，可以查看它变成什么。这些街区包含 331 个多边形，具有 5,151 个顶点，并且它们变成了 4,514 个三角形。我们位于华沙周边的马祖维亚省的离线地图的第 13 个缩放级别有 3,740,425 个多边形。在一颗 M4 Pro 核心上，我们引擎中的约束 Delaunay 三角剖分器需要 2.93 秒来切割它们所有。这个十月，我用耳切替换了它。为了撰写本文，我一次一个想法重建耳切，每个想法一个提交，并在这 370 万个多边形上记录每个提交的时间，因此下面的每个部分都以一个数字结束。Delaunay 一组点的三角剖分是 Delaunay，当且仅当没有点位于任何三角形的三个顶点通过的圆内。共享一条边的两个三角形就足以看出规则的工作原理。拖动点 D：45°ABCD 最小角度 45°；如果是 BD 则为 37°。当 D 保持在贯穿 A、B 和 C 的虚线圆之外时，共享边是 AC，边缘翻转为 BD；然后它又翻转回来。每次翻转都是一次局部修复，而没有边想要翻转的三角剖分就是 Delaunay。在所有三角化相同点的方法中，它拥有最大的最小角度。橙色弧标记两三角形的最小角度，图下的线显示另一条对角线可能得到的结果：无论你把 D 放在哪里，圆规则选出的边都会获胜。“约束”意味着多边形自身的边必须保持为三角剖分的边，即使圆规则会将它们翻转。我们的三角剖分器一次插入一个顶点。对于每个新点，它在到目前为止构建的三角形中行走，直到找到所落入的三角形，分割它，并围绕新点翻转边缘，直到圆规则再次成立。它还强制多边形的边缘，并在最后仅保留位于多边形内部且位于其孔之外的三角形。良好形状的三角形在你在其上进行插值或运行模拟时尤为重要。平面填充对此无关紧要：GPU 以同样正确的方式填充细如针的三角形和胖三角形。而大部分工作是在基本上不需要任何切割的多边形上进行的。近一半的马祖维亚多边形，180 万个，具有四个或更少的顶点。一个三角形不需要任何切割，而一个凸四边形是两个三角形，但 Delaunay 代码在它们上花费了 419 毫秒，从头构建每个三角剖分。耳 多边形的一个耳是你可以用一刀切掉的一个角。取三个连续的顶点 a、b 和 c。如果在 b 的角是凸的，并且多边形的其他部分没有进入三角形 abc，那么该三角形就是一个耳。将其切掉，剩下的就是一个少一个顶点的多边形。1975 年，加里·迈斯特斯证明了每个简单多边形如果有三个以上的顶点，便至少有两个不重叠的耳。因此，总是还有另一只耳可以切，而一个具有 n 个顶点的多边形可以分解成 n - 2 个三角形。以下是上述街区中的一栋建筑。移动滑块可以一次切掉它的耳，或者：0 / 25 绿色三角形是下一个要去的耳。算法需要一个测试，“这个角是耳吗？”最简单的版本检查这个角，然后检查边界的每个其他顶点。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