出来事の日付：2026年10月22日。
地図ソフトウェアを開発するGlobusが、ポリゴンを三角形に分割するライブラリearstripを公開した。従来の同社の手法や広く使われているearcutの実装よりも少ない処理負荷で、地図の形状データをグラフィックスプロセッサ向けに準備することを目指している。プロジェクトは、単一のC++ヘッダーとnpm上のWebAssemblyパッケージとして、制約の少ないISCライセンスで提供されている。
ポリゴンの三角形分割は、デジタル地図の描画で通常は目に見えないものの、欠かせない工程だ。建物や公園など、内部を塗りつぶす図形のデータは通常、ポリゴンの輪郭として渡される一方、グラフィックスプロセッサは三角形を描画する。地図を描く前に、レンダラーは穴のある図形も含め、それぞれの輪郭を同じ面積を覆う三角形の集合に分割しなければならない。
Globusは、ポーランドのマゾフシェ県のオフライン地図に含まれる3,740,425個のポリゴンで、新しい実装を試した。同社によると、earstripはApple M4 Proの1コアでこの処理を489ミリ秒で完了した。公開された比較では、C++実装はearcut.hppより14%高速で、ブラウザー版はearcut.jsの1.4〜2.1倍の速度で動作した。これらの数値は、開発元が選んだデータセットとハードウェアで実施したベンチマークであり、独立した第三者によるプラットフォーム横断の評価ではない。
開発は、アルゴリズムで何を優先するかを見直すことから始まった。Globusは従来、形の整った三角形を優先する制約付きドロネー三角形分割を使っており、同じデータセットの処理に2.93秒かかっていた。この性質は、シミュレーションや形状内で値を補間する場合には重要になり得るが、平面の地図を塗りつぶす用途では利点がほとんどない。テスト用ポリゴンのほぼ半数は頂点が4個以下で、多くの単純な図形にとって、より複雑な処理は割高になっていた。
Earstripは代わりに耳切り法を採用する。この手法では、三角形の内部にほかの関連する境界点を含まない凸の角を繰り返し見つけ、その三角形を切り離し、ポリゴン全体を分割するまで処理を続ける。実装は穴にも対応している。安全な橋渡しとなる線で穴と外周を結び、切り取り処理でたどれる境界へと形状を変換する。
開発元が最初に完成させた耳切り法の実装では、データセットの処理に1.12秒かかった。その後の変更は、切り取る耳の候補を検査するコストに重点を置いた。特に、数は比較的少なくても多数の頂点を繰り返し走査するため処理が重くなる、大きなポリゴンを対象にした。最終的なベンチマーク結果は、教科書的な手法を単純に実装したものではなく、こうした最適化の積み重ねを反映している。
Earstripはearcutと同じ引数を受け付けるため、そのインターフェースをすでに使っているチームは試しやすい可能性がある。今回の公開は、ドロネー品質の三角形を作ることよりも処理量が重要な場合に、地図エンジンの開発者へ新たな選択肢を提供する。ただし、実際の利点はデータの形状、実行環境、プロセッサ、組み込みのコストによって変わる。本番用レンダラーを切り替える前に、利用者自身の処理負荷で比較測定する必要がある。
