離散ボロノイ図

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

離散ボロノイ図(りさんボロノイず、英語:Discrete Voronoi diagram)は、画素の集合からなる平面上で考えたボロノイ図である。

画素毎に最も近い母点へ所属させる。離散ボロノイ図のボロノイ領域は多角形ではなく画素の集合で表され、遠くからは通常のボロノイ図と同じに見える。通常のボロノイ図では勢力分割線の交点を求めなければならないが、離散ボロノイ図では任意の画素にとってどの画素が最も近いか決定すればよい。その方法として、母点のある画素から距離の順に母点の所属を決めていく波面法がわかりやすい。通常のボロノイ図では母点が多くなると計算誤差の累積のためにアルゴリズムが破綻をきたすが、離散ボロノイ図ではアルゴリズムが簡単であるために破綻しにくい。

外部リンク[編集]