重心ボロノイ分割

コルクボード風の壁紙を生成するアプレットを作っているときに，
・平面上に均等にランダムな点を作りたい
と思って何かいい方法がないか考えてみました．

で，使えるかな，と思った方法が

• ポワソンディスクサンプリング

各サンプリング点ごとに円盤状の半径を持っていて
新たにサンプリングするときに，それまでに配置されている他のサンプリング点の半径の中に入っていた場合は棄却し，他の点をサンプリングする．
というのを繰り返す．

• 重心ボロノイ分割をして，その重心を用いる

任意の数のサンプル点を適当に生成．
その点を用いて，ボロノイ分割をし，各領域の重心を求める．
サンプル点の位置をその領域の重心に移動．
これを，サンプル点と重心が一致(距離が閾値以内)になるまでくりかえす．

今回はサンプル点がいくつになってもいいようにしたかったので，重心ボロノイ分割を使うことにしました．
ポワソンディスクサンプリングでは，たくさんの点を配置しようとした場合に，
半径を変更しないと，サンプルをとれないような状況が出てくる気がしたので・・

あと，重心ボロノイ分割を使うと，
・一個のときには画面の中心に
・二個のときは画面を二等分するように
とキレイに配置できるので，今回の目的にはこちらが適していると判断しました．

で，重心ボロノイ分割の実装方法ですが，
各画素ごとに全探索をしてボロノイ分割・重心の計算をしているので，計算負荷が高めです．
この用途では，写真の大まかな配置位置を決めたいだけなので，正確に計算する必要はありません．
なので，キャンバスサイズの1/4のサイズの画像で重心ボロノイ分割を行い，その結果を元にして写真を配置しています．

重心ボロノイ分割のサンプルをprocessingで作ってみたので，↓こちらに置いておきます．
http://www.geocities.jp/sourcechord/tips/processing/index.html
最初にランダムにいくつかの点が配置されて，その点をもとにボロノイ分割がされています．
スペースキーを押すと，サンプル点の位置を，その点を含む領域の重心の位置に変更して，再びボロノイ分割をする，というものです．
サンプル点の位置と重心の位置が一致すると，それ以上ボロノイ分割されなくなります．
黒い点がサンプル点，赤い点が各領域の重心の位置です．
だいたい各領域の大きさが均等になるように分割されます．


左：ボロノイ分割　　　右：重心ボロノイ分割