- @ThothChildren
- 2018.8.6
- PV 188
ボロノイ図とは
ー 概要 ー
ボロノイ図はある平面に複数の点がばら撒かれているときにそれらの点のどこに最も近いかで領域を分割している図形.
この章を学ぶ前に必要な知識
条件
- 複数の点.何次元でも構わない.
効果
- 各点のどれに近い領域かで分割できる
ポイント
- 点のことをサイトと呼ぶ
- ボロノイ図の頂点数は高々2n-5
- ボロノイ図の辺数は高々3n-6
- ボロノイ図辺は隣接点同士の二等分線
解 説
ボロノイ図はある平面に複数の点(サイトと呼ぶ.)がばら撒かれているときにそれらの点のどこに最も近いかで領域を分割している図形のこと.
様々なアプリケーションで用いることができ、ネットワーク、CG、医療、環境、建築など複数の分野で活用されている.
ボロノイ図の幾何的特徴
・ボロノイ図の頂点数は高々2n-5
・ボロノイ図の辺数は高々3n-6
・ボロノイ図の辺(ボロノイ辺)は隣接点同士の二等分線
| ボロノイ図とは |
ボロノイ図の成長の様子 | |
よく見られるのはユークリッド距離によって距離を計算して求めるボロノイ図形であるが、
これをマンハッタン距離に置き換えられたものなどもある. | 他の距離を使用したボロノイ図 |
マンハッタン距離を距離にしたボロノイ図 | |
ボロノイ図を求めるアルゴリズムの例 |
この章を学んで新たに学べる
Comments