緯度、経度の比較

Question

私には15000以上の緯度と経度座標のリストがあります。任意のX、Y座標を指定すると、リスト上で最も近い座標を見つける最速の方法は何ですか？

Answer 1

Voronoi diagramと呼ばれる幾何学的構成を使用すると便利です。これは、各点に1つずつ、各点に最も近いすべての点を含むいくつかの領域に平面を分割します。

Voronoiダイアグラムを作成してデータ構造のルックアップを配置するための正確なアルゴリズムのコードは、この小さな編集ボックスに収まらないほど大きすぎます。 :)

@Linor：これは基本的に、ボロノイ図を作成した後に行うことです。しかし、長方形のグリッドを作るのではなく、ボロノイ図の線によく似た線分を選ぶことができます（この方法で分割線を横切る領域が少なくなります）。各サブダイアグラムの分割線分に沿ってボロノイ図を半分に再帰的に分割すると、ルックアップする各点についてツリー検索を行うことができます。これは少し前の作業を必要とするが、後で時間を節約する。各ルックアップはlogNの順番であり、Nはポイントの数である。 16の比較は15,000よりずっと優れています！

Answer 2

ボロノイ図を作成しても、x座標とy座標を15000個の作成領域すべてと比較する必要があります。これを簡単にするために、最初に私の心に浮かんだのは、可能な値にいくつかの種類のグリッドを作成して、グリッド内のボックスの1つに簡単に配置してx/y座標を設定できるようにすることでした（グリッドがより長方形になるので、エリアが複数のグリッド位置にある可能性があるため）候補の候補をすばやく縮小する必要があります。

Answer 3

説明している一般的な概念はnearest-neighbour searchであり、これらのタイプの問題を正確にまたはほぼ解決する技術があります。基本的な考え方は、空間分割技法を使用して、クエリごとのO（n）からクエリあたりの（ほぼ）O（log n）までの複雑さを軽減することです。

KDツリーとKDツリーのバリアントは非常にうまくいくようですが、クワッドツリーも機能します。これらの検索の品質は、15,000データポイントのセットが静的であるかどうか（参照セットに多くのデータポイントを追加しない場合）によって異なります。 Approximate Nearest NeighbourライブラリでのMountとAryaの作業は、数学での適切なアースがなくても、使いやすく理解しやすいものです。また、クエリの種類と許容範囲に柔軟性をもたせています。

Answer 4

Premature optimization is the root of all evil.

15K座標はそれほどではありません。 15Kの座標を繰り返し処理して、それが実際にパフォーマンス上の問題であるかどうかを確認してください。あなたは多くの仕事を節約することができますし、気づいても遅すぎることはありません。

Answer 5

あなたが最速のものを指定していません。コードを書くことなく迅速に回答を得たい場合は、gpsbabel radius filterを行ってください。

Answer 6

これは、何回何回実行したいか、どのリソースが利用できるかによって異なります。テストを1回実行すると、O（ログN）技法が有効になります。サーバー上で何千回も実行している場合、ビットマップルックアップテーブルを構築する方が、結果を直接または最初の段階として与える方が高速になります。 2GBのビットマップは、世界全体のlat-lonを0.011度ピクセル（赤道で1.2km）の32bit値にマップすることができ、メモリに収まる必要があります。あなたが単一の国だけを行っている場合、または極を除外できる場合は、マップを小さくするか、解像度を上げることができます。 15,000ポイントの地図はもっと小さいかもしれません。最初は、緯度経度から郵便番号の検索までの最初のステップとしてサイズを大きくしました。これには高解像度が必要です。要件に応じて、マッピングされた値を使用して結果を直接指し示すか、または候補リストの短いリスト（マップを小さくすることができますが、後続の処理がより多く必要になります）、O（1）ルックアップ領域には）。

Answer 7

ウェブサイトでこれを1回行いました。私。あなたの郵便番号の50マイル以内にディーラーを見つける。私はgreat circle calculationを使って北50マイル、東50マイル、南50マイル、西50マイルの座標を見つけました。それは私に最小と最大の緯度と最小と最大の長さを与えました。そこから私は、データベースのクエリをした：

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

それらの結果のいくつかは、まだ50以上のマイル離れなりますので、それから私は、座標の小さなリストにもう一度great circle formulaを使用しました。それから、ターゲットからの距離とともにリストを印刷しました。もちろん

、あなたは国際日付変更線や極近いポイントを検索したい場合は、この方法ではうまくいきません以上。しかし、北米内の検索には効果的です！

Answer 8

これらの座標はどのくらい広い範囲に広がっていますか？彼らはどんな緯度ですか？どのくらいの精度が必要ですか？彼らがかなり接近しているならば、地球が丸いという事実を無視して、これを球状のジオメトリと大きな円の距離でぶち壊すのではなく、デカルト平面として扱うだけです。もちろん、あなたが赤道から遠ざかるにつれて、緯度の度合いは緯度の度合いに比べて小さくなりますので、何らかの種類の倍率が適切かもしれません。

かなり単純な距離の式と力まかせ探索で始まり、それが取るために起こっているどのくらい見ると結果はあなたが空想を取得する前に十分に正確である場合。

Answer 9

回答ありがとうございました。

@Tom、@クリスアップチャーチ：座標は、お互いにかなり接近している、と彼らは約800平方キロの比較的小さな領域です。私は表面が平坦であると仮定できると思う。私は何度もリクエストを処理する必要があり、レスポンスはより多くのWebエクスペリエンスのために十分速くなければなりません。

Answer 10

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

Answer 11

グリッドは非常に簡単で、非常に高速です。基本的には、リストの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 

アレホ

Answer 12

これは、いくつかの方法で解決することができます。私はまず、最も近い点を互いに接続しているネットワークを生成することによってこの問題にアプローチします。これは、オープンソースGISアプリケーションGRASSのv.delaunayコマンドで実行できます。あなたはGRASSの多くのnetwork analysis modulesの1つを使ってGRASSの問題を完成させることができます。また、空き空間RDBMS PostGISを使用して遠隔照会を行うこともできます。PostGIS空間クエリは、BBOX操作に制約されないため、MySQLのものよりもかなり強力です。たとえば：

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

あなたは経度と緯度を使用しているので、おそらくSpheroid-Distance functions使用したいです。空間インデックスを使用すると、PostGISは大きなデータセットに対して非常によくスケーリングされます。

Answer 13

ちょうどcontrairianになるには、遠くに（運転）時間が近いのですか？都市部では、高速道路で5マイル（5分）を4マイル（20分停止して行く）よりも別の方向に運転しています。

したがって、必要な「最も近い」メトリックであれば、旅行時間の指標を使ってGISデータベースを調べます。