離散ボロノイ図

離散ボロノイ図

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

『フリー百科事典ウィキペディア日本語版』 2008/12/12/07/08、URL: http://ja.wikipedia.org/