じぇのサイト

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次元にも同様の方法で適用できます．その証拠が前回の記事の図にまります．