earcutを超えた：370万の地図ポリゴンを489ミリ秒で三角形分割
Faster than earcut: triangulating 3.7M map polygons in 489 ms
地図エンジンのポリゴン三角形分割器をISCライセンスの小さなライブラリearstripとして公開。C++ではearcut.hppより14%速く、ブラウザではearcut.jsの1.4〜2.1倍。ワルシャワ周辺の370万ポリゴンをDelaunayの2.93秒から489ミリ秒まで短縮した過程を、耳クリッピングの最適化を一歩ずつ積み上げて解説する。
ほぼ半数のマゾフシェのポリゴン、180万個は頂点が4つ以下だ。三角形は一切切る必要がなく、凸四角形は2つの三角形になるだけなのに、Delaunayのコードはそれらに419ミリ秒を費やし、毎回ゼロから三角形分割を構築している。
HNでの議論
35- morishuz
すごい。パフォーマンスの改善は印象的ですね！
私はDelaunay32の作者です。ポリゴンと穴をサポートする制約付きドロネー三角形分割器です。分割統治法を使っていて、逐次挿入ではないので、ここでのドロネーベースラインとどう比較されるか興味があります。
https://github.com/morishuz/delaunay32
まだあなたのコーパスでベンチマークを取っていませんし、現在のポリゴンAPIは穴が接触しない単純なリングを要求します。データセットを公開してくれてありがとう、テストと比較に役立ちそうです！
- amelius
三角形分割器の母と言うべきものを挙げておくべきでしょう：
- mistercow
長い間、なぜイヤクリッピング＋最適化が三角形分割でSeidelの台形法のようなものに勝ってきたのか不思議に思っていました。Seidel法はO(n log* n)の時間計算量で、穴も自然に扱えます。big-Oがすべてではないことは分かっていますが、これは本質的に線形対二次であり、時間が経つにつれてより複雑なポリゴンを三角形分割することに関心が高まっているように思えます。
それは単に三角形の品質の問題なのでしょうか？Seidel法は扱いにくいスリバーを多く生み出すのでしょうか？
- mourner
やあEvgen、Earcutの作者です — 記事と本当にクールなライブラリをありがとう！EarcutのJS版に借用できるトリックがないか見てみる必要がありますね。 :)
一つ注意すべきは、バンドルサイズが爆発しないように、ライブラリを小さく保つために潜在的な最適化のいくつかを意図的に却下しなければならなかったことです — ほとんどの実用的なアプリケーション（例えばMapbox GL JS）ではすでに十分速いです（そして4.1k min/gz）。EarstripのWASMビルドがどれくらいの大きさか興味があります。
C++側では、Mapboxは現在ハイブリッドアプローチを使っていて、小さなポリゴンはearcut.hppで処理し、大きく複雑なポリゴンは単調分解に基づく別のアルゴリズムに切り替えます。アルゴリズムの複雑さの定数は高いものの、入力サイズに対してはるかにスケールするからです。
- stymaar
結果には非常に長くて非常に薄い三角形がたくさん含まれているのが分かります。それらは一般にGPUラスタライザにとって最悪のケースではないでしょうか？