「earstrip」：地図データ向け高速トライアングレーションライブラリの開発とベンチマーク

ISC ライセンスと同様のライセンスの下で公開された新ライブラリ**

earstrip

**について紹介します。単一の C++ ヘッダーファイルと、npm 経由で使用可能な WebAssembly（Wasm）ビルド版を備え、引数は既存の

earcut

と共通しています。

パフォーマンス概要

earstrip

は既存の実装と比較して以下のように高速化されています。

• C++ 環境

  • earcut.hpp

    に比べて約 14% 高速化
• ブラウザ環境（WebAssembly）

  • earcut.js

    の JavaScript 版に比べて、1.4 倍〜2.1 倍の高速化を実現

本記事では、なぜそのような性能が出せるのかという開発経緯と改善プロセスを解説します。

---

なぜトライアングレーションが必要なのか？

GPU は三角形のみを充填する機能しか持ちませんが、地図データ（建物、公園、道路など）は主に多角形で構成されています。したがって、レンダリング前にすべての多角形の輪郭を切断し、三角形に変換する必要があります。

• テスト対象: ワルシャワの Śródmieście 地区にあるブロック群
  • 合計：331 つの多角形（5,151 の頂点）
  • 変換後：4,514 個の三角形に分割
• 大規模テスト: ポーランド、マゾフシェ県のオフライン地図（ズームレベル 13）
  • 合計：3,740,425 個の多角形

当社エンジン（M4 Pro チップ搭載）の初期実装である「制約付きデラネー分割法」では、この大規模テストを処理するのに 2.93 秒かかりました。今年 10 月にはこれを「耳切り算法（Ear Clipping）」に置き換え、開発を進めることにしました。

以下は、同じ 370 万の多角形セット上で各改善案を計測した結果です（時間は各セクション末尾に記載）。

---

アルゴリズムの背景：デラネー分割法 vs. 耳切り算法

デラネー分割法 (Delaunay Triangulation)

点集合から三角形を作る際、「円則」を満たす方法です。任意の三角形の外接円の内部に他の頂点が存在しない状態を指します。

• 特徴: 最小角が最大になるように辺を配置する（形状が整った）。
• 欠点: 計算コストが高い。特に「凸四角形」であってもゼロから構築するため、マゾフシェ県の約半数である180 万の多角形で合計 419 ミリ秒という過大な時間を要します。

耳切り算法 (Ear Clipping)

多角形の「耳（Ears）」と呼ばれる部分を順次切り離して三角形化する方法です。

• 原理: 連続する 3 つの頂点 $a, b, c$ で構成される三角形が「耳」であれば切り落とせる。内部に他の部分が入らない凸角のみが対象。
• 理論: ゲイリー・マイスターズ（Gary Meisters）により、単純多角形には常に耳が存在することが証明されているため、$n-2$ 回の操作で分解可能です。

---

実装の課題と改善ステップ

1. 孔（Holes）への対応

耳切り算法は単一の閉じた境界線（リング）だけで動作しますが、地図には中庭や森の穴（孔）が含まれます。これを処理するには、各穴を外部の輪郭と橋（Bridge）で繋ぎ合わせる必要があります。

• ブリッジ生成: 凹みの先端から外部へ向かう安全な線を引く。
  • デヴィッド・エーバーリーの手法を採用：穴の右端から伸ばした線が最初に交わる点を接続する。
• 地図データ特有のケース:
  • タイルグリッド上の整数座標のため、グリッド線に沿った線分の交差処理が必要。
  • 一点で描画された中庭は共有頂点で接続され、橋は不要。

2. シンプルな耳切り器の実装（−1,812 ms）

孔を橋で繋いだ上で動作する最初の完成版。境界全体を行き来して凸角を検査し、耳があれば切り落とす。

メソッド	時間
デラネー分割法	2,931 ms
単純な耳切り	1,119 ms (改善約 62%)

• 課題: 最大の多角形（257 個以上の頂点を持つ 1,123 個）では、耳検査に数百の頂点を巡回し、コストが $N^2$ に比例して増加。
  • 単純な耳切り：199 ms
  • デラネー分割法：90 ms (最大サイズでは耳切りの方が遅い)

3. 凹みのみを対象としたテスト（−237 ms）

「凸角が耳でなくなる」のは、その三角形の内部に他の頂点がある場合です。これは必ず**凹み（Reflux Vertex）**と呼ばれる反射頂点を持つことを意味します。したがって、凸角すべてをチェックする代わりに、リスト内の「凹み」だけをチェックすれば十分になります。

• 最適化効果: 参照される点が 3.53 億から 1.85 億へ削減。
• 注意点: 小さな多角形（三角形や四角形）では、凹みをソートするコストが上回ってしまい、わずかに遅くなることがある。

4. 凸多角形でのテスト跳躍（−2 ms）

凹みを持たない多角形は「凸多角形」であり、すべての角が耳となります。これをチェックするには「すべての角が左へ曲がる」という条件だけでなく、X 方向の変化回数（左端と右端の通過）を監視するロジックを追加しています。

• 効果: 2,810 万回の耳テストのうち 440 万回を検出可能。
• 結果: 独立しては影響が少ないが、合計時間は微少改善。小さな多角形が 54ms から 48ms に改善。

5. ストリップの記述（−118 ms）

GPU は個別の三角形ではなく、「三角形ストリップ」でも描画可能です。新しいインデックスはそれ以前の 2 つと組み合わさって三角形を形成します。

• 手法: 凸輪であればジグザグで横断し、1 つのストリップを作成可能。
  • 例：

    01234567

    →

    0-1-7, 0-7-2, ...

• コードロジック: 耳を切ると隣接角が鋭くなり、次の耳候補になるため、ストリップを交互に拡張していく。

メモリ使用	単一三角形	ストリップ形式
インデックス数	6,450 万	3,580 万 (約半減)

• 効果: テスト回数自体は増える（ストリップ破断時の再試行）が、総時間は減少。最大多角形が 146ms から 103ms に改善。

6. 凹みをバケットにソート（−65 ms）

数千の頂点を持つ巨大な多角形では、耳テストですべての凹みを参照するのは非効率です。境界長方向に沿って約 2 つごとに「バケット」と呼ばれる区画に分け、三角形が覆うバケットのみを検査します。

• 効果: スキャンされた点が 1.81 億から 1.01 億へ減少。
  • 巨大多角形（257 頂点以上）で顕著な改善（103ms → 57ms）。

7. ブランチなしでのカウント（−178 ms）

凹みテストのループは、三角形内の最初の凹みを見つけると終了します。多くの場合そのような凹みがないため、無駄な分岐判断が CPU に負荷を与えます。

• 手法: まず分岐なしで「三角形内にある凹みの数」をカウントするパスを実行。
  • 式：$side \ge 0$ の最小値をチェック（3 つの決定式）。
  • カウントがゼロであれば即座に「耳」と判定。

8. マーク付き凹みのみを検証（−30 ms）

カウントがゼロでない場合のみ、正確なループで再度参照します。バケット版では、情報をビットマスク（1 ビット per 点）として保持し、初期パスでヒット数を数えるのではなくビットをセットしておきます。

• 効果: 参照される点が 1.28 億から 1.20 億へ削減。
• 最終結果:

  earstrip

  （公開コード）。同じ多角形セット上で、デラネー法よりも約 6.0 倍高速化を実現しました。

---

限界とフォールバック処理

耳がない場合の扱い

マイスターズの定理は「単純多角形」に対して成り立ちますが、地図データはタイルグリッドに丸められるため、単純性を失うことがあります。

• 事例: ワルシャワ・Śródmieście 駅の付近
  • グリッドステップが大きすぎると、隣接点が同一座標となり、輪郭が自身と接触。耳自体が存在しなくなる。
• フォールバック戦略:
  1. 面積のない角（重複点）を除外して再試行。
  2. それでも失敗すればデラネー分割法に切り替える。
• 現状: マゾフシェのデータでは、273 の多角形が修復され、ファイル内の全多角形は耳切り可能になりました。

孔（Holes）が多い場合

数千の穴を持つ多角形に対して、橋を見つけるために境界全体をスキャンするのはコストがかかります。

• 比較:
  • 11,675 の穴を持つ多角形：
    • 耳切りアルゴリズム：606 ms
    • デラネー分割法：17 ms
• 方針: 現在、穴が 128 つ以上の多角形は全てデラネーに送られています。

  • earstrip

    は内部にこのフォールバックも保持しており、条件次第で自動的に切り替わります。

精度比較（世界地図タイル）

56,472 の多角形（最大穴数 11,675）を用いたベンチマーク結果：

項目	earstrip (C++/Wasm)	earcut.hpp	差異
処理時間	459 ms	2,892 ms	earstrip は約 6.3 倍速い
リング充填精度	0.15%	31% (誤差あり)	earcut はリングの偶数/奇数充填で平均 31% のピクセル不一致を発生。earstrip はほぼ正確。

---

ブラウザ環境での比較（WebAssembly vs. JavaScript）

MapLibre や Mapbox GL など、既存の耳切りアルゴリズムである

earcut

との比較を行いました。

ベンチマーク結果（ズームレベル 13 の 374 万多角形に要する時間）

バージョン	ネイティブ C++	WebAssembly (V8/JSC)	npm パッケージ (JS 呼び出し)
earstrip	489 / 557 ms	601 / 566 ms	688 / 688 ms
earcut	(参照なし)	930 / 843 ms	1,103 / 1,290 ms

(注：ネーティブ環境では earstrip は約 14% 高速。Wasm で V8 を使う場合、earstrip は 23% 低下だが earcut.hpp は 67% の低下)

ブラウザ版の性能向上ポイント

1. 直接呼び出し: npm パッケージ（ポリゴンごとの呼び出し）を回避し、座標配列を一度に渡すことで WebAssembly メモリへのコピーコストを削減。
   • 結果: JavaScript の

     earcut.js

     より1.7 倍〜2.1 倍高速化。
2. 最適化されたループ構造: Wasm 版 earcut.hpp ではメインループの大部分で性能低下が見られたが、earstrip はアロケーターの問題ではなくロジック効率による改善。

まとめ

earstrip

は C++ 環境でもブラウザ（WebAssembly）環境でも、既存の

earcut

を大幅に凌駕する性能を発揮しています。特に大規模な地図データや複雑な輪郭を持つポリゴンを扱う場合に有効です。

• 利用方法: GitHub と npm で入手可能。
• 測定コード: 本記事で使用した多角形セットと計測コードは公開済みです。