著者

渡辺 貴史 村島 定行

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-コンピュータ (ISSN:09151915)

巻号頁・発行日

vol.79, no.3, pp.114-122, 1996-03-25

被引用文献数

19

---

ボロノイ図は勢力範囲図とも言うべきもので情報処理のさまざまの分野で重要な役割を果たしている. ボロノイ図を描く方法は母点間の垂直二等分線を描くのが一般的である. この方法では母点数をNとしてO(N)の計算時間がかかる. ここでは計算機画面上で多数の点を配置し, それぞれの点のボロノイ領域を色分けするアルゴリズムを提案する. この方法は与えられた母点に互いに異なる色を割り当てた後, その母点から近い画素順にどの母点の勢力範囲であるかを示す色を置いていくことで実現する. 既に色が置いてある場合はパスする. すべての画素にどの母点の勢力範囲であるかを示す色を置き終わるとボロノイ図が出来上がる. このアルゴリズムは整数演算に基づいているので丸め誤差などは影響しない. またボロノイ図の作成時間は母点の数に依存しない. 母点数2から4000の範囲で調べた結果, ほぼ一定の30秒であった. 距離を計算して, 最近接の母点を決定するS.K.Parui等の方法と比較すると, 母点数が10を超えると, ここで提案の方法が速くなることがわかった.