earcut超えの高速三角分割ライブラリ公開
原題: Faster than earcut: triangulating 3.7M map polygons in 489 ms
なぜ重要か
地図・GIS・ゲームエンジン分野でポリゴン三角分割は基盤処理であり、性能改善はリアルタイム描画の大規模化に直結する。
Globus Softwareは2026年10月16日、地図エンジン向けポリゴン三角分割ライブラリ「earstrip」をISCライセンスでオープンソース公開した。C++実装でearcut.hppより14%高速、ブラウザ上のWebAssembly版ではearcut.jsの1.4〜2.1倍の速度を達成。370万ポリゴンをM4 Proの1コアで489ミリ秒で処理できる。
地図レンダリングエンジンを開発するGlobus SoftwareのCEO、Evgen Bodunov氏が、同社エンジンの三角分割処理をライブラリ「earstrip」として切り出し公開した。実装は単一のC++ヘッダファイルで、npm上にWebAssembly版も用意されている。APIはearcut.jsと同一の引数を取るため、既存プロジェクトへの移行コストは低い。
GPUはポリゴンを直接描画できず、三角形のみを扱う。地図データには建物・公園・駐車場などポリゴンが大量に含まれるため、高速な三角分割は描画パフォーマンスに直結する。同社のオフラインマップ（マゾフシェ県域、ズームレベル13）には3,740,425個のポリゴンが含まれ、従来の制約付きDelaunay三角分割では同じM4 Proの1コアで2.93秒を要していた。
Bodunov氏はこれを「耳切り法（ear clipping）」に置き換えることで489ミリ秒まで短縮した。ポリゴンの角（耳）を1つずつ切り取って三角形を生成するアルゴリズムで、実装をアイデアごとにコミットを分けて段階的に最適化し、各ステップを同一の370万ポリゴンで計測した。
Delaunay法の課題として、全体の約半数にあたる180万ポリゴンが頂点数4以下（三角形か凸四角形）であるにもかかわらず、個別にフル三角分割を構築するため419ミリ秒を消費していた点が挙げられた。GPU描画においてDelaunay法が提供する「最大最小角」の保証は不要で、針のように細い三角形でも凸型の太い三角形と同様に正確に描画される。
earstripはブラウザ環境での実測でearcut.jsを1.4〜2.1倍上回り、C++環境ではearcut.hppを14%上回る。ライセンスはearcut.jsと同じISCを採用している。