earcutより高速、3.7Mのマップポリゴンを489msで三角形分割

2026年10月、著者は地図エンジンの多角形三角形分割器「earstrip」をISCライセンスのライブラリとして公開した。ネイティブC++版はearcut.hppより14%速いとされる。

著者は、自身の地図エンジンで使う多角形三角形分割器「earstrip」をISCライセンスのライブラリとして公開した。1つのC++ヘッダーで構成され、npm向けのWebAssemblyビルドも用意されている。引数はearcutと同じである。

公開されたライブラリ

著者は2026年10月、エンジンの制約付きDelaunay三角形分割器をear clippingに置き換えた。対象はポーランドのマゾフシェ県(ワルシャワ周辺地域)のズームレベル13のオフラインマップで、3,740,425ポリゴンを含む。従来のDelaunay三角形分割器は、M4 Proの1コアで全ポリゴンの処理に2.93秒を要していた。

earstripは、Delaunay三角形分割器の置き換えと、その後の段階的な改良によって構成されている。著者は、ear clipperを一度に一つずつ手法を加えて作り直し、各段階をマゾフシェ県のポリゴンで計測した。

三角形分割器の置き換え

マゾフシェ県のデータの内訳は以下のとおりである。

• 頂点が4つ以下のポリゴンは1.8 million件あり、Delaunayでは419msを要していた。
• 穴を持つポリゴンは11,345件である。
• 単純なear clipperは1,119msで処理でき、Delaunayより2.6倍速かった。
• 257頂点以上の最大ポリゴン1,123件は、クリップに199ms、Delaunayでは90msを要した。
• 76件のポリゴンはDelaunayにフォールバックする。

穴が128以上のポリゴンはエンジンがDelaunayに送る仕様で、マゾフシェ県のデータでは2件が該当する。凹みを除去するテストでは合計処理時間が237ms減少した。三角形ストリップを書き出すことで、インデックス数は64.5 millionから35.8 millionに減った。

マゾフシェ県の地図を新たにビルドした際は、GEOSのスナップ丸めにより273件のポリゴンが修復された。これにより、すべてのポリゴンをear clippingで切り出せるようになった。ワルシャワのSrodmiescieの街区例では、331ポリゴン(5,151頂点)が4,514個の三角形に分割された。

Gary Meistersは1975年に、3頂点より多い単純多角形には互いに重ならない耳が少なくとも2つあることを証明している。earstripはこの原理に基づくear clippingを採用している。

性能と検証結果

• ネイティブC++では、earstripはearcut.hppより14%速い。
• ブラウザでは、earstripはearcut.jsの1.4〜2.1倍の速さである。
• 世界地図タイル56,472ポリゴンでは、earstripが459ms、earcut.hppが2,892msを要した。
• 11,675個の穴を持つ世界地図の1ポリゴンは、ear clippingで606ms、Delaunayで17msかかった。
• WebAssemblyにコンパイルすると、V8ではearstripが23%、earcut.hppが67%性能を失う。

ズームレベル13と9の計4.4 million件のポリゴンについて、すべてのWebAssemblyビルドはネイティブ版と完全に同一の三角形を出力した。

この記事は元記事の事実のみに基づいて自動生成されました。

出典

• 媒体名: globus.software(David Eberly's write-up of ear clipping の報道による)
• 原題: Faster than earcut: triangulating 3.7M map polygons in 489 ms
• URL: https://globus.software/blog/2026/10/16/cutting-map-polygons/