3

大量の 2 次元の点でユークリッド距離によるルックアップを処理するアルゴリズムとデータ構造を開発しています。

Google Scholar でこれを調査しようとしましたが、まだ何も見つかりませんでした (おそらく、この問題が文献で通常何と呼ばれているのかわからないためです)。

これらは、私が検討した2つのアプローチです。

アプローチ 1: バケットを使用して 2 次元グリッドを作成します。ポイントをバケットに挿入し、各ポイントのバケットの参照を保持します。距離 D のポイント P のルックアップで、そのバケット B と、そのグリッド スクエアの角のいずれかが (B までの距離) < D であるすべてのバケットを取得します。最後に、これらすべてのバケット内のポイントを列挙し、P までの距離を計算します。 .

アプローチ 2: 2 つのリストを作成します。各リストには、座標 (x,y) のいずれかですべての点が並べられています。距離 D のポイント P のルックアップで、二分探索を実行してリストのそれぞれで 2 つのポイントを見つけ、ポイントが P < D までのチェビシェフ距離を持つ長方形領域を見つけます。最後に、P までのすべてのポイントのユークリッド距離を計算します。

しかし、最先端のアルゴリズムはこれよりもはるかに優れていると思いますか? これに関するアイデアは大歓迎です

4

1 に答える 1

5

あなたを助けるためのいくつかのヒント：

  • KDTreeを見てください。これは、最近傍を探す最良の方法の 1 つである k 次元ツリー (この場合は 2d) です。
  • おそらく、地理空間データを処理するために特別に開発されたSpatial Databaseの恩恵を受けることができます。
  • 上記のいずれも、目的の距離関数で使用できます。アプリケーションに応じて、マップ距離、大圏距離、一定の傾斜距離、一定の方位距離などが必要になります。距離関数は、ユーザーが知っている必要があります。私は、大円 (haversine) 距離を適用して、Google マップのようなマップとトラックを処理するために使用します。

Python の実装が必要な場合は、scipy.spatial( docs ) があります。このモジュールから、関数query_ball_point((px, py), radius)はあなたが探しているもののようです。

お役に立てれば！

于 2012-11-20T13:35:11.253 に答える