1

points一定の空間内の位置の x-y- および z- コンポーネントを含む一連のオブジェクト ( と呼びましょう) があります。のオブジェクト間の相互作用をモデル化したいと考えてpointsいますが、このセット内のオブジェクトの 1 つから一定の距離よりも離れていないセット内のオブジェクトをすばやく見つけることができない限り、モデル化することはできません。

これは間違いなく少し不明確に聞こえるので、別の言い方をしましょう: の最初の点pointsが座標を持っている場合、<x, y, z>どのオブジェクトがpoints最初の点から [任意の値] よりも短い距離を持っているかを調べたいと思います。 .

Java でこれを行うために R ツリーの実装を検討していましたが、これはよくある問題であり、より簡単な解決策が存在するように感じます。x存在しない場合は、ツリー内のオブジェクトからある程度の距離内にあるオブジェクトを見つけるために R ツリーにクエリを実行する方法の簡単な説明をいただければ幸いですx。

編集: これらのオブジェクトの位置の値が変更されることに注意してください

4

3 に答える 3

1

EDIT : 正方形 = 立方体 (ただし、2D 空間で想像した方がよいかもしれませんが、簡単に 3D に変換できます)

と思っていたのですが、解決したようです。ただし、これは単なる「私の」解決策であり、参照はありません。

そのオブジェクトの位置、幅、およびポイントのリストを持つクラス「Square」を作成します。

すべての正方形は、その位置に基づいて配列またはハッシュマップに格納されるため、求める位置がわかっている場合はすばやくアクセスできます。

すべての正方形は定期的に分散されるため、「ポイント インスタンス」の観点からは、既存のすべての正方形を知っていなくても、自分がどの正方形に属しているかを一定時間で把握できます。(例: 幅 40 の正方形があり、それらは 20 の距離で分散されていることを知っています。私は位置 10001 にいるので、位置 9980 と 10000 の正方形に属していることがわかります)

正方形は互いに交差するため、1 つの点がより多くの正方形に存在する可能性があります。

何かを行うとき、ポイントごとに、ポイントが属する正方形に保存されているポイントのみをチェックします。もちろん、目標を達成するには、正方形が十分に大きく、十分に交差している必要があります。

ポイントが移動するとき、それらは正方形への登録と登録解除を担当します。

1D の例:

クラス :Line segmentおよびPoint

Attrributes:

Line segment: int position,List<Points> points

Point: int position,List<LineSegment> lineSegments

20 の距離にある点のみとやり取りしたい。

そこで、幅 40 のインスタンスを作成し、Line segmentsそれらを 20 の距離に 1 つずつ配置します。

したがって、それらは位置 0、20、40、60 .... になります。

最初のものはエリア 0 ～ 40、2 つ目は 20 ～ 60 などをカバーします。

それらを配列に入れ、既知の位置ですばやくアクセスできます。arrayOfLineSegments[position/20]

ポイントを作成するとき、line segmentsそれが属する に彼を追加します。

更新すると、各ポイントは lineSegments 内のポイントとのみ相互作用します。

ポイントを移動すると、それが属する lineSegments が登録および登録解除されます。

于 2014-02-26T03:04:26.340 に答える
1

R* ツリーは、特にポイントが変化する場合に、このための非常に優れたデータ構造です。実際、変更用に設計されています。

kd-tree はより単純ですが、変更をうまくサポートしていません。これは、1 回限りの一括構築用に設計されています。

ただし、データは 3 次元にすぎないため、データがメモリに収まるほど小さく、x、y、z の最大値と最小値がわかっている場合、octreeまたは単純なグリッドは単純さとパフォーマンスのトレードオフになる可能性があります。あなたが必要です。

特に、クエリの半径を事前に固定している場合は、グリッド ファイルに勝るものはありません。R* ツリーは、複数の半径、ウィンドウ クエリ、最近傍クエリなどをサポートする必要がある場合に魅力的です。

于 2014-02-26T12:04:23.797 に答える