6

私は、緯度/経度のポイントを取得し、既知の場所のリストで最も近い上位 5 つのポイントを見つけることを含む学校のプロジェクトに取り組んでいます。リストはメモリに保存されますが、「適切なデータ構造」を選択する必要があることに注意してください。つまり、単純にすべての場所を配列に保存して、距離を 1 つずつ直線的に比較することはできません。教師は、明らかに遠すぎる場所の距離を計算しないように、場所のデータを米国の州ごとにグループ化することを提案しました。もっとうまくやれると思う。

私のオンライン調査によると、R ツリーまたはそのバリアントの 1 つが適切な解決策になるようです。残念ながら、その文は、実際のテクニックを理解した上で得た限りのものです。学術的ではない私の頭には文献があまりにも濃すぎるからです.

  • Rツリーに緯度/経度データを入力し、ツリーをトラバースして特定のポイントの5つの最近傍を見つけるプロセスが何であるかについて、誰かが本当に高い概要を教えてくれますか?

  • さらに、このプロジェクトは C で作成されており、これについて一からやり直す必要はありません。そのため、R ツリーの既存のオープン ソース C 実装を使用したことがある場合は、その経験に興味があります。

更新: このブログ投稿では、地域的に分割された空間 (PR 四分木など) の簡単な検索アルゴリズムについて説明しています。将来の読者に役立つことを願っています。

4

2 に答える 2

7

別のデータ構造を検討しましたか? R ツリーの代わりに、Point Quadtree の方がニーズにより効果的であると思います。Spatial Index Demosは、R-tree や Point Quadtree を含む可能なデータ構造のリストのいくつかのデモを提供します。それが洞察を与えることを願っています。

于 2010-05-07T08:29:24.260 に答える
5

四分木

四分木はスペースの正方形を取り、X軸とY軸に沿って半分の寸法を持つ4つの子に分割します。

+---+---+
|   |   |  Each square is a child
|   |   |  of the parent; when you
+---+---+  get to leaves a node has
|   |   |  a single point or a list
|   |   |  of points.
+---+---+

このデータ構造は再帰的であり、リーフに到達するまでどの子がポイントを保持しているかを確認することでポイントを検索します。リーフには、実装に応じて、単一のメンバー（X、Y座標を持つポイント）またはメンバーのリストがあります。ノードを埋める場合は、ノードを4つに分割し、子を分散します。基本的に、データ構造は二分木の一般化であるため、必ずしもバランスが取れているとは限りません。

クワッドツリーのバランスをとる必要はないかもしれませんが、読者の練習問題として残されています。ウェブで「バランスの取れたクワッドツリー」を検索してみてください。

このデータ構造では、重複する可能性のあるアイテムにインデックスを付けることはできませんが、ポイントのみを格納している場合は問題になりません。

四分木で最も近い隣人を見つける

頭のてっぺんから、あなたのポイントに最も近い「n」を見つけるための迅速で汚いアルゴリズムがあります。必ずしも最適に効率的であるとは限りませんが、実装はかなり簡単です。誰かがより良いものへのリンクを持っている場合は、コメントまたは回答でそれを投稿してください。

  • 親のリストを保持しながら、ポイントを含む四分木ノードを見つけます。

  • ノード内のすべてのポイントを、ベースポイントからの距離に基づいて（つまり、ピタゴラスの定理による斜辺の長さによって）優先キューにプッシュします。実装によっては、ノードごとに1つ以上存在する場合があります。優先キューデータ構造の簡単な実装については、「バイナリヒープ」を検索してください。

  • 'n'ポイントのいずれかがバウンディングボックスの端よりも遠くにある場合は、その隣接ボックスのコンテンツを追加します。つまり、基点がバウンディングボックスの端に近い場合、隣接するツリーノードに、バウンディングボックス内にあるポイントよりも近いポイントが含まれている可能性があります。これを行うには、ツリーをバックアップする必要があります。そのため、親ノードを追跡する必要があります。

  • すべての「n」個の最も近い点がバウンディングボックスの端よりも近い場合、見逃した隣人が存在する可能性はないことがわかります。したがって、このボックス内の「n」個の最も近い点は、「n」個の最も近い点である必要があります。

于 2010-05-07T09:20:18.660 に答える