sorting - 緯度と経度の座標の比較

Question

私は15000以上の緯度と経度の座標のリストを持っています。X、Y座標が与えられた場合、リストで最も近い座標を見つけるための最速の方法は何ですか？

score 8 · Accepted Answer

私はこれをWebサイトで1回行いました。つまり、郵便番号から50マイル以内にディーラーを見つけます。大円計算を使用して、北に50マイル、東に50マイル、南に50マイル、西に50マイルの座標を見つけました。それは私に最小と最大の緯度と最小と最大の長さを与えました。そこから、データベースクエリを実行しました。

select *
    from dealers
    where latitude  >= minlat
      and latitude  <= maxlat
      and longitude >= minlong
      and longitude <= maxlong

これらの結果の一部はまだ50マイル以上離れているので、その小さな座標リストでもう一度大円の数式を使用しました。次に、ターゲットからの距離とともにリストを印刷しました。

もちろん、国際日付変更線または極の近くのポイントを検索したい場合は、これは機能しません。ただし、北米内の検索には最適です。

score 6 · Accepted Answer

ボロノイ図と呼ばれる幾何学的構造を使用することをお勧めします。これにより、平面がいくつかの領域に分割されます。各領域に1つずつあり、指定された各点に最も近いすべての点が含まれます。

ボロノイ図を作成し、データ構造のルックアップを配置するための正確なアルゴリズムのコードは大きすぎて、この小さな編集ボックスに収まりません。:)

@Linor：それは基本的にボロノイ図を作成した後に行うことです。ただし、長方形のグリッドを作成する代わりに、ボロノイ図の線に厳密に一致する分割線を選択できます（これにより、分割線と交差する領域が少なくなります）。ボロノイ図を各サブダイアグラムの最適な分割線に沿って再帰的に半分に分割すると、検索する各ポイントのツリー検索を実行できます。これには前もって少し作業が必要ですが、後で時間を節約できます。各ルックアップはlogNのオーダーになります。ここで、Nはポイントの数です。16の比較は15,000よりもはるかに優れています！

score 3 · Accepted Answer

あなたが説明している一般的な概念は最近傍検索であり、これらのタイプのクエリを正確または近似的に解決するためのテクニックがたくさんあります。基本的な考え方は、空間パーティショニング手法を使用して、複雑さをクエリごとに O(n) からクエリごとに (ほぼ) O( log n ) に減らすことです。

KD-Trees および KD-Trees の変種は非常にうまく機能するようですが、quad-trees も機能します。これらの検索の品質は、15,000 個のデータポイントのセットが静的であるかどうかによって異なります (参照セットに大量のデータポイントを追加していません)。Mount と Arya の近似最近傍ライブラリに関する作業は、数学の十分な根拠がなくても、使いやすく理解しやすいものです。また、クエリのタイプと許容範囲にある程度の柔軟性が得られます。

score 2 · Accepted Answer

むしろ、何回実行したいか、および利用可能なリソースによって異なります。テストを 1 回実行する場合は、O(log N) 手法が適しています。サーバー上で何千回も実行している場合は、ビットマップルックアップテーブルを構築する方が高速で、結果を直接または最初の段階として提供できます。2GB のビットマップは、全世界の緯度経度を 0.011 度ピクセル (赤道で 1.2km) の 32 ビット値にマッピングでき、メモリに収まるはずです。1 つの国のみを扱っている場合、または極を除外できる場合は、マップを小さくするか、解像度を高くすることができます。15,000 ポイントの場合、マップはおそらくはるかに小さくなります。緯度経度から郵便番号への検索を行うための最初のステップとして、最初にサイズを大きくしました。これには、より高い解像度が必要です。要件に応じて、マップされた値を使用して結果を直接ポイントします。

score 1 · Accepted Answer

これはいくつかの方法で解決できます。最初に、最も近いポイントを相互に接続するDelaunayネットワークを生成することによってこの問題に取り組みます。これは、オープンソースのGISアプリケーションGRASSのv.delaunayコマンドを使用して実行できます。GRASSの多くのネットワーク分析モジュールの1つを使用して、GRASSで問題を完了することができます。または、無料の空間RDBMSPostGISを使用して距離クエリを実行することもできます。PostGIS空間クエリは、BBOX操作に制限されていないため、MySQLのクエリよりもかなり強力です。例えば：

SELECT network_id, ST_Length(geometry) from spatial_table where ST_Length(geometry) < 10;

経度と緯度を使用しているので、回転楕円体-距離関数を使用することをお勧めします。空間インデックスを使用すると、PostGISは大規模なデータセットに非常に適しています。

score 1 · Accepted Answer

あなたの説明に基づいて、KDツリーやRツリーなどの幾何学的データ構造を使用します。MySQLには、これを行うSPATIALデータ型があります。他の言語/フレームワーク/データベースには、これをサポートするライブラリがあります。基本的に、このようなデータ構造は、長方形のツリーにポイントを埋め込み、半径を使用してツリーを検索します。これは十分に高速であるはずであり、ボロノイ図を作成するよりも簡単だと思います。ボロノイ図の追加のパフォーマンスを好むしきい値があると思います。そうすれば、追加の複雑さを支払う準備が整います。

score 1 · Accepted Answer

最速の意味を指定しませんでした。コードを書かずにすぐに答えを得たい場合は、gpsbabel radius フィルターを試してみてください。

score 0 · Accepted Answer

グリッドは非常にシンプルで、非常に高速です。基本的には、リストの2D配列にすぎません。各配列エントリは、グリッドセル内にあるポイントを表します。グリッドの設定は非常に簡単です。

各ポイントpについて
  pを含むセルを取得します
  そのセルのリストにポイントを追加する

物事を調べるのはとても簡単です：

与えられたクエリポイントp
  pを含むセルを取得します
  クエリポイントpに対して、そのセル（およびその8つの隣接セル）のチェックポイント

アレホ

score 0 · Accepted Answer

答えてくれてありがとう。

@Tom、@Chris Upchurch: 座標は互いにかなり近く、約 800 平方 km の比較的小さな領域にあります。表面が平らであると仮定できると思います。リクエストを何度も処理する必要があり、Web エクスペリエンスを向上させるには、応答が十分に高速である必要があります。

score 0 · Accepted Answer

ボロノイ図を作成したとしても、x、y 座標を作成した 15,000 の領域すべてと比較する必要があります。それを簡単にするために、最初に頭に浮かんだのは、可能な値の上にある種のグリッドを作成することでした。これにより、グリッド内のボックスの 1 つに x/y 座標を簡単に配置できます。エリアのリストを作成したら、比較のために可能な候補をすばやく縮小する必要があります (グリッドがより長方形になるため、エリアが複数のグリッド位置にある可能性があります)。

score 0 · Accepted Answer

時期尚早の最適化は諸悪の根源です。

15K 座標はそれほど多くありません。15K の座標を反復処理して、それが本当にパフォーマンスの問題かどうかを確認してみませんか? 多くの作業を省くことができます。

score 0 · Accepted Answer

これらの座標はどのくらいの範囲に広がっていますか? 彼らはどの緯度にいますか？どのくらいの精度が必要ですか? それらがかなり接近している場合、おそらく地球が丸いという事実を無視して、球面幾何学と大円距離をいじるのではなく、これをデカルト平面として扱うことができます. もちろん、赤道から遠ざかるにつれて、緯度に比べて経度が小さくなるため、何らかのスケーリング係数が適切な場合があります。

かなり単純な距離の式と力ずくの検索から始めて、どれくらいの時間がかかるか、結果が十分に正確かどうかを確認してから、空想にふけってください。

score 0 · Accepted Answer

逆説的に言えば、距離が近いということですか、それとも（運転）時間が近いということですか？都市部では、別の方向に 4 マイル (20 分停車して行く) よりも、高速道路を 5 マイル (5 分) 進んで運転します。

したがって、それが必要な「最も近い」メトリックである場合は、移動時間メトリックを使用して GIS データベースを調べます。

sorting - 緯度と経度の座標の比較

13 に答える 13

Related

Reference