「私の周り」のジオロケーションを取得するための「メモリ内」データ構造

Question

対象のポイントを探すメソッド（クラス）を作成する必要があります。 は所定の距離内にあります。このような

何か：

Collection <Position> getAroundMe(Position myPosition, int distInMeters); 

方法は（ないDB） "メモリー・データの" 使用する必要があります。

位置クラスがある：

Position { 
    double latitude; 
    double longitude; 
} 

Iは、関心のあるポイントを格納するTreeSetのを使用していたが、私は、2つ（緯度と経度）フィールドの比較を定義することができませんでした。

あなたのアドバイスをしてください。

コメント：「メモリ内のデータ」はめったに更新されず、1分に約 のgetArroundMeメソッドが1000回呼び出されます（現在はDBで動作します）。

Answer 1

おそらくオプションではないので、位置が変更されたときにマップを常に更新する必要があります。

アプローチ1

単純なアプローチは、経度と緯度によってソート二つのリストを維持するかもしれません。あなたの現在の位置までの距離xとポジションを取得するときは、次の操作を行うことができます：

• 間隔current.longitude +/- xを取得し、経度の一覧で、例えばその間隔を調べますバイナリ検索を使用します。
• 緯度を同じにします。
• 両方の間隔に存在する位置のみを保持します。
• 現在の位置までの距離に基づいて位置を並べ替えます。
• バイナリ検索を使用して、距離がxより大きいすべての位置を検索して削除します。

アプローチ2

別の、より複雑なアプローチは、すべての位置が含まれている矩形領域を定義するクワッドツリーである同じサイズの4つの小さな長方形にそれを分割、細分化を続けるかもしれません合理的なレベルに達するまで（あなたが指数関数的な成長をするほど深くはない）、それぞれの葉の四角にポジションを割り当てます。

次に、辺の長さがxの正方形のボックスでどの葉の四角形がタッチされているのかを確認し、トップダウンをチェックして現在の位置に中心を置きます。 の位置のリストがあなたの位置の周りに直径xの円の中にあるので、それらをチェックして、結果からより遠くにあるものをすべて削除する必要があります。

アプローチ3

あなたが試みることができるもう一つの選択肢は、（例えば、ここで参照：http://www.gicentre.net/utils/hashgrid/）は、いわゆるハッシュグリッドです。基本的に、（粗い）位置に基づいてハッシュ関数を定義します。つまり、位置をいくつかの「セルサイズ」に切り捨てて、そのより低い精度の位置のハッシュ値を計算します。あなたは、同じハッシュを持つ近くの位置で終わるので、同じ仮想セルにいます。セルのように多くのバケットを使用したくないので、ハッシュ値はおそらく最終的に折り返され、お互いに近くない各バケットのセルのリストになります。

位置を確認するときに、現在の位置の周りの円が触れているセルを最初に計算してから、それらをハッシュマップで検索します。その後、前と同じようにそれらのセルの位置をチェックします。