2点間の最短距離について

[おかべー]

こんにちは。
いつもお世話になっております。
現在、円の内部と円周上の各点の座標が格納されている2つの配列から、円内部の各点から最も近い円周上の点を調べるプログラムを作成しています。
一応作成してみて実行したのですが、うまくいってないような結果が得られました。以下に作成したアルゴリズムを示します。

コード:

for(i=0;i<4310;i++)
	{
		min=100.0;
		for(j=0;j<1206;j++)
		{
			t=sqrt(pow(outcoord[j][0]-cen_grav[i][0],2)
				+pow(outcoord[j][1]-cen_grav[i][1],2));
			
			if(t<min)
			{
				min=t;
			}
			
		}
		dis[i]=min;
		fprintf(fpw,"%d %f\n",i+1,dis[i]);
	}

円周上にある点（1206点）はoutcoordという2次元配列に格納してあり、outcoord[1206][x]、outcoord[1206][y]のようにx座標とy座標の成分を持たせています。
また、cen_gravという配列は円内部の各点（4310点）の座標が格納されている配列であり、outcoordと同様x成分y成分を持たせています。

要するに、円内部の各点と円周上の各点の間の最短距離を求めたいと考えています。
このアルゴリズムにおかしいところ等ないか調べてみたのですが見つけられず困っています。
どなたかご指摘いただけると、あるいは他のアルゴリズムを教えていただけると助かります。

よろしくお願いします。

[can110]

ロジックは問題ないように見えますが、t, min disなどの型が
intなどだと誤差が発生するため、正しい結果は得られないでしょう。

型に問題がない場合、具体的におかしなケースはあげられますか？

>あるいは他のアルゴリズムを教えていただけると助かります。

「円の中心と内部の点を結ぶ線分」と「円の中心と円周上の点を結ぶ線分」のなす角度が最小の点が最短距離になるかと思います。
つまり、もし円の中心がわかるのなら、角度の差だけを見ればよくなります。

さらに、円周上の各点は等間隔に並んでいる
つまり、outcordの添え字位置だけから円周上の座標が決定できるなら
Nを円周の分割数（1026など）とすると
-Pi *(n / N) < atan2( 内部の点 - 円の中心) < Pi * ((n+1) / N)
である円周上の連続する２点outcord[n], outcord[n+1]は計算で求めることができるので
あとは、その角度の小さいほうが最短距離の点となります。

[deny]

あくまで距離を計算して最小値を求めるならば以下のように書けるでしょうか。
ただしC++11を用いておりますが…
(スマホからなので誤植等あればすみません)

コード:

class Coordinate {
public:
    Coordinate(float x_, float y_) : x(x_), y(y_) { }

    float magnitude2() const {
        return x * x + y * y;
    }

    Coordinate operator-(const Coordinate& rhs) const {
        return Coordinate(x - rhs.x, y - rhs.y);
    }

private:
    float x;
    float y;
}

std::vector<Coordinate> cen_grav, outcoord;

//...

for (size_t i = 0, size = cen_grav.size(); i < size; ++i) {
    for (const auto& oc : outcoord) {
        auto distance = (oc - cen_grav[i]).magnitude2();
        if (distance < min * min) {
            min = std::sqrt(distance);
        }
    }
    dis[i] = min;
}

[おかべー]

can110さん

ありがとうございます。
変数は全てdouble型ですので、誤差の可能性は低いと思われます。

このアルゴリズムで得られた円周上からの各内部点の最短距離を、autoGLというものを使って色の濃淡（濃：距離が小さい、薄：距離が大きい）で可視化してみました。
その結果、本来なら同心円のように円の中心から外側に行くにつれグラデーションがかかるはずなのですが、得られた結果はほんの一部だけグラデーションがかかり、後はぐちゃぐちゃというものでした。

これがおかしなケースです。

アルゴリズムを示してくれてありがとうございます。
ちなみに、円の中心は原点（0,0）です。

[おかべー]

denyさん

ありがとうございます。
せっかく教えて下さり嬉しいのですが、当方C言語の学習を始めたばかりですので、C++に関してはあまり分からないのですが、そのアルゴリズムはCでも実装できるものなのでしょうか？
くだらない質問で申し訳ありません。

[deny]

そのアルゴリズムはCでも実装できるものなのでしょうか？

というかあの、すみません、アルゴリズムはおかべーさんのものとほぼ同じです…
投稿してからしまったと思いましたorz
唯一の違いは、値の比較の仕方に関して、距離と最小値を比較するのではなく、距離の二乗(=二乗根の計算を行わない)と最小値の二乗を比較していることだけです。
申し訳ないです。

[みけCAT]

約4000×約1000を浮動小数点数の演算を用いて全探索したら遅そうですね。
円の中心から、x軸の正の方向に向く半直線と各点の方向に向く半直線のなす角でソートし、角度が近いものだけと比較するなど、工夫が必要かもしれません。

[みけCAT]

このアルゴリズムにおかしいところ等ないか調べてみたのですが見つけられず困っています。

minの初期値を100と決め打ちしてしまうと、全ての点との距離が100を超えている場合に誤動作します。
minの初期値は最初の点との距離などにするべきです。

コード:

for(i=0;i<4310;i++)
	{
		min=0.0;
		for(j=0;j<1206;j++)
		{
			t=sqrt(pow(outcoord[j][0]-cen_grav[i][0],2)
				+pow(outcoord[j][1]-cen_grav[i][1],2));
			
			if(j == 0 || t<min) /* 最初の点との距離は必ず代入されるようにする */
			{
				min=t;
			}
			
		}
		dis[i]=min;
		fprintf(fpw,"%d %f\n",i+1,dis[i]);
	}