緯度と経度の座標の比較
https://stackoverflow.com/questions/35870
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
15,000 を超える緯度と経度の座標のリストがあります。X、Y 座標が与えられた場合、リスト上で最も近い座標を見つける最も速い方法は何ですか?
解決
と呼ばれる幾何学的構造を使用するとよいでしょう。 ボロノイ図. 。これにより、平面が、指定した各点に最も近いすべての点を含む複数の領域 (点ごとに 1 つ) に分割されます。
ボロノイ図を作成し、データ構造のルックアップを調整するための正確なアルゴリズムのコードは、この小さな編集ボックスに収まるには大きすぎます。:)
@リノール:これは基本的に、ボロノイ図を作成した後に行うことです。ただし、長方形のグリッドを作成する代わりに、ボロノイ図の線に厳密に一致する分割線を選択できます (これにより、分割線と交差する領域が少なくなります)。各サブダイアグラムの最適な分割線に沿ってボロノイ図を再帰的に半分に分割すると、調べたい各点に対してツリー検索を行うことができます。これには事前に少しの作業が必要ですが、後で時間を節約できます。各ルックアップは log N のオーダーになります。ここで、N はポイントの数です。16 件の比較は 15,000 件よりもはるかに優れています。
他のヒント
Web サイトでこれを一度実行しました。つまり、郵便番号から 80 マイル以内のディーラーを見つけてください。私が使用したのは、 大圏計算 北 80 マイル、東 50 マイル、南 50 マイル、西 50 マイルの座標を見つけます。これにより、緯度の最小値と最大値、経度の最小値と最大値が得られました。そこからデータベース クエリを実行しました。
select *
from dealers
where latitude >= minlat
and latitude <= maxlat
and longitude >= minlong
and longitude <= maxlong
これらの結果の一部はまだ 80 マイル以上離れているため、次の方法を使用しました。 大圏の公式 もう一度、その小さな座標リストに戻ってみましょう。次に、ターゲットからの距離とともにリストを印刷しました。
もちろん、日付変更線や極点の近くのポイントを検索したい場合は、これは機能しません。ただし、北米内の検索には最適です。
あなたが説明している一般的な概念は次のとおりです 最近傍検索, そして、この種のクエリを正確にまたは近似的に解決するテクニックはたくさんあります。基本的な考え方は、空間分割手法を使用して、クエリあたりの複雑さを O(n) からクエリあたり (およそ) O( log n ) に軽減することです。
KD ツリーおよび KD ツリーのバリアントは非常にうまく動作するようですが、クワッド ツリーも動作します。これらの検索の品質は、15,000 データ ポイントのセットが静的かどうか (参照セットに大量のデータ ポイントを追加していないかどうか) によって決まります。マウントとアリアの取り組み おおよその最近傍 このライブラリは、数学の基礎が十分でなくても、使いやすく、理解しやすいものです。また、クエリの種類と許容範囲にある程度の柔軟性が与えられます。
むしろ、それを何回行うか、そしてどのようなリソースが利用できるかによって決まります。テストを 1 回だけ行うのであれば、O(log N) 手法が適しています。サーバー上でこれを 1,000 回実行する場合は、ビットマップ ルックアップ テーブルを構築した方が、結果を直接与えるか、最初の段階として結果を与える方が高速になります。2 GB のビットマップは、全世界の緯度経度を 0.011 度ピクセル (赤道で 1.2 km) の 32 ビット値にマッピングでき、メモリに収まるはずです。単一の国のみを対象とする場合、または極を除外できる場合は、マップを小さくしたり、解像度を高くしたりできます。15,000 ポイントの場合は、おそらくはるかに小さい地図になります。緯度経度から郵便番号までの検索を行うための最初のステップとして、まず地図のサイズを大きくしました。これにはより高い解像度が必要です。要件に応じて、マップされた値を使用して結果を直接指定するか、候補のリストを絞り込みます (これによりマップは小さくなりますが、後続の処理がより多く必要になります。O(1) ルックアップ領域にはもう入っていません) ）。
最速というのが何を意味するのかは明記されていませんでした。コードを書かずにすぐに答えを知りたい場合は、次のようにします。 gpsbabel 半径フィルター 前。
あなたの説明に基づいて、KD ツリーや R ツリーなどの幾何学的データ構造を使用します。MySQL にはこれを行う SPATIAL データ型があります。他の言語/フレームワーク/データベースには、これをサポートするライブラリがあります。基本的に、このようなデータ構造は長方形のツリーにポイントを埋め込み、半径を使用してツリーを検索します。これは十分に高速であるはずであり、ボロノイ図を作成するよりも簡単だと思います。おそらく、ボロノイ図の追加パフォーマンスを優先するためのしきい値があり、追加の複雑さを支払う準備ができていると思います。
これはいくつかの方法で解決できます。私はまず、 ドロネー 最も近い点を相互に接続するネットワーク。これは、オープン ソース GIS アプリケーションの v.delaunay コマンドを使用して実現できます。 草. 。GRASS で問題を解決するには、数多くの方法のうちの 1 つを使用します。 ネットワーク分析モジュール グラスで。あるいは、無料の空間 RDBMS を使用することもできます。 ポストGIS 距離のクエリを実行します。PostGIS 空間クエリは、BBOX 操作に制約されないため、MySQL の空間クエリよりも大幅に強力です。例えば：
SELECT network_id, ST_Length(geometry) from spatial_table where ST_Length(geometry) < 10;
経度と緯度を使用しているため、おそらく 回転楕円体距離関数. 。空間インデックスを使用すると、PostGIS は大規模なデータセットに対して非常に適切に拡張できます。
ボロノイ図を作成したとしても、作成した 15,000 個の領域すべてと X、Y 座標を比較する必要があることを意味します。それを簡単にするために、最初に頭に浮かんだのは、可能な値の上にある種のグリッドを作成して、グリッド内のボックスの 1 つに X/Y 座標を簡単に配置できるようにすることでした。エリアのリストを完了したら、比較の候補をすぐに縮小する必要があります (グリッドがより長方形になるため、エリアが複数のグリッド位置に存在する可能性があります)。
15K 座標はそれほど多くありません。15K の座標を反復処理して、それが本当にパフォーマンス上の問題であるかどうかを確認してみてはいかがでしょうか。多くの作業を節約でき、おそらく、作業が遅すぎて気付かないほどになることはありません。
これらの座標はどれくらいの面積に広がっていますか?彼らはどの緯度にいますか?どれくらいの精度が必要ですか?それらが互いにかなり近い場合は、おそらく地球が丸いという事実を無視して、球面の幾何学や大圏の距離をいじるのではなく、単にこれをデカルト平面として扱うことができます。もちろん、赤道から遠ざかるにつれて経度は緯度に比べて小さくなるため、ある種の倍率が適切な場合があります。
かなり単純な距離の計算式と総当たり検索から始めて、それにどれくらいの時間がかかるか、結果が十分に正確かどうかを確認してから、本格的に始めてください。
皆さん、ご回答ありがとうございました。
@トム、@クリス・アップチャーチ:座標は互いにかなり近く、約 800 平方キロメートルの比較的小さなエリア内にあります。表面は平らだと考えていいと思います。リクエストを何度も処理する必要があるため、より多くの Web エクスペリエンスを得るには、応答が十分に高速である必要があります。
グリッドは非常にシンプルで、非常に高速です。これは基本的に単なるリストの 2D 配列です。配列の各エントリは、グリッド セル内にある点を表します。グリッドのセットアップは非常に簡単です。
for each point p get cell that contains p add point to that cell's list
調べるのもとても簡単です。
given a query point p get cell that contains p check points in that cell (and its 8 neighbors), against query point p
アレホ
逆に言えば、距離や（運転）時間が近いということですか？都市部では、別の方向に 4 マイル (ストップアンドゴー 20 分) するよりも、高速道路で 5 マイル (5 分) 運転するほうがいいと思います。
したがって、それが必要な「最も近い」指標である場合は、移動時間の指標を含む GIS データベースを調べることになります。
