0

私は地図アプリケーションを作っています。私はたくさんの場所の座標を持っています。画面に表示されている領域内のすべてのポイントを返したい。これは、Google マップ API を使用して行います。画面に表示されている地図の北東と南西の座標が表示されます。MongoDb を使用しています。

明らかな方法は、ne-sw 対角線の中点を中心とし、いずれかの角からの距離を半径とし、その半径内のすべての点を見つけることです。

しかし、それらを単一のリストに格納するのは O(n) 操作になり、すべてのリクエストに対してスケーラブルではありません。ポイントをすぐに獲得できるように保管するには、どのような方法がよいでしょうか?

radius(r) 内のすべてのポイントを含むバケットに分割し、代わりにソートされたバケットのリストを維持することを考えています。画面は最大で 4 つのバケット (個別のバケットのすべてのコーナー) に配置できるため、O(log n) で最も近いバケットを見つけ、O(1) で次の 3 つの最も近いバケットを見つけます。ここで、これら 4 つのバケットに対してのみ計算を行う必要があります。

しかし、それはまだたくさんのバケツです! Google は、マップ上のポイントを非常に迅速にレンダリングできます。そして、彼らはたくさんのポイントを持っています。そしてたくさんのユーザー。彼らはそれをどのように管理していますか？そのレベルの最適化に達するとは思っていませんが、より良いデータ構造が必要です。

4

1 に答える 1

0

わからないかも…。あなたのソリューションはかなり複雑に聞こえます..

画面のコーナーがあります-NE Long と Lat および SW Long と Lat したがって、SW_Lat、SW_long、NE_lat、SW_Lat があります。

この境界内のポイントを選択したい...経度と緯度を10進数として保存している場合は、次の疑似コードを使用します:

Select * from points 
where point_lat > SW_lat 
and point_lat < NE_lat
and point_long > SW_long
and point_long < NE_long

これにより、表示されている画面がいっぱいになります。

于 2013-07-25T15:18:47.170 に答える