2次元離散ボロノイ図

Imple
  • 画素の集合などを扱う場合，離散として扱える(簡単)
  • 離散点なので，各画素毎に一番近い母点に属するように全探索すればボロノイ図が得られる
  • 下のflashは，母点を10点分クリックした後，ボロノイ図を表示する

ボロノイ領域分割 - wonderfl build flash online

  • 母点数に依存しない(画像サイズに依存する？)場合の方法もある(たぶん，波面法の一つ)
  • 下のflashは，母点900点をランダムにおいてその母点から領域円を拡げることでボロノイ図を作成する

ボロノイ領域分割2 - wonderfl build flash online

  • さらに，そのエッジをとることで，ボロノイ辺が作成できるはず

ボロノイ領域分割3 - wonderfl build flash online

  • ドロネー三角形分割は双対グラフなので，上記のボロノイ図により隣接する領域を辺でつなぐことで生成できる
  • 下の図は，母点10000点でドロネー三角形分割をしたもの