凸包！

質問

どちらさまか、凸包問題と言うのを知りませんか？
多数ある点を取り囲む多角形を求めるというものです。
現実的な話で言うと、
壁に多数の釘が刺さっていて、その一番外側を囲むように
輪ゴムを引っ掛けたときにできる多角形の角の座標を求め、
その座標すべてを出力するといったものです。

具体的なアルゴリズムはこちらを見ると詳しく載っています。
よろしくお願いいたします。
http://www.race.u-tokyo.ac.jp/~masuda/jugyo/program99/package.html

回答No.3

nanura2

解答とはいきませんがちょいと手助け。
一応このソースでは変数を宣言して、ファイルからデータを受け取るところまで書いてあります。

データファイルの形式は
[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;

/* ファイルの中身を１行ずつ読みます。 */
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;
}

回答No.2

nanura2

凸多面体の基底を求めるアルゴリズムを拝見しましたが
書いてあることをそのままするだけですね。

書けませんでは何が書けないのかわからないのでアドバイスのしようがありません。

１．点データをセットするやり方がわからない。とか
２．どうやってΘを求めるかがわからない。とか
３．ループ文の条件がわからない。とか

こうゆうのでしたら答えようもあるんですが。。。
いかかがなもんでしょう？

補足

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

回答No.1

nagata

えーと、一体何が聞きたいのでしょうか。
必要な情報はすべて出そろっているようですが。

凸包問題を知っている人と友達になりたいとか?

補足

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