ドロネー三角形のプログラム

質問

二次元上にある点群を読み込み、ドロネー三角形を作成したいのですが、紙の上で絵を描いて考えるのと、プログラム上で考えるのとではまったく違うことに気づき、初っ端から手が止まっています。

点群を入れる大きな三角形は作成しました。

struct coo // 座標の構造体
{
float x;
float y;
}

struct tri　　　　 // 頂点を入れる構造体
{
struct coo top[3];
}

main (){

float **prj; // ここに点群がある
float M_prj[3][2];　　// 点群を入れる大きな三角形の３つの頂点
int Q;　　　　　　　　// 読み込んだ頂点が他の三角形の外接円の中に含まれているか判断する

struct tri triangle[100];　　　　　// 三角形をを入れる構造体

// まず、大きな三角形を三角形の配列(triangle)に入れる

for(i=0; i<3; i++){
triangle[0].top[i].x = M_prj[i][0];
triangle[0].top[i].y = M_prj[i][1];
}

// 外接円の中に点Pを含むものを探す

Q = hantei;

// 含むなら分割する

if(Q > 0){
}
}

というように続いていくと思うのですが。。。
ドロネー三角形については理解しているつもりですが、プログラムになると全くです。そして、プログラミングは初心者です。

ここから先、どのように考えていけばよいでしょうか。

回答No.1

seta_takahiro

ドロネー図、ボロノイ図について、
効率の良いアルゴリズムがどんなものだったか、
参考書を参照しないと思い出せないので、
参考意見にもならないかもしれませんが、書くだけ書きます。

まず、「hantei」とある関数はかけているのでしょうか？
各三角形の外接円の中心および半径を求めることが出来れば良いので、
垂直二等分線の式を2つ求めて、交点を計算すれば中心が求まるという感じでしょうか。
これは簡単な方程式で行けそうだな、と思いました。

「分割する」というのは、点が3角形に含まれる場合と
外接円には含まれるけれど3角形には含まれない、
という場合とで、難しさが違う様な気がしますが、
とりあえず3本線をつないで、
辺が交差してしまったら交差した辺を消せば良さそう気がするので、
何とかなるのかな、と思います。

後は、考えているアルゴリズムが正しくドロネー図を計算出来るのか、
言い替えると、3角形を分割することによって、外接円の形が変わって、
分割が連鎖する、と言った状況について、考えられているのか、
というのが気になります。
知識がないので、要らない心配だったらごめんなさい。

読むのは大変かもしれませんが、
http://www2s.biglobe.ne.jp/~kaz_h/Tech/engineer.html#voronoi
http://www.simplex.t.u-tokyo.ac.jp/~sugihara/opensoft/opensoft.html
のソースは参考になるのではないのでしょうか

また、有名なアルゴリズムだと思うので、本屋でアルゴリズム辞典的なものを探すのも良いように思います

お礼

ごめんなさい。返信遅くなりました。
回答ありがとうございます。

hanteiの関数は行列式の関数でかけています。

私は座標での計算が必要だと思ったのですが、そうではなくて、点と点の番号でリスト構造でプログラムしていくと良いみたいです。それでも？がいっぱいなのですが。。。

結ぶというよりは、点３つを１つの箱に入れる、といった感じです。
その点の出し入れで、メッシュ/ポリゴンができます。