11

私はこれをすべて検索しましたが、これに対する最良のアプローチを見つけることができないようです。約 22000 の緯度/経度ポイントがあり、iPhone の現在の位置に最も近いポイントを見つけたいと考えています。四分木、ダイクストラのアルゴリズム、空間データベースについて質問する人を見てきました。iPhoneに最適なのはどれですか？空間データベースが最も簡単に思えますが、よくわかりません。

編集: 実際には 20,000 ポイント以上あります。それらすべてを反復することがそれを行う方法だと思いますか? しかし、入力していただきありがとうございます。

ありがとう。

4

6 に答える 6

5

実際には、緯度/経度ポイントにHaversine（大円）計算を使用するのが最善です。そうしないと、特にJhericoの回答のように単純な三角関数を使用する場合、距離がますます大きくなるのは間違いです。

クイック検索は、このjavascriptの例を提供します。

var R = 6371; // km Radius of earth
var dLat = (lat2-lat1).toRad();
var dLon = (lon2-lon1).toRad(); 
var a = Math.sin(dLat/2) * Math.sin(dLat/2) +
        Math.cos(lat1.toRad()) * Math.cos(lat2.toRad()) * 
        Math.sin(dLon/2) * Math.sin(dLon/2); 
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
var d = R * c;

データ構造の観点から、Geohashは一見の価値があります。

于 2009-05-27T01:51:23.087 に答える
5

O（N）よりも優れたものが必要な場合は、ある種の空間ハッシュ（四分木、八分木、ハッシュグリッドなど）を構築するために最初にNlgNを支払った場合にのみそれを取得できます。その場合、各テストは約O（lg N）になり、一貫性が高い場合（通常はあります）、最後にチェックした場所をキャッシュすることで、通常ははるかに優れたものになります。

私はおそらくオイラー（天動説、XYZ）空間に八分木を構築します。これにより、緯度/経度の「ゆがんだ」距離ではなく、「真の」距離を取得できるからです。ただし、実際には、緯度/経度空間の四分木はおそらく十分に機能します。ヒットしたら、そのツリーノードを保持し（実行時にツリーが再構築されないと仮定）、次のクエリはそのツリーノードから開始され、より近いノードについてのみ心配する必要があります。前のポイントは前の答えからさらに離れました。

于 2009-05-29T04:09:47.827 に答える
2

iPhone を使用しているので、CoreLoaction を使用して地理的距離を実行できます - CLLocation を使用して– getDistanceFrom:

総当たりの線形検索を使用したくなるかもしれませんが、それが十分に高速でない場合は、GeoHash のようなものに切り替えて、検索用のポイントに対してメタデータを保存します。

于 2009-05-27T09:42:26.273 に答える
1

地球を地域に並べてみませんか? (16 進数を考えてください。) 次に、ポイントをリストに追加するとき、または 1 つの大きな前処理ループで、各ポイントの領域を保存します。

次に、ヘクス X 内のポイント A の近くのポイントを検索する場合、ヘクス X 内のポイントと最大 3 つの隣接するヘクスのみを確認する必要があります。

それでもチェックするポイントが多すぎる場合は、サブリージョンを追加します。

于 2009-05-29T07:01:22.933 に答える
0

ダイクストラを使用するには、グラフ内のノードの位置を知る必要があることを考慮する必要があります。これが、解決しようとしている問題です。あなたはグラフに載っていませんが、あなたに最も近い点を知りたいです

簡単に言えば、Chaos がすでにあなたに言ったように、あなたの位置と 20.000 ポイントすべての間のすべての距離を計算し、それらを並べ替える必要があります。

于 2015-02-19T09:30:17.640 に答える
-3

このアルゴリズムは機能すると思います：

緯度で並べ替えた配列を作成する 経度で並べ替えた配列を作成する

最も近いものを見つけるには、最初に緯度配列でバイナリ検索を実行して、緯度で最も近いものを見つけます。経度配列についても同じことを行います。これで、緯度で最も近いポイントと経度で最も近いポイントの 2 つのポイントができました。ピタゴラスの定理を使用して、各ポイントまでの距離を計算します。最も近いポイントが勝ちます。

ロジャー

于 2009-09-19T21:47:57.903 に答える