じぇのサイト

割りばしに3mm程の穴を開けたいと思ったので，小さい手動ドリルを買いに出かけました．
100均にドリルが売っているというある筋の情報を信じて，うろつきました．
しかし，実際は見つからず，結局，買えずに帰ってきました．
実に悲しいものです．
100均の他にもオモチャ屋やデパートまで回ったのに．

2次元のボロノイ図では，ボロノイ境界は線分によってで表現でき，3次元では閉じた面で表現できます．
線分は2点を指定することによって定義できますが，面というのはややこしく，頂点の数が定まらず，三角形や四角形，などの多角形によって定義します．
これはCGで描画するときに結構な面倒なことだと感じています．
ですが，多角形を分割していくと最終的に三角形にすることができますから，多角形を三角形にうまく分割できれば，その問題はなくなります．
しかし，次はどのように三角形に分割するかという問題が出てきます．
一般的な手法はどのようなものなのでしょうか．ボクは知りません．

三角化の手法としては，ドロネー図などが応用できます．
あるボロノイ境界の点群（ボロノイ頂点）から三角形のみの図を作って，ボロノイ境界に乗っている三角形のみを取り出します．
その処理を全ボロノイ領域に行うと，ボロノイ境界上の三角化されたメッシュを得ることができます．
その三角形を描画すれば，3次元のボロノイ図をボロノイ境界によって表示させることができます．
例としてはこの画像です．

赤い点がボロノイ図の母点，青い点がボロノイ頂点，面がボロノイ境界で，中が見えるように透過してレンダリングしています．
しかし，この絵ではうまくいっているのかわかりにくい．
どうすれば見やすい絵作りができるか，模索中であります．

ボロノイ図の計算のためにqhullを用います．
www.qhull.org/

自分でコードを書いても良いかもしれませんが，高速化も面倒なことですし，ここは優秀なツールを使いましょう．
qhullのqhull.exeを用いていてボロノイ図を計算する際，次元と頂点数，頂点が定義された母点が必要です．
今回も思い切って簡単な母点で実験してみましょう．
ドロネー図の実験同様，2次元で4点，(1,0)(0,0)(0,2),(1,1)という点群で実験してみます．

2
4
1 0
0 0
0 2
1 1

これをtest.ptsという名前のテキストファイルとします．実際は，拡張子はなんでもいいです．
これからボロノイ図を計算します．
ボロノイ図のファイルは「test.vrn」という名前で保存することにします．
qhullでボロノイ図を計算するとき，オプションを指定してやる必要があります．
そのオプションはボロノイ図の「v」とOFF(オブジェクトファイルフォーマット)のための「o」，そしてファイル出力の「TO ファイル名」です．
この「o」のアウトプットは
・次元
・ボロノイ頂点数とボロノイ領域数，尾根の数
・ボロノイ頂点
・ボロノイ領域
となります．
最初の次元は入力が2次元なら2次元ですし，3次元なら3次元です．
2番目のボロノイ頂点数とボロノイ領域数，尾根の数がスペース区切りで並んでいます．
ボロノイ図の頂点とボロノイ領域の数はそのままです．
最後の尾根の数というのがわかりにくいのですが，ボロノイ図の場合，qhull側が定義した無限遠としている点の数です．
ボロノイ図には必ず無限遠の頂点が必要であり，その無限を指すために仮に定義しています．
この値が1の場合，ボロノイ頂点のうち，1番目の点が無限遠と定義されているようです．
3番目の項目のボロノイ頂点というのは，座標が並んでおり，一行につき，一つの頂点が定義されています．
4番目の項目のボロノイ領域は3番目の項目で定義されたボロノイ頂点を指すインデックスで定義されています．
ボロノイ領域が定義されている列の1番目の要素は，ボロノイ領域の頂点の数が記されています．
それ以降は，ボロノイ頂点のインデックスになります．
実際に先ほど定義したtest.ptsで計算させます．
そのときのコマンドはこのようになります．

qhull v o TO test.vrn < test.pts

このコマンドによってtest.vrnが作成されます．

2
3 4 1
-10.101 -10.101
   0.5    0.5
     0      1
2 0 1
3 2 0 1
2 0 2
3 0 1 2

最初の列が2次元を指し，次に3頂点，4領域，無限遠1，頂点3つの座標，領域4つのインデックスとなっています．
ちなみに領域の数と入力の母点の数は必ず同じになります．
その上，入力の頂点に対応したボロノイ領域が同じインデックスとして計算されています．
つまりは，最初の母点に対応したボロノイ領域はボロノイ領域の最初に定義されているということです．

無限遠を抜いて描画するとこのようになります．
母点を黒，ボロノイ頂点を赤，ボロノイ辺を緑としています．



これは見ての通り，ほとんどが無限遠のため描画しても1本しか表せません．
もっと多くの点を描画すると，このようになります．

ボロノイ図(Voronoi diagram)は，母点(site)からボロノイ領域(Voronoi region)を計算し，その堺をボロノイ境界(Voronoi edge，2次元上ではボロノイ辺)として構成した図です．
ある母点が最も近くにある領域をある母点のボロノイ領域として定義しています．
また，ボロノイ境界の頂点をボロノイ頂点(Voronoi vertex)としています．

ボロノイ図は，ドロネー図同様，2次元以上ならば任意の次元で定義できます．
しかし，2次元平面上に分布された母点から3次元のボロノイ図は計算することは難しいです．
2次元上に母点がある場合，すべてのボロノイ領域が3次元方向に無限になるため，ボロノイ図をボロノイ頂点として構成できません．
頂点の座標が定義できないため，コンピュータでは2次元の母点からは3次元のボロノイ図は計算できません．

とにかく，ボロノイ図を見てましょう．
このうさぎの頂点を母点とし，ボロノイ図を計算してみます．
色は表裏がわかりやすいように，6方向から別の色の光が当たるように光源を設定しています．


これが母点となるモデルです．



これがうさぎのボロノイ図です． 3次元の母点だとこのようになります．
ボロノイ境界が面ですから，描画したとき，奥が見えなくなり，何がなんだかわかりません．
ということで面の辺のみを描画してみました．

/*画像が重すぎるため削除しました*/
/*意味がなさすぎるので，もう少し意味ありげなときにスタンフォードバニーを使います*/

まぁ結局同じようなものです．

不満が残るかもしれませんが，これがボロノイ図です．

www.qhull.org/

qhullのqdelaunay.exeという実行ファイルに点群データ入力すると，その点群からドロネー図を構成して出力することができます．
しかし，このときオプションで設定する必要があります．
このオプションに関しては，qhullサイトのqdelaunayの項目に適度に書いてあります．
http://www.qhull.org/html/qdelaun.htm

今回は思い切って簡単にいきましょう．
点群の座標をqdelaunayに入力し，その点群のドロネー図を頂点のインデックスで出力させましょう．

qhullの仕様だと，点群の定義は「次元」「点の個数」「座標」が必要で，入力するときもその順である必要があります．
座標は頂点を一行に一頂点とし，各次元の値はスペース区切りで記述します．
2次元で4点，(1,0)(0,0)(0,2),(1,1)という点群だと

2
4
1 0
0 0
0 2
1 1

となります．これを「test.pts」という名前でファイルに保存します．
このときの拡張子はなんでもいいです．

三角化したドロネー図を返してほしい場合のオプションは「Qt」で，ドロネー図のドロネー領域の数とその頂点のインデックスだけを返してほしい場合のオプションは「i」です．
それに，結果を表示させるために「s」のオプションをつけます．
これら「Qt i s」によって，入力に対して，領域数とそのインデックスを表示させることができます．
表示されるものをリダイレクトでファイルにそのまま保存すれば，インデックスデータが入ったファイルが作れます．
入力に関してはパイプを使ってもよいと思いますが，ファイルに保存してあるので，入力のリダイレクトを用いると便利だと思います．
今は実験的に出力されたデータを「test.dln」という名前を付けます．
コマンドは次のようになります．

qdelaunay Qt s i < test.pts > test.dln

リダイレクトでtest.ptsを入力し，表示される内容をリダイレクトでtest.dlnに保存しています．
これを行った結果test.dlnは次のようになります．

2
0 3 1
3 2 1

これがtest.ptsのドロネー図です．
実際に描画してみましょう．



赤い線がドロネー図のエッジです．
これは2次元ですが，3次元にも同様の方法で適用できます．その証拠が前回の記事の図にまります．