-
@ThothChildren
- 2018.8.6
- PV 216
Fortune Algorithm
ー 概要 ー
Fortune Algorithm(フォーチューンアルゴリズム)は複数の点からボロノイ図をO(nlog(n))で生成する手法.平面走査法をベースにして特定の方向から掃くようにしてボロノイ図を作成していく.
この章を学ぶ前に必要な知識
条件
- 複数の点
効果
- ボロノイ図をO(n log(n))で生成
ポイント
- ある方向に移動しながら逐次的に調べる平面走査法ベース
- 各点と走査線(Sweap Line)の放物線を作成し、その放物線の出現と削除でボロノイ図を作成
- 放物線は走査線と点との距離が等しい点の集合である特徴を生かしている
- 新しい点を追加するのは走査線がその点を越えたとき.これをSite Eventと言う.
- 注目している点のリストを保持
- 注目している点のリストの隣接する3点と走査線が同一円上に載ったら真ん中の点を削除.これをCircle Eventと言う
- イベントは優先度付キューで管理
解 説
Fortune Algorithm(フォーチューンアルゴリズム)は複数の点からボロノイ図をO(nlog(n))で生成する手法.
平面走査法をベースにしており、特定の方向から掃く(sweap)ようにしてボロノイ図を作成していく.ボロノイ図の作成ではそのボロノイ図を構成する頂点を求めていけばよい.
以下y座標をsweapしていくことを前提で考える.
処理概要
・走査線(sweap line)を特定方向に移動させていく.
・このときに通過した点に対して走査線とその点とで放物線を作成し、他の点の放物線との交点を追う.
・保持するリストは二つ. 一つは「どの点に注目すべきか」もう一つは「どのタイミングで確認すべきか」
・「どの点に注目すべきか」は走査線に最も近いBeach Line(放物線の集まり)を点の番号で保持
・「どのタイミングで確認すべきか」はイベントが逐次追加される.y座標を優先度としてキューに入れるため、優先度キューを用いて実装する.
・イベントは二種類「Site Event(注目点追加)」「Circle Event(注目点削除)」 | Fortuneアルゴリズムについて |
 | Fortuneアルゴリズムの処理概要
優先度キューに入っているイベントを元に走査線に近いBeachLineに現れる点の番号をリストで保持.
それらの追加と削除を行いながら交点を求めていく.
(X .... Z)の形は、BeachLine上に現れる点の番号を下からソートしているもの.
(1,3,0,2)は下から1番,3番,0番,2番といった順で放物線が見れるということ. |
Fortuneアルゴリズムのアニメーション |
この章を学んで新たに学べる
Comments