フォーチュンアルゴリズムを用いたボロノイ図の生成

ボロノイ図を生成する

• ボロノイ図とは？

  • ボロノイ図は平面を複数の領域に分割する方法で、主に手続き的な地図生成に使われる。
  • 平面上に「サイト」と呼ばれる複数の点を選び、各サイトに対応する領域は、そのサイトに最も近いすべての点を含む領域となる。
  • 各領域の境界は、2つのサイトから等距離にある点で構成される。3つのサイトから等距離にある点は「ボロノイ頂点」と呼ばれる。

• フォーチュンアルゴリズム

  • フォーチュンアルゴリズムは、平面を左から右へ「スイープ」する線を使って図を生成する方法である。
  • スイープラインがサイトに達すると、その周囲に「バブル」（放物線弧）が生成され、スイープラインが離れるほどバブルは大きくなる。
  • 2つのサイトの弧が衝突すると、その衝突点がセルの境界になる。
  • すべてのアクティブなバブルの境界は「ビーチライン」と呼ばれる。

• 用語解説

  • サイト: 2次元の点で、ボロノイ図の形状を決定する。
  • スイープライン: 領域を横切る垂直線で、イベントキュー内の各イベントを処理する。
  • ビーチライン: 複数の弧から成る線で、イベントが処理されるたびに弧が追加または削除される。
  • 交点: ビーチライン上の2つの弧が出会う点で、関連するサイトと等距離にある。
  • イベントキュー: サイトイベントと円イベントが保存される場所で、x座標の昇順に整列される。
  • サイトイベント: イベントキューにある2種類のイベントの1つで、そのサイトの座標によって定義される。
  • 円イベント: キュー内のもう1つのイベント種別で、円周上にある3つの弧によって定義される。
  • ボロノイ頂点: 3つのサイトから等距離にある点で、セルの角になる。
  • 等距離境界: 2つのサイトから等距離にある線。
  • 未完成の境界: 一方の端は固定点で、もう一方は2つの放物線の焦点の交点によって定義される線。

• 放物線の接線

  • 放物線の概念と性質は、このアルゴリズムで非常に重要である。
  • 放物線は焦点と直線（準線）によって定義される。
  • 2つのサイトの焦点を設定し、スイープラインを準線として設定すると、2つの放物線の交点を見つけることで、2つのサイトから等距離にある境界線を求められる。

• ビーチラインに戻る

  • ビーチラインは、スイープライン上のある時点におけるすべての弧の「境界」である。
  • 各弧はサイトの焦点によって表現できる。
  • ビーチラインは単純な点のシーケンスとして表現できる。

• 新しい弧はスイープラインが新しいサイトに達したときに生成される

  • ビーチラインは点のシーケンスであり、各点はサイトと弧を表す。
  • スイープラインが新しいサイトに達すると新しい弧が生成され、シーケンスに挿入される。

• 交差する境界と外接円

  • 3つのサイトが円周上にあるとき、その円の中心は3点から等距離にある。
  • 外接円の中心はボロノイ頂点となる。

• 未完成の境界

  • 未完成の境界は、一方の端が固定点で、もう一方は2つの弧の交点である。
  • 2つの未完成の境界が衝突するとボロノイ頂点が生成され、未完成の境界は半辺に変換される。

• 反時計回りの円だけが円イベントを生成する

  • 3つの弧が反時計回りに読まれる場合にのみ、円イベントが生成される。

• 要約

  • サイト集合が与えられたら、すべてのサイト点を「サイト」イベントとしてキューに入れ、x値でソートする。
  • キューが空でない間、次のイベントをキューから取り出して処理する。
  • サイトイベントの場合、新しい弧をビーチラインに追加し、未完成の境界を生成する。
  • 円イベントの場合、ボロノイ頂点を追加し、ビーチラインから弧を削除する。