2

+10k ポイント (緯度、経度) があり、ユーザーの場所に最も近い k ポイントを表示するアプリを作成しています。

これは非常に一般的な問題であり、車輪の再発明はしたくありません。四分木について学んでいます。この空間的な問題を解決するための良いアプローチのようです。

私はこれらのツールを使用しています：

  • パイソン2.5
  • MySQL
  • MongoDB

Quadtreeの構築はそれほど難しくありません。クエリ？

次のようなクエリを実行する必要があります。

  1. ユーザーの位置から 10 km 以内のすべてのポイントを検索します。
  2. ユーザーの位置に最も近い 6 つ (または少なくとも 6 つ) のポイントを見つけます。

それを行うための標準的で一般的なアプローチは何ですか?

編集1：

+10k ポイントを MongoDB (地理空間インデックス作成) にロードしましたが、一見すると問題なく動作します。とにかく私はPostGisを見つけました:

PostGIS は、GIS (地理情報システム) オブジェクトをデータベースに格納できるようにする PostgreSQL オブジェクト リレーショナル データベース システムの拡張機能です。

そこで、PostGis を試してみようと思います。

SimpleGeoも見つけました。ポイント/場所をクラウドに保存し、API を介してクエリを実行できます: https://simplegeo.com/docs/tutorials/python#how-do-radial-nearby-query

4

3 に答える 3

6

MongoDBは組み込みの空間インデックスをサポートしているため、必要なのは、正しい形式を使用してポイントをロードし、空間インデックスを作成してから、クエリを実行することだけです。

簡単な例として、mongoシェルの50州すべての中心点をロードしました。

> db.places.ensureIndex({loc: "2d"})
> db.places.save({name: "AK", loc: {long: -152.2683, lat: 61.3850}})
> db.places.save({name: "AL", loc: {long: -86.8073, lat: 32.7990}})
> db.places.save({name: "AR", loc: {long: -92.3809, lat: 34.9513}})
> db.places.save({name: "AS", loc: {long: -170.7197, lat: 14.2417}})
> ...

次に、指定された場所に最も近い6つのポイントをクエリします。

> db.places.find({loc: { $near: {long: -90, lat: 50}}}).limit(6)
{"name" : "WI", "loc" : { "long" : -89.6385, "lat" : 44.2563 } }
{"name" : "MN", "loc" : { "long" : -93.9196, "lat" : 45.7326 } }
{"name" : "MI", "loc" : { "long" : -84.5603, "lat" : 43.3504 } }
{"name" : "IA", "loc" : { "long" : -93.214, "lat" : 42.0046 } }
{"name" : "IL", "loc" : { "long" : -89.0022, "lat" : 40.3363 } }
{"name" : "ND", "loc" : { "long" : -99.793, "lat" : 47.5362 } }

次に、指定された場所から10km以内のすべてのポイントをクエリします。最も近い州を計算しているので、888km（緯度は約8度）を使用します。

> db.places.find({loc: { $near: {long: -90, lat: 50}, $maxDistance: 8}})
{"name" : "WI", "loc" : { "long" : -89.6385, "lat" : 44.2563 } }
{"name" : "MN", "loc" : { "long" : -93.9196, "lat" : 45.7326 } }

1度の緯度は約111.12kmであるため、アプリケーションではaを使用し$maxDistance: 0.08999て10kmを表します。

更新デフォルトでは、MongoDBは「理想的な地球平面説」を想定していますが、経度線が極に収束するため、これにより不正確になります。 MongoDBバージョン1.7以降では、球面距離の計算がサポートされており、精度が向上しています。

これは、球面距離を使用して上記のクエリを実行する例です。これmaxDistanceはラジアンであるため、地球の平均半径で割る必要があります。

> db.runCommand({geoNear: "places", near: [-90, 50], spherical: true, 
                 maxDistance: 800/6378});
(summarizing results as they're too verbose to include)
"MN"  dis: 0.087..
"WI"  dis: 0.100..
"ND"  dis: 0.120..
于 2011-05-17T05:34:28.167 に答える
2

ウィキペディアのkdtreeエントリを参照してください。これは、(四分木とは異なり) 3 つ以上の次元がある場合にも役立ちます。エントリにはツリーを作成してクエリするための Python コードがあるため、kd-tree をお勧めします。

于 2011-05-17T04:18:38.790 に答える
1

MongoDB を使用する場合は、MongoDBのドキュメントを注意深く読んでください。デフォルトのモデルは平らな地球です。経度は緯度と同じ長さであると仮定しています。

引用: """現在の実装では、平らな地球の理想化されたモデルを想定しています。つまり、緯度 (y) と経度 (x) の弧度はどこでも同じ距離を表します。これは、両方がほぼ同じである赤道でのみ当てはまります。 69 マイルまたは 111 km に相当します. ただし、{ x : -74 , y : 40.74 } にある 10gen のオフィスでは、経度の 1 弧度は約 52 マイルまたは 83 km です (緯度は変更されません). これは、北に 1 マイルの何かを意味します1マイル東に何かよりも近くに見えるだろう."""

彼らの「新しい球面モデル」が必要です。注意してください: (経度、緯度) をこの順序で使用する必要があります。繰り返しますが、ドキュメントを注意深く読んでください。

于 2011-05-19T03:32:35.247 に答える