algorithm - バウンディングボックスよりも優れたものはありますか？

Question

経度の緯度がx百万ポイントあるシナリオがあります。

新しいlong/latポイントが追加されたときに、ユーザーが構成した距離パラメーター内にある他のポイントを効率的に知りたいので、それらをリストに追加できます。

バウンディングボックスよりも優れたものはありますか？

アルゴリズム、リファレンス、いくつかの実装を見てみたいです;）ありがとうございます！

Answer 1

より良いオプションがかなりありますが、主にスペースの分割に基づいています。

一般的で、多くの場合非常に優れたオプション（実装するのはそれほど難しくありません）は、KDツリーを使用することです。 四分木は実装が簡単ですが、検索には時間がかかります。データの分散と要件によっては、他のスペース分割アルゴリズムのパフォーマンスが向上したり、メモリ要件が低くなったり、その他の関連する問題が発生したりする場合があります。

Answer 2

同僚は、モートンコードをGISデータの空間インデックスとして使用した経験が豊富であると私に話しました。おそらくそれは調査する価値のあることです。

Answer 3

この手っ取り早いアプローチは、あなたにいくらかの悲しみを救うかもしれません：地球の表面を1度の箱に分けてください。次に、180x360の要素配列が作成され、新しいポイントを含むボックスと、そのすぐ周囲のコーナーの1つがユーザー指定の距離内にあるすべてのボックスを含む、少数のボックスを検索するだけで済みます。すべてを考慮せずに、使用するボックスをすばやく把握するために使用できるトリックがいくつかあることがわかります。緯度と経度のラップアラウンドを忘れないでください。

あなたの「唯一の」が数百万のポイントを持っていて、それらがホットスポットにクラスター化されていない場合、それはあなたを通り抜ける可能性があります。

理論的に優れた方法：各ポイントを3次元空間にマッピングし、それらを八分木に保存すると、任意の距離内にある近くのポイントをすばやく見つけることができます。もちろん、3次元空間での距離は、地球上の大円距離とはわずかに異なるため、変換係数を計算する必要があります。ただし、これは単純なはずです。実装言語については言及していませんが、使用している言語に対して十分にテストされたoctree実装があることはほぼ間違いありません。サードパーティのコードを挿入してもかまわない場合は、このソリューションが次の方法です。行く。