• 締切済み

凸包!

どちらさまか、凸包問題と言うのを知りませんか? 多数ある点を取り囲む多角形を求めるというものです。 現実的な話で言うと、 壁に多数の釘が刺さっていて、その一番外側を囲むように 輪ゴムを引っ掛けたときにできる多角形の角の座標を求め、 その座標すべてを出力するといったものです。 具体的なアルゴリズムはこちらを見ると詳しく載っています。 よろしくお願いいたします。 http://www.race.u-tokyo.ac.jp/~masuda/jugyo/program99/package.html

みんなの回答

  • nanura2
  • ベストアンサー率50% (4/8)
回答No.3

 解答とはいきませんがちょいと手助け。 一応このソースでは変数を宣言して、ファイルからデータを受け取るところまで書いてあります。 データファイルの形式は [x1],[y1] [x2],[y2] . . . と、カンマ区切りで縦に書いてください。(ちなみに[]はいりません) 一番下の/* ここから先が大切 */以下にグリグリかいていくわけです。 コンパイル時には -lm をつけましょう。 cc -lm Convex_Closure.c とかだったかな? それでは。 #include<stdio.h> #include<stdlib.h> #include<math.h> #include<string.h> /* 座標データ最大数 */ #define MAX_NUM 64 /* バッファサイズ */ #define BUF_SIZ 256 /* 円周率 */ #define PIE 3.14159265358979 /* 構造体宣言 */ typedef struct{ double x; double y; } point; FILE *fp; int main(int argc, char *argv[]) { int i, j; int last = 0; int wp, len, min, nxt; char rBuff[BUF_SIZ]; char Temp[64]; point p[MAX_NUM], tp; double rad[2]; /* ソース内でのデータ指定は面倒くさいのでファイルで渡すことにします。*/ if(argc == 1){ printf("データファイルがありません。\n"); return 0; } /* ファイルを開きましょう。*/ if( (fp = fopen(argv[1], "r")) == NULL ){ printf("ファイルのオープンに失敗しました。\n"); return 0; } /* p[]の初期化 */ for(i = 0 ; i < MAX_NUM ; i++) p[i].x = p[i].y = 0; /* ファイルの中身を1行ずつ読みます。 */ last = 0; while( fgets(rBuff, BUF_SIZ, fp) != NULL){ /* 読み込んだバイト数 */ len = strlen(rBuff); /* 座標データのセット */ for( i = 0, wp = 0 ; i < len ; i++ ){ /* X */ if(rBuff[i] == ','){ Temp[wp] = 0; wp = 0; p[last].x = atof(Temp); continue; } /* Y */ if(rBuff[i] == '\n' || rBuff[i] == 0){ Temp[wp] = 0; p[last].y = atof(Temp); break; } Temp[wp++] = rBuff[i]; } last++; } fclose(fp); /******************************************************************/ /* ここから先が大切 */ return 0; }

すると、全ての回答が全文表示されます。
  • nanura2
  • ベストアンサー率50% (4/8)
回答No.2

 凸多面体の基底を求めるアルゴリズムを拝見しましたが 書いてあることをそのままするだけですね。 書けませんでは何が書けないのかわからないのでアドバイスのしようがありません。 1.点データをセットするやり方がわからない。とか 2.どうやってΘを求めるかがわからない。とか 3.ループ文の条件がわからない。とか こうゆうのでしたら答えようもあるんですが。。。 いかかがなもんでしょう?

lusy7
質問者

補足

最初からすべてわかりません。 cは一通りやったのですが、 どうやら向いていないようで・・・・。

すると、全ての回答が全文表示されます。
  • nagata
  • ベストアンサー率33% (10/30)
回答No.1

えーと、一体何が聞きたいのでしょうか。 必要な情報はすべて出そろっているようですが。 凸包問題を知っている人と友達になりたいとか?

lusy7
質問者

補足

凸包問題のアルゴリズムはわかったのですが、 プログラムが書けません。cで。 非常に困ってます。 お願いいたします。

すると、全ての回答が全文表示されます。

関連するQ&A