一番近い点を見つけたい。

質問

今　
struct POINT{
double x;//x座標
double y;//y座標
}

struct Model{
POINT point[18000];
}
というふうな　構造体を宣言し、
Model upper;
Model lower;
を　宣言します。

upper.point[0]　から　一番近い点　を　lowerから　みつけたいのですが、lower.point[0]からlower.point[17999]まで　順番に探して　より小さいものがみつかれば　それを　（例えば）m に　代入すると　いった風にしています。しかし　それをupperの点すべてにそれぞれ　一番近いてんをlowerから　探そうと　すると　プログラムが　固まってしまって　うまく　うごきません。　なにか　いいアイデアは　ありませんでしょうか？アルゴリズム　など　なにか　知っている方が　いれば　教えて下さい。

回答No.4

rot-N · ベストアンサー

もし距離を調べるのにsqr((x-a)^2+(y-b)^2)を使っているので有れば、平方根を取らないで2乗のままにしましょう。
ちょっとした間違いがあっても良いのなら、abs(x-a)+abs(y-b)で距離を近似するという手も有ります。

さらに言うと、upper.point[x]、lower.point[n]それぞれにupper.i[x]、lower.i[n]という整数を宣言しておき、距離を計算するときに、まずupper.i[x]、lower.i[n]で距離を計算し、mに近ければあらためてupper.point[x]、lower.point[n]で距離を測定するという手が有ります。
(まず8bitか10bit程度の整数での距離計算で篩い分けします。)

upperの中心の点、lowerの中心の点をModel Uc,Lc;と宣言します。
upper、lowerそれぞれ移動する毎にUc、Lcを計算します。
upper.point[x]とlower.point[n](n=0～17999)の距離を
調べるのに、まずlower.point[n]のx座標がLcのx座標よりupper.point[x]のx座標に近く、次にlower.point[n]のy座標がLcのY座標よりupper.point[x]のy座標に近いものだけ調べることにします。
うまくすれば、計算時間が1/4になるはずです。

回答No.5

Tacosan

「プログラムが固まる」といっても, 動かしている PC の速度もわからなければどのくらいの時間がかかるのかもわからないので比較にはなりませんが....
手元の PC (Pentium3 1GHz) で動かしてみたところ, 全点間の距離を調べるプログラムで実行時間は約2分でした.

回答No.3

JaritenCat

18000程度なら工夫なしでもそんなに時間がかかるとは思えませんが。。。
工夫のしかたとては、例えば座標を3x3の9つのグループに分けて、真ん中のグループじゃないときは、同じグループか隣のグループから探すとか。

とりあえず工夫なしのコード。。。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct POINT{
double x;//x座標
double y;//y座標
};

struct Model{
struct POINT point[18000];
};

struct Model upper;
struct Model lower;

/* 距離を計算 */
double kyori(int i, int j) {
return sqrt((upper.point[i].x-lower.point[j].x)*(upper.point[i].x-lower.point[j].x)
+(upper.point[i].y-lower.point[j].y)*(upper.point[i].y-lower.point[j].y));
}

/* upperから一番近いlowerを探す */
int sagasu(int n) {
int i,res;
double d;
double dd;
res=n; d=kyori(n,n); /* とりあえず1個距離を求めて仮の最小値とする */
for (i=0; i<18000; i++) {
dd = kyori(n,i);
if (d>dd) { res=i; d=dd; }
}
return res;
}

int main(void) {
int i,j;
double d,dd;
int min1,min2;
/* 乱数で座標セット */
for (i=0;i<18000;i++) {
upper.point[i].x = (double)rand();
upper.point[i].y = (double)rand();
lower.point[i].x = (double)rand();
lower.point[i].y = (double)rand();
}
min1=0; min2=sagasu(min1); d=kyori(min1,min2);
/* 各upperに対して探す */
for (i=1;i<18000;i++) {
j=sagasu(i);
dd=kyori(i,j);
printf("%d %d %g\n",i,j,dd);
if (dd<d) { d=dd; min1=i; min2=j;}
}
printf("min: upper=%d lower=%d distance=%g\n",min1,min2,d);

return 0;
}

補足

いえ　ものすごい　時間かかります。最初は　こおったのかと　おもってたんですが、実は　そうではありませんでした。

質問内容を　もう少し詳しく　いうと　

struct POINT{
double x;
double y;
double z;
}
実は POINT は　3次元です。

struct Model upper;
struct Model lower;

と宣言した場合　
upper.point[0]の点と 一番近い点をlower から探す。
upper.point[1]の点と 一番近い点をlower から探す。
upper.point[2]の点と 一番近い点をlower から探す。
upper.point[3]の点と 一番近い点をlower から探す。
upper.point[4]の点と 一番近い点をlower から探す。
　　　　　　　　　　　　.　
　　　　　　　　　　　　.　
　　　　　　　　　　　　.　
　　　　　　　　　　　　.　
　　　　　　　　　　　　.　
upper.point[17998]の点と 一番近い点をlower から探す。
upper.point[17999]の点と 一番近い点をlower から探す。

このような　感じです。
かなり　時間がかかります。単純に考えて　18000×18000　です

どう　工夫すればいいか　教えてください。お願いします。あと　私が　工夫せずに　おこなっていたのは　JaritenCat　と　似たような　内容です。

（あとで　線形探索　だと　わかりました。）

回答No.2

Tacosan

たとえば lower の点を使ってボロノイ分割しておけば, 多分かなり高速になると思います.

回答No.1

keikan

簡単にするために第１象限限定して考えると、

全部の点を調べるのが前提であれば、upperおよびlowerをそれぞれ原点に近い順にソートしておき、
upper[0]をlower[0]から順に距離を調べていきます。
で、探し当てたlower[n]を基準にupper[1]を探していきます。

このときlower[n-１]、lower[n-２]・・・lower[n-i]とlower[n]より近い物がある間、戻って調べ、lower[n-１]よりlower[n]が近ければlower[n＋１]側もより近い物がある間調べていきます。

ソートされていることにより、lowerもupperも、後になればより原点より遠くなっていくので、調べる範囲も絞れるのではないでしょうか？

第１象限に限定しましたが、座標においてオフセットをとってやれば同じ事になると思います。