点列

質問

平面上にとある点（x座標y座標）をあらかじめ（配列で）入力しておき次のプログラムで一つの点（x,y）を入力しさっき入力した点列の中からその点に一番近い点を表示するプログラムなんです。

わかる人教えてください。考え方（アルゴリズム）やプログラムの文そのままでも教えてくれたら嬉しいです。

回答No.1

Rossana · ベストアンサー

入力する一つの点からの半径rを0からforループでできるだけ小さい刻みで増やしていってその半径内にあらかじめ入力した点があればループ抜けるって感じのアルゴリズムはどうでしょうか？

回答No.3

miswaki777

もっともシンプルなコードを載せておきます。
もう少し、高速に実行したいときは、sqrtをはずしても構いません。
そのときは、distには距離の２乗が代入されることになります。
点の配列が大きくなると、より効率のよいアルゴリズムが必要になってくるかもしれません。
そのときは、#2さんのURLを参考にしてみてください。
参考URLは#2さんのURLからたどってみつけたものです。

void Func(double xInput , double yInput)
{
double dist; //dist := distance
int idxNearest;
double distNearest = DBL_MAX; //double型の最大値
for(int idx = 0 ; idx < sizeof(PointArray1) / sizeof(PointArray) ; idx++)
{
dist = sqrt((PointArray1[idx].x - xInput) * (PointArray1[idx].x - xInput)
+ (PointArray1[idx].y - yInput) * (PointArray1[idx].y - yInput));

if(dist < distNearest){
idxNearest = idx;
distNearest = dist;
}
}
DrawPoint(PointArray1[idxNearest].x , PointArray1[idxNearest].y);//一番近い点を描画する関数を呼び出す。
}

参考URL：

http://grape.c.u-tokyo.ac.jp/~makino/kougi/keisan_tenmongakuII/note10/note10.html

回答No.2

fo-o

どっかで聞いた話だなあって思ったら思い出しました。
C++:language&libraries(cppll)っていうメーリングリストで話題になってました。

http://www.tietew.jp/cppll/archive/5861

この機会に参加してみてはどうですか。一時に比べると最近は静かだけど…