ポイントから一定の距離内のすべての3Dオブジェクトを検索する

Question

私はオブジェクトのセットを持っています（それを呼びましょう points）は、ある一定の空間内の位置のx-y-およびz-成分を含む。私はオブジェクト間の相互作用をモデル化したいと思います points, ただし、セット内のオブジェクトの1つから一定の距離未満のオブジェクトをすばやく見つけることができない限り、そうすることはできません。

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

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

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

Answer 1

R*-treeは、特にポイントが変化している場合に、このためのかなり良いデータ構造です。これは、実際には、変更のために設計されています。

K-d-treeはより単純ですが、変更をあまりうまくサポートしていません。それは一度だけのバルク構造のために設計されています。

ただし、データは3次元のみであるため:データがメモリに収まるほど小さく、x、y、zの最大値と最小値がわかっている場合は、x、y、zの最大値と最小値がわかっている場合は、x、y、zの最大値と最小値 オクトリー または単純な グリッド あなたが必要とするシンプルさとパフォーマンスのトレードオフかもしれません。

特に、事前にクエリ半径を修正した場合、グリッドファイルを打ち負かすのは難しいです。R*-複数の半径、ウィンドウクエリ、最近傍クエリなどをサポートする必要がある場合、ツリーは魅力的になります。

Answer 2

編集 :Square=Cube（ただし、2D空間で想像する方が良いかもしれませんが、簡単に3Dに変換できます）

私は考えていたし、私はそれを解決したと思う。しかし、これは単なる「私の」解決策であり、私はそれについての参照を持っていません。

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

すべての正方形はその位置に基づいてarrayまたはhashmapに格納されるため、探している位置がわかっている場合はすぐにアクセスできます。

すべての正方形は定期的に配布されるため、「ポイントインスタンス」の観点から、あなたが属している正方形を一定の時間内に把握するために、既存のすべての正方形を知る必要はありません。（例 :私は幅が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の距離の点だけと対話したい。

だから私はのインスタンスを作成します Line segments 幅40と私は20の距離でそれらを一つずつ置きます。

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

Fristの1つは区域0-40、第2 20-60等をカバーします。

私はそれらを配列に入れ、既知の位置で、私はすぐにそれらにアクセスすることができます : arrayOfLineSegments[position/20]

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

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

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

Answer 3

Forループを使用して、オブジェクトの配列をチェックすることができます。

次の式を使用します: d = sqrt[(x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2]

x1、y1、z1が最初の点である Points そして、x2、y2、z2はあなたがチェックしているオブジェクトのポイントです。これにより、既知のポイントと他のすべてのポイントがチェックされます。距離（d）がご希望の距離よりも小さい場合 x 次に、プログラムに実行したいことを何でも実行します。