- 締切済み
ドロネー三角形のプログラム
seta_takahiroの回答
- seta_takahiro
- ベストアンサー率60% (23/38)
ドロネー図、ボロノイ図について、 効率の良いアルゴリズムがどんなものだったか、 参考書を参照しないと思い出せないので、 参考意見にもならないかもしれませんが、書くだけ書きます。 まず、「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 のソースは参考になるのではないのでしょうか また、有名なアルゴリズムだと思うので、本屋でアルゴリズム辞典的なものを探すのも良いように思います
関連するQ&A
- プログラムが解読できないです。解読していただける方いませんか？
以下のプログラムなんですが、各変数の値、および配列がどのように動いているのか、理解できなくて困っています。どなたか解読していただける方いらっしゃいましたら、出来るだけ詳しくお願いします。。 { int triangle[3]={0,1,2}; int nextVertex; int i; /* 三角形の頂点の組を表示 */ printf("Triangle %d : ",1); for(i=0;i<3;i++){ printf("(%f, %f)",x[triangle[i]], y[triangle[i]]); } printf("\n"); /* 各頂点の処理 */ for(nextVertex=3;nextVertex < n; nextVertex++){ double m,k; int side1,side2; /* 傾きが極端に大きくなったときに計算誤差が発生。これが起こらないよう、傾きが1を境に処理をxとyで入れ替える*/ if(y[triangle[2]]-y[triangle[1]]<x[triangle[2]]-x[triangle[1]]){ /* 直線の傾き・切片を計算 */ m=(y[triangle[2]]-y[triangle[1]])/(x[triangle[2]]-x[triangle[1]]); k=y[triangle[2]]-m*x[triangle[2]]; /* side1,side2にはy>mx+kが成り立っていれば0以外、成り立たなければ0がそれぞれ入る */ side1=y[triangle[0]]>m*x[triangle[0]]+k; side2=y[nextVertex]>m*x[nextVertex]+k; }else{ /* xyを入れ替えただけ */ m=(x[triangle[2]]-x[triangle[1]])/(y[triangle[2]]-y[triangle[1]]); k=x[triangle[2]]-m*y[triangle[2]]; side1=x[triangle[0]]>m*y[triangle[0]]+k; side2=x[nextVertex]>m*y[nextVertex]+k; } /* 判別結果によって次の三角形の頂点を選択 */ if(side1^side2){ /* 排他的論理和を使って判別。side1/side2のいずれか一方のみが非0のとき条件成立 */ triangle[0]=triangle[1]; } /* else節はなくても一緒なので略す else{ triangle[0]=triangle[0]; } */ triangle[1]=triangle[2]; triangle[2]=nextVertex; /* 三角形の頂点の組を表示 */ printf("Triangle %d : ",nextVertex-1); for(i=0;i<3;i++){ printf("(%f, %f)",x[triangle[i]], y[triangle[i]]); } printf("\n"); } }
- 締切済み
- C・C++・C#
- 点の組をキューに入れたいのですが。
以下のプログラムは、小さい順にソートされたx座標を三角形にして分割するプログラムです。 三角形の頂点の組をすべてキューQに入れたいのですがどうしたらよいでしょうか？ 初歩的な質問かもしれませんが、回答してくれるかたいましたらよろしくお願いします。 --------------------------------------------- #include <stdio.h> double x[100],y[100]; int n; int main() {int triangle[3]={0,1,2}; int nextVertex; int i; makepoints(&n, x, y); /* 三角形の頂点の組を表示 */ printf("Triangle 1 : "); for(i=0;i<3;i++){ printf("%d ",triangle[i]); } printf("\n"); /* 各頂点の処理 */ for(nextVertex=3;nextVertex < n; nextVertex++){ double m,k; int side1,side2; /* 傾きが極端に大きくなったときに計算誤差が発生。これが起こらないよう、傾きが1を境に処理をxとyで入れ替える*/ if(y[triangle[2]]-y[triangle[1]]<x[triangle[2]]-x[triangle[1]]){ /* 直線の傾き・切片を計算 */ m=(y[triangle[2]]-y[triangle[1]])/(x[triangle[2]]-x[triangle[1]]); k=y[triangle[2]]-m*x[triangle[2]]; /* side1,side2にはy>mx+kが成り立っていれば0以外、成り立たなければ0がそれぞれ入る */ side1=y[triangle[0]]>m*x[triangle[0]]+k; side2=y[nextVertex]>m*x[nextVertex]+k; }else{ /* xyを入れ替えただけ */ m=(x[triangle[2]]-x[triangle[1]])/(y[triangle[2]]-y[triangle[1]]); k=x[triangle[2]]-m*y[triangle[2]]; side1=x[triangle[0]]>m*y[triangle[0]]+k; side2=x[nextVertex]>m*y[nextVertex]+k; } /* 判別結果によって次の三角形の頂点を 選択 */ if(side1^side2){ /* 排他的論理和を使って判別。side1/side2のいずれか一方のみが非0のとき条件成立 */ triangle[0]=triangle[1]; } /* else節はなくても一緒なので略す else{ triangle[0]=triangle[0]; } */ triangle[1]=triangle[2]; triangle[2]=nextVertex; /* 三角形の頂点の組を表示 */ printf("Triangle %d : ",nextVertex-1); for(i=0;i<3;i++){ printf("%d ",triangle[i]); } printf("\n"); } printf("正常に終了しました。何かキーを押してください。"); rewind(stdin); getchar(); }
- 締切済み
- C・C++・C#
- ばばぬきプログラムについて
下記のようなプログラムで4人のコンピュータにババヌキをさせるプログラムを組んでる最中なんです。 decklistまでは表示できてもshufflelistではコンパイルは通っても実行するとデバックが起きてしまって困っています。while文をなくすとちゃんと返り値を持って表示はできるんですがwhile分で繰り返したとたんデバックが起きるんですがその理由がわかりません。どうして無理でしょうか？ご教授願います。 decklistは整列されリストに保存した山札の関数。 shufflelistはランダムで保存していく関数。 personの関数はdecklistのほうで試したところコンパイルは通るんですがこちらもデバックが起きてしまいます。 #include<stdio.h> #include<stdlib.h> #include<string.h> #include<time.h> #define N 53 //デッキのカードの構造体 struct card{ int t; struct card *next; }*deck; //カードを配った後のそれぞれのプレイヤーの情報（仮 struct player{ int card; struct player *nextcard; struct player *nextturn; }; //関数定義 struct card *talloc(void); struct player *lalloc(void); struct card *decklist(void); struct card *shufflelist(void); struct player *person(struct player *P); void displist(void); int main(void){ struct player *A,*B,*C,*D; struct player *p; p=person(A); while(p!=NULL){ printf("%d ",p->card); p=p->nextcard; } return 0; } //card構造体のセルの確保 struct card *talloc(void){ return (struct card *)malloc(sizeof(struct card)); } //player構造体のセルの確保 struct player *lalloc(void){ return (struct player *)malloc(sizeof(struct player)); } //カードを切る前の整列された山札の関数 struct card *decklist(void){ int i,add=1,count=0; struct card *p; deck=NULL; for(i=0;i<53;i++){ if(count==4){ add+=1; count=0; } p=talloc(); p->t=add; p->next=p; count++; p->next=deck; deck=p; } return deck; } //山札をシャッフルした後の山札の関数 struct card *shufflelist(void){ int i,a,count=0,r; struct card *d,*p,*q,*shuffle; p=decklist(); shuffle=NULL; while(p!=NULL){ srand(time(NULL)); r=(int)rand()%(N-count); for(i=0;i<r;i++){ p=p->next; } q=talloc(); q->t=p->t; d=p->next; p->next=d->next; q->next=shuffle; shuffle=q; count++; p->next=p; } return shuffle; } //プレイヤーへカードを配るための関数 struct player *person(struct player *PERSON){ struct player *a; struct card *library; int i; PERSON=NULL; library=decklist(); a=lalloc(); while(a!=NULL){ a->card=library->t; for(i=0;i<4;i++){ library=library->next; } a->nextcard=a; a=PERSON; } a->nextcard=NULL; while(a!=NULL){ printf("%d ",a->card); } return PERSON; }
- ベストアンサー
- C・C++・C#
- Ｃ言語 構造体でつまずいています
以下、番号と点数を入力して構造体配列に入力し、番号に0が入力されたら、入力処理をやめ、平均点を表示するプログラムです。 今のコードでは、最初から番号に0を入力すると、0除算になりエラーになります。どうすれば良いのでしょうか？ #include <stdio.h> #define MAX 50 //配列の要素数を定義 int count=0; //グローバル変数 struct data { //構造体の定義 int num; //メンバの宣言 int ten; }; void nyuryoku(struct data *); //プロトタイプ宣言 float heikin(struct data *); //プロトタイプ宣言 void main() { struct data score[MAX]; //構造体の宣言 printf("**学生番号／点数入力**\n"); printf("\n"); nyuryoku(score); //nyuryoku関数呼び出し printf("\n**以上%d名の平均点：%0.1f点**\n",count,heikin(score)); //heikin関数の戻り値表示 } //nyuryoku関数 //機能：構造体配列にデータを入力する void nyuryoku(struct data *pd) //仮引数pdに構造体ポインタが渡る { int i; for(i=0;i<MAX;i++){ printf("学生番号>>"); scanf("%d",&pd->num); if(pd->num==0){ //学生番号に0を入力するとループを抜ける break; } printf("点 数>>"); scanf("%d",&pd->ten); count++; //人数のカウント pd++; //構造体配列を一つずらす } } //heikin関数 //機能：構造体配列の点数の平均を計算、戻り値として返す float heikin(struct data *pd) //仮引数pdに構造体ポインタが渡る { int i; int sum=0; float ave=0; for(i=0;i<MAX;i++){ if(pd->num==0){ break; } else{ sum+=pd->ten; //点数を加算 pd++; } } ave=(float)sum/count; //平均値を求める return(ave); //平均値を戻り値として返す }
- ベストアンサー
- C・C++・C#
- ポインタと構造体
C言語初心者です。 下のコードはリスト構造のサンプルコードを元に自分で書き直そうとしているコードです。（なので、現時点では不完全なところ（例えばfreeしてないとか）があるのと、自分で理解出来ていない箇所があります。） 実行すると、８から３までの値が一応表示されるようになったですが、その過程の仕組みが自分でもよく理解出来ていません。 （１）tra *q = NULL; 通常、構造体のポインタを使用するときはq = &___のように他の構造体のアドレスを渡して使用出来るようにすると思いますが、ここではなぜ*qに、NULLを代入する必要があるのでしょうか。 （２）そのNULL状態のポインタqを関数printingdudeに突っ込んで結果的に８、７、６、、と出力されるまでの過程がよくわかりません。簡単に解説して頂けると助かります。（ちょっと雑な質問になってしまい申し訳ありません） typedef struct transcript{ int no; struct transcript *next; } tra; void printingdude(struct transcript *m); tra* noud(int v, tra* c); int main(){ tra *q = NULL; int i; for(i = 8; i>1; i--){ printingdude(q); q = noud(i, q); } return; } void printingdude(struct transcript *m){ if(m ==NULL) return; printf("%d\n", m->no); } tra* noud(int v, tra* c){ tra *a = (tra *) malloc(sizeof(tra)); a->no = v; a->next = c; return a; }
- ベストアンサー
- C・C++・C#
- ドロネー三角形分割のプログラムを作成中なのですが、参考プログラムが読めなく困っています。
ドロネー三角形分割のプログラムを作成中なのですが、参考プログラムが読めなく困っています。 ソースコードは以下の様になります。 -------------------------------------------------- bool incircle(point a, point b, point c, point p) { a -= p; b -= p; c -= p; return norm(a) * cross(b, c) + norm(b) * cross(c, a) + norm(c) * cross(a, b) >= 0; // < : inside, = cocircular, > outside } #define SET_TRIANGLE(i, j, r) \ E[i].insert(j); em[i][j] = r; \ E[j].insert(r); em[j][r] = i; \ E[r].insert(i); em[r][i] = j; \ S.push(pair<int,int>(i, j)); #define REMOVE_EDGE(i, j) \ E[i].erase(j); em[i][j] = -1; \ E[j].erase(i); em[j][i] = -1; #define DECOMPOSE_ON(i,j,k,r) { \ int m = em[j][i]; REMOVE_EDGE(j,i); \ SET_TRIANGLE(i,m,r); SET_TRIANGLE(m,j,r); \ SET_TRIANGLE(j,k,r); SET_TRIANGLE(k,i,r); } #define DECOMPOSE_IN(i,j,k,r) { \ SET_TRIANGLE(i,j,r); SET_TRIANGLE(j,k,r); \ SET_TRIANGLE(k,i,r); } #define FLIP_EDGE(i,j) { \ int k = em[j][i]; REMOVE_EDGE(i,j); \ SET_TRIANGLE(i,k,r); SET_TRIANGLE(k,j,r); } #define IS_LEGAL(i, j) \ (em[i][j] < 0 || em[j][i] < 0 || \ !incircle(P[i],P[j],P[em[i][j]],P[em[j][i]])) double Delaunay(vector<point> P) { const int n = P.size(); P.push_back( point(-inf,-inf) ); P.push_back( point(+inf,-inf) ); P.push_back( point( 0 ,+inf) ); int em[n+3][n+3]; memset(em, -1, sizeof(em)); set<int> E[n+3]; stack< pair<int,int> > S; SET_TRIANGLE(n+0, n+1, n+2); for (int r = 0; r < n; ++r) { int i = n, j = n+1, k; while (1) { k = em[i][j]; if (ccw(P[i], P[em[i][j]], P[r]) == +1) j = k; else if (ccw(P[j], P[em[i][j]], P[r]) == -1) i = k; else break; } if (ccw(P[i], P[j], P[r]) != +1) { DECOMPOSE_ON(i,j,k,r); } else if (ccw(P[j], P[k], P[r]) != +1) { DECOMPOSE_ON(j,k,i,r); } else if (ccw(P[k], P[i], P[r]) != +1) { DECOMPOSE_ON(k,i,j,r); } else { DECOMPOSE_IN(i,j,k,r); } while (!S.empty()) { int u = S.top().first, v = S.top().second; S.pop(); if (!IS_LEGAL(u, v)) FLIP_EDGE(u, v); } } double minarg = 1e5; for (int a = 0; a < n; ++a) { for (set<int>::iterator itr = E[a].begin(); itr != E[a].end(); ++itr) { int b = *itr, c = em[a][b]; if (b < n && c < n) { point p = P[a] - P[b], q = P[c] - P[b]; minarg = min(minarg, acos(dot(p,q)/abs(p)/abs(q))); } } } return minarg; } -------------------------------------------------- http://www.prefield.com/algorithm/geometry/delaunay.htmlのサイト様のものなんですが、私自身ｃ++プログラム初心者なので、わからず困っています。。概要でも結構ですのでどなたか回答してくださる方いらっしゃれば回答よろしくお願いします。
- 締切済み
- C・C++・C#
- 因数分解プログラム（Ｃ言語）について（2）
つづきです /*因数分解できるか判断する関数*/ int judge(int *a,int *b,int *c,float *D) { *D = (float)((*b) * (*b)) - (4 * (*a) * (*c)); if(D > 0 || D ==0){ printf("判別式は条件を満たしました。\n因数分解を行います。\n"); } else if(D < 0){ printf("判別式はD < 0であるため、因数分解できません。\n"); exit(1); } return 0; } /*因数分解をする関数*/ int bunkai1(int *a,int *b,int *q,int *n1,int *m1,float *D) { *q = sqrt(*D); *n1 = -(*b) + *q; *m1 = 2 * (*a); return 0; } int bunkai2(int *a,int *b,int *q,int *n2,int *m2,float *D) { *q = sqrt(*D); *n2 = -(*b) - *q; *m2 = 2 * (*a); return 0; } /*約分を行う関数*/ int yakubun1(int *m1,int *n1,int *min1,int *flag,int *i,int *d,int *e) { /*最大公約数を見つける*/ if(*m1 < *n1){ *min1 = *m1; } else{ *min1 = *n1; } *flag = 0; for(*i = min1; *i > 0; *i--){ if(*m1 % *i == 0){ if(*n1 % *i == 0){ *flag = 1; break; } } } つづく 関連URL:http://www.okweb.ne.jp/kotaeru.php3?q=474593
- 締切済み
- C・C++・C#
- 構造体
プログラミングの授業で構造体を習ったのですが、課題がよく分からないので質問させていただきます。その課題ですが、 複素数を表す構造体を、 struct complex{float r;（実部）float i;（虚部）}; の形で定義したとして、２つの複素数を入力し、その２つの絶対値の２乗、和、差、積、商を求めるプログラムを作るというものです。 ただし、条件として、 複素数を入力する関数void inputComp(struct complex*c)、複素数をａ＋ｂｉのような形に表示する関数void printComp(struct complex*c)、複素数の絶対値の２乗を関数値として返す関数float asqrComp(struct complex*c)を作成せよというのがあって困っています。 条件がなければprintfを多用してできないこともないでしょうが、条件を満たすプログラムを教えてください。
- 締切済み
- C・C++・C#
お礼
ごめんなさい。返信遅くなりました。 回答ありがとうございます。 hanteiの関数は行列式の関数でかけています。 私は座標での計算が必要だと思ったのですが、そうではなくて、点と点の番号でリスト構造でプログラムしていくと良いみたいです。それでも？がいっぱいなのですが。。。 結ぶというよりは、点３つを１つの箱に入れる、といった感じです。 その点の出し入れで、メッシュ/ポリゴンができます。