じぇのサイト

ボロノイ図の計算のために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本しか表せません．
もっと多くの点を描画すると，このようになります．