ボロノイ図
fitcでのマリオ・クリンゲマンさん(Quasimondo)のセッションで、
「そうそう、こういうことがやりたくて
こっちの世界に移ってきたんだよ!」
とものすごく刺激を受けてきました。
よし、この感動を忘れないよう、
マリオさんについていろいろ調べてまとめるかー
と思ってみたものの、まだ日本語での記事はあまりなく、
http://pingmag.jp/J/2007/07/23/fitc-flashy-islands/
本家のブログをがんばって読んでみるかー
と思った見たものの、びっしり書かれた英語にひるみ、
http://www.quasimondo.com/
とりあえずいろいろ使いまわせそうな「ボロノイ図」
http://ja.wikipedia.org/wiki/ボロノイ図
のサンプルでも作ろう、というところに落ち着きました。
で、こちらの記事のアルゴリズムの解説がわかりやすかったです。
http://d.hatena.ne.jp/rsakane/20090331/voronoi_diagram
- 適当な位置に点を置く(配列に全ての点の座標x,yを保持しておく)
- あるピクセルに注目して、そのピクセルと上で打った点の中で一番近いのを探す。
- その一番近い点の位置にある色を取得して、注目したピクセルに代入する。
- あとは、他の全ピクセルに同じように処理させるだけ。
#ボロノイ図って必ずしも「不規則な形で領域分割するための方法」てわけじゃないんですね
(最初に打つ点の位置関係によっては規則的な領域分割にもなりうる)
で、wonderfulにソースコードもありました。
http://wonderfl.net/code/870ff8531447e24f8bae52ace1bbda4c92b16049
こちらのソースでは、
- 100個の点を置く。各点は座標と速度を個別に保持。初期座標と速度は乱数で決定。
- 各点の座標を速度に応じて動かす
- 境界線の視点座標と終点座標を求める処理(ちゃんと解読してないけど、たぶん2点を結ぶ線分の二等分線の式を求めて、交点を求めたり云々してる)
- 境界線を描画
つまり、このクラスは「ボロノイで領域の境界線を引く」
というもののようです。
自分は「ビットマップをボロノイで領域分割」という使い方をしたいので、
コアな処理は自分で書く必要がありそう。
ちょっと今からつくってみようと思います。