初心者の質問で申し訳ありません。

質問

初心者の質問で申し訳ありません。

点の座標情報(x,y,z)が入っているテキストデータを読み込み、
それぞれの点同士が距離r以内に存在するか、しないかを判定する
プログラムについて教えていただきたいです。

距離r以内に他の点が存在しない点は消去、
距離r以内に他の点が存在している点は書き出し、という流れを考えています。

どなたかご教授お願い致します。

回答No.5

asuncion

＞if (flag ==1){
＞fprintf(outfile,"%f,%f,%f,%f,%f,%f,%f,%f \n", xx, yy, zz, rr, gg, bb, pp, qq);
＞} else {
＞fprintf(outfilefly,"%f,%f,%f,%f,%f,%f,%f,%f \n", xx, yy, zz, rr, gg, bb, pp, qq);
＞}

ここは、xxなどのアドレス値を書き込みたいのですか？本当に？
また、

＞double* xx = (double*)malloc(number+1*sizeof(double));

mallocの引数は本当に正しいですか？
double* xx = (double*)malloc((number+1)*sizeof(double));
ではなくて、ですか？

回答No.4

magicalpass

ある点から半径ｒの球内に別の点Ａが存在するかという判定には２通りあります。
(1)球面の方程式を用いて、点Ａがその内部に存在するかどうか。
(2)球の中心との距離がｒ以下かどうか。

(1)は点の分布がある直線上に沿ってるとか、ある平面上に分布してるとか、あるいは判定中心が常に固定しているので球体空間の座標データをテーブルで固定して持てる（準備に計算時間が掛りますが）とかいう時には効率的に行えますが、１点１点を個別に判定する場合は(2)の距離を求めるのと大差ありません。

質問内容の問題だと素直に(2)の距離判定の方が良いでしょう。

やり方としては点のデータを最初から順番に、その点から後続の他の点が距離ｒ内にあるかどうかを１点１点調べていきます。もし、距離ｒ内に別の点があれば、その点と判定対象の別の点には他の点が存在するとし、判定の基準を「存在する」となっていない後続の最初の点から繰り返します。

点Ａ，Ｂ，Ｃ，Ｄ，Ｅがあったとして
１．Ａを基準に判定を開始
　ａ．ＢはＡの球の外
　ｂ．ＣはＡの球の中 → ＡとＣを「存在する」に設定
２．Ｂを基準に判定を続ける
　ａ．Ｃは既に「存在する」のでパス
　ｂ．ＤはＢの球の外
　ｃ．ＥはＢの球の外
　ｄ．Ｂは「存在しない」に設定
３．Ｃは既に「存在する」のでパス
４．Ｄを基準に判定を続ける
　ａ．ＥはＤの球の中 → ＤとＥを「存在する」に設定
５．Ｅは既に「存在する」のでパス
６．終了

１つでも距離ｒ内の点があればそこで判定を中断できるのですべての点について判定処理を繰り返す必要はありません。（無い場合は最後まで判定しないといけませんが）

回答No.3

akayoroshi

x座標の差がr以上だったら2点間の距離を計算しなくてもよいということを考えれば、計算量を減らせると思います。
配列markを用意しておいて、
double rr=r*r;
for (i=0; i<n; i++ ) mark[i]=0;
for ( i=0; i<n-1; i++ ) {
double dx, dy, dz;
if ( mark[i]!=0 ) continue;
for ( j=i+1; j<n; j++ ) {
dx=fabs(x[i]-x[j]);
if ( dx>r ) continue;
dy=fabs(y[i]-y[j]);
if ( dy>r ) continue;
dz=fabs(z[i]-z[j]);
if ( dz>r ) continue;
if ( dx*dx+dy*dy+dz*dz>rr ) continue;
mark[i]=1;
mark[j]=1;
break;
}
}
の後でmark[i]の値が0のものを消去するというのはどうでしょうか。

補足

回答していただきありがとうございます。

今のところ計算量はかなり耐えうる環境なので大丈夫そうなんですが、
xだけですと、3次元を考えると除ききれないような気がしました。

以下にプログラムの一部を載せました。
この流れのなかで、/*点から半径rの球に含まれる点があるのかないのか判定する*/という部分でつまずいています。。

printf("memory20100705\n");
double xx,yy,zz,rr,gg,bb,pp,qq ;

double* xx = (double*)malloc(number+1*sizeof(double));
double* yy = (double*)malloc(number+1*sizeof(double));
double* zz = (double*)malloc(number+1*sizeof(double));
double* rr = (double*)malloc(number+1*sizeof(double));
double* gg = (double*)malloc(number+1*sizeof(double));
double* bb = (double*)malloc(number+1*sizeof(double));
double* pp = (double*)malloc(number+1*sizeof(double));
double* qq = (double*)malloc(number+1*sizeof(double));

FILE* inifile = fopen("pos.txt", "r");
if(inifile==NULL)
{
printf("pos.txt is nothing!!");
return 0;
}

FILE* outfile = fopen("outpos.txt", "w");
if(outfile==NULL)
{
printf("outpos.txt is nothing!!");
return 0;
}

FILE* outfilefly = fopen("outposfly.txt", "w");
if(outfilefly==NULL)
{
printf("outposfly.txt is nothing!!");
return 0;
}

for ( int ii = 0, ii < number, ii ++ )
{ fscanf( inifile,"%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf \n", &xx[ii], &yy[ii], &zz[ii], &rr[ii], &gg[ii], &bb[ii], &pp[ii], &qq[ii] );
}
{
printf("%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf \n", xx[ii], yy[ii], zz[ii], rr[ii], gg[ii], bb[ii], pp[ii], qq[ii]);
return 0;
}

/*点から半径rの球に含まれる点があるのかないのか判定する*/
{
int flag, r;
flag = 1;
if ( 0.5 <= sqrt((ii.xx-jj.xx)*(ii.xx-jj.xx)+(ii.yy-jj.yy)*(ii.yy-jj.yy)+(ii.zz-jj.zz)*(ii.zz-jj.zz))
flag = 0;
break;
}

if (flag ==1){
fprintf(outfile,"%f,%f,%f,%f,%f,%f,%f,%f \n", xx, yy, zz, rr, gg, bb, pp, qq);
} else {
fprintf(outfilefly,"%f,%f,%f,%f,%f,%f,%f,%f \n", xx, yy, zz, rr, gg, bb, pp, qq);
}

fclose(inifile);
fclose(outfile);
fclose(outfilefly);

printf("Normal END \n");
return 0;
}

回答No.2

edomin7777

２点間の距離を求めるのはそんなに難しくありません。
例えば、(x1,y1,z1)と(x2,y2,z2)間の距離なら、
kyori = (float)sqrt( (double)(x1-x2)*(double)(x1-x2) + (double)(y1-y2)*(double)(y1-y2) + (double)(z1-z2)*(double)(z1-z2) );
こんな感じになると思います。

でも、最初の前提条件が判りません。
> 距離r以内に他の点が存在しない点は消去、
これが、どの点からなのかということです。
点１(x1,y1,z1)、点２(x2,y2,z2)、点３(x3,y3,z3)という順番で点を読み込んだとき、
点１と点２はrよりも離れているとし、点１と点３もrよりも離れているとします。
でも、点２と点３はr以内の距離だった場合、
消去するのは点１？点２？点３？

補足

説明不足で申し訳ありません。
考え直したところ、点と点の距離ではなく、
点を中心とした半径rの球内にその他の点が存在するか、しないか、というプログラムが必要でした。

3次元に無数に存在する点群があり、その点群の数を減らす為に、
点と点同士が離れている点だけを消去（別ファイル）するためのプログラムを作成することが目的です。

初心者ですので、今は単純に一つ一つの点に対し、
その点を中心とした半径rの球内に他の点が存在するか、しないかという判定をし、
存在する場合は1、存在しない場合は0というように区別し、別々のファイルに出力したいです。

手元にはテキストファイルで
(x,y,z)
(x,y,z)
(x,y,z)
…
と1000行位のデータがあります。
かなりの数なのでメモリーをとる関数なども入れたプログラムを作成しているところですが、
この質問にある判定文のところで悩んでいるので質問に至りました。
質問より補足の方が長なり、申し訳ありません。

回答No.1

magicalpass

何を知りたいのか具体的に記述してください。

　座標の分かっている２点間の距離の求め方なら普通に学校で数学を習っていればわかるはずなので、それをプログラムに利用すればよいだけです。
　プログラムの作り方がわからないのなら、どこが分からないのかを示してください。

【例】
(1)距離の判定方法を知りたい
(2)全体のロジックが組み立てられない
(3)入出力の仕様を確定できない
(4)データのの読み書きが分からない
(5)具体的にコーディング出来ない
(6)GUIの作り方がわからない
　等々

　動作環境も何も提示されていないものを丸投げされても困ります。

補足

説明不足で大変申し訳ありません。
今回質問させていただいた内容は、判定方法に関する記述です。

また、考え直したところ、点と点の距離ではなく、
点を中心とした半径rの球内に、他の点が存在するか、しないか、という判定文を作成したいです。判定後はそれぞれの点を二つの別ファイルに書き出す予定です。

この目的は、3次元空間に無数に存在する点群の数を上記の判定文によって数を減らしたい、というものです。

データはテキストファイルで
(x,y,z)
(x,y,z)
…
というように数千行あります。
そのファイルを読み込み、
行数をカウントし、
配列を作って、その配列にデータを入れる、
というところまでは作成済です。

最後の判定文の所でつまづき、質問に至りました。
不快な思いをさせてしまい、申し訳ありませんでした。