比 earcut 更快：489 毫秒三角剖分 370 万多边形
Faster than earcut: triangulating 3.7M map polygons in 489 ms
我们发布了名为 earstrip 的多边形三角剖分库，在 C++ 中比 earcut 快 14%，在浏览器中快 1.4 到 2.1 倍。文章详细记录了从 Delaunay 三角剖分切换到耳切割法（ear clipping）的优化历程。通过仅检测凹点、跳过凸多边形测试、处理带孔多边形等技巧，我们将处理 370 万个地图多边形的时间从 2.93 秒压缩至 489 毫秒。GPU 只负责填充三角形，而地图数据多为多边形，高效的剖分算法是地图渲染的关键。
GPU 只填充三角形，而地图却主要是多边形：建筑物、公园、停车场，以及两条有轨电车轨道之间的那条草带。
HN 评论区
33- amelius
应该提一下所有三角剖分算法的鼻祖：
- morishuz
太棒了。性能提升看起来令人印象深刻！
我是 Delaunay32 的作者，这是一个支持多边形和孔洞的约束 Delaunay 三角剖分器。它使用的是分治法而不是增量插入法，所以我很好奇它和这里的 Delaunay 基线相比会如何。
https://github.com/morishuz/delaunay32
我还没在你的数据集上做过基准测试，而且我们当前的多边形 API 要求是互不接触的简单环和孔洞。感谢发布这些数据集，它们看起来对测试和对比很有用！
- mourner
嘿 Evgen，我是 Earcut 的作者——感谢这篇博文和这个很酷的库！我得看看有没有什么技巧可以借用到 Earcut 的 JS 版本上。:)
有一点需要说明的是，我故意拒绝了一些潜在的优化，以保持库的体积小巧，这样打包大小就不会爆炸——对于大多数实际应用（例如 Mapbox GL JS）来说，它已经够快了（且最小化/gzip 后仅 4.1k）。很好奇 Earstrip 的 WASM 构建有多大。
在 C++ 方面，Mapbox 现在采用了一种混合方案：小多边形用 earcut.hpp 处理，而大且复杂的多边形则切换到另一种基于单调分解的算法，因为虽然它的算法复杂度常数更高，但随着输入规模增大，其扩展性要好得多。
- mistercow
我长期以来一直纳闷，为什么耳切法（ear clipping）加优化在三角剖分领域胜过 Seidel 的梯形法之类的东西，后者具有 O(n log n) 的时间复杂度并且能自然地处理孔洞。我知道大 O 表示法不是万能的，但这本质上就是线性与二次方的区别，而且随着时间推移，我们似乎越来越关心对更复杂多边形的三角剖分。
这仅仅是因为三角形质量的问题吗？Seidel 的方法是否会导致太多难以处理的狭长三角形（slivers）？
- stymaar
我看到结果中包含大量非常长、非常细的三角形。这些难道不是 GPU 光栅化器的最坏情况吗？