10

平面上の特定の点に最も近いx個の点を見つけるために、高速なアルゴリズムを見つけたいと思います。

私たちは実際にはあまり多くのポイント（1,000から100,000の間）を扱っていませんが、これらのポイントすべてにx個の最も近いポイントが必要です。（ここで、xは通常5から20の間です。）

C＃で書く必要があります。

ユースケースに関するもう少しコンテキスト：これらのポイントはマップ上の座標です。（これは、平面について正確に話しているわけではないことを意味しますが、投影の問題に対処することは避けたいと思います。）他の多くのポイントが近くにあるエンドポイントでは、あまり多くないポイントは赤で表示する必要があります。それらに近いポイントは緑色で表示されます。これらの2つの極値の間で、ポイントはカラーグラデーション上にあります。

4

4 に答える 4

14

必要なのは、平面内のポイントを整理するのに適したデータ構造です。KDツリーはこのような状況でよく使用されます。ウィキペディアのkdツリーを参照してください。

ここで、幾何学的アルゴリズムの一般的な説明を見つけました

アップデート

KDツリーのJava実装をC＃に移植しました。RoboWikiのUser：Ojd/KD-Treeを参照してください。そこからコードをダウンロードするか、CySoft.Collections.zipを私のホームページから直接ダウンロードできます（ダウンロードのみ、ドキュメントなし）。

于 2012-02-02T14:42:38.367 に答える
11

特定のポイント（すべてではない）について、ポイントの数が極端ではないため、各ポイントからの距離を計算できます。

var points = new List<Point>();
Point source = ...
....
var closestPoints = points.Where(point => point != source).
                           OrderBy(point => NotReallyDistanceButShouldDo(source, point)).
                           Take(20);

private double NotReallyDistanceButShouldDo(Point source, Point target)
{
   return Math.Pow(target.X - source.X, 2) + Math.Pow(target.Y - source.Y, 2);
}

（私はx = 20を使用しました）

計算はdoubleに基づいているので、fpuはここでまともな仕事をすることができるはずです。Pointが構造体ではなくクラスの場合、パフォーマンスが向上する可能性があることに注意してください。

于 2012-02-02T14:20:53.703 に答える
1

これをより効率的にするため。距離がkだとしましょう。xkとx+kの間のx座標を持つすべての点を取ります。同様に、ykとy+kを取ります。したがって、余分な座標をすべて削除しました。ここで、距離を（x-x1）^ 2 +（y-y1）^2にします。それらにk個の要素の最小ヒープを作成し、新しいポイント<min（heap）の場合はそれらをヒープに追加します。これで、ヒープにk個の最小要素があります。

于 2012-02-02T14:29:05.840 に答える
1

距離関数を作成してから、すべてのポイントの距離を計算して結果を並べ替え、最初のxを取得する必要があります。

結果が100％正確でなければならない場合は、標準の距離関数を使用できます。

d = SQRT（（x2-x1）^ 2 +（y2-y1）^ 2）

于 2012-02-02T14:21:53.830 に答える