Finden aller 3D-Objekte innerhalb einer bestimmten Entfernung vom Punkt

Question

Ich habe eine Reihe von Objekten (nennen wir es points), die die x-, y- und z-Komponenten ihrer Positionen in einem bestimmten Raum enthalten.Ich möchte die Interaktionen zwischen den Objekten in modellieren points, Allerdings kann ich dies nicht tun, es sei denn, ich kann schnell die Objekte in der Menge finden, die weniger als eine bestimmte Entfernung von einem der Objekte in dieser Menge entfernt sind.

Das klingt zweifellos etwas unklar, also lassen Sie es mich anders formulieren:wenn der erste Punkt in points hat Koordinaten <x, y, z>, Ich würde gerne herausfinden, welche der Objekte darin enthalten sind points hat einen Abstand, der kleiner als [ein beliebiger Wert] vom ersten Punkt ist.

Ich habe über die Implementierung eines R-Tree nachgedacht, um dies in Java zu erreichen, aber ich habe das Gefühl, dass dies ein so häufiges Problem ist, dass es eine einfachere Lösung gibt.Wenn es keinen gibt, würde ich mich über eine einfache Erklärung der Methode freuen, mit der man einen R-Baum abfragt, um Objekte zu finden, die sich in einiger Entfernung befinden x von einem Objekt im Baum, wo x ist bereits bekannt.

Bearbeiten:Beachten Sie, dass sich die Positionswerte dieser Objekte ändern

Answer 1

Der R * -Tree ist dafür eine ziemlich gute Datenstruktur, insbesondere wenn sich Punkte ändern.Es ist eigentlich für Änderungen konzipiert.

Der K-D-Baum ist einfacher, aber es unterstützt Änderungen nicht sehr gut.Es ist für eine einmalige Bulk-Konstruktion ausgelegt.

Da Ihre Daten jedoch nur dreidimensional sind: Wenn Ihre Daten klein genug sind, um in den Speicher zu passen, und die maximalen und minimalen Werte von X, Y, Z sind ein octree oder aEinfaches Raster kann der Kompromiss der Einfachheit und Leistung sein, die Sie brauchen.

Insbesondere wenn Sie Ihren Abfrageradius vorher reparieren, ist eine Gitterdatei schwer zu schlagen.R * -Trees wird attraktiv, wenn Sie mehrere Radien, Fensterabfragen, nächstgelegene Nachbarabfragen und all dies unterstützen müssen.

Answer 2

BEARBEITEN :Quadrat = Würfel (allerdings wäre es vielleicht besser, es sich im 2D-Raum vorzustellen, dann kann man es leicht in 3D umwandeln)

Ich habe nachgedacht und ich glaube, ich habe es gelöst.Dies ist jedoch nur „meine“ Lösung, ich habe keine Referenz dafür.

Sie erstellen die Klasse „Quadrat“, die Position, Breite und Liste der Punkte in diesem Objekt enthält.

Alle Quadrate werden basierend auf ihrer Position in einem Array oder einer Hashmap gespeichert, sodass Sie schnell auf sie zugreifen können, wenn Sie die gesuchte Position kennen.

Alle Quadrate werden regelmäßig verteilt, sodass Sie – vom Standpunkt der „Punktinstanz“ aus – nicht alle vorhandenen Quadrate kennen müssen, um in konstanter Zeit herauszufinden, zu welchem ​​Quadrat Sie gehören.(Beispiel :Ich weiß, dass es Quadrate mit einer Breite von 40 gibt, die im Abstand von 20 verteilt sind.Ich bin auf Position 10001, also weiß ich, dass ich zu den Feldern auf Position 9980 und 10000 gehöre)

Quadrate werden einander überschneiden, daher kann ein Punkt in mehreren Quadraten liegen.

Wenn Sie für jeden Punkt etwas tun, überprüfen Sie nur die Punkte, die in den Quadraten gespeichert sind, zu denen der Punkt gehört.Natürlich müssen die Quadrate groß genug und ausreichend gekreuzt sein, um Ihr Ziel zu erreichen.

Wenn sich Punkte bewegen, sind sie für die Registrierung und Abmeldung auf den Feldern verantwortlich.

---

1D-BEISPIEL:

Klassen : Line segment Und Point

Attrributes:

Line segment : int position, List<Points> points

Point : int position, List<LineSegment> lineSegments

Ich möchte nur mit Punkten im Abstand von 20 interagieren.

Also erstelle ich Instanzen von Line segments mit einer Breite von 40 und ich habe sie einzeln im Abstand von 20 platziert.

Sie befinden sich also an den Positionen 0, 20, 40, 60 ....

Der erste deckt den Bereich 0–40 ab, der zweite 20–60 usw.

Ich füge sie in das Array ein und mit bekannter Position kann ich schnell darauf zugreifen: arrayOfLineSegments[position/20]

Wenn ich einen Punkt erstelle, füge ich ihn hinzu line segments es gehört.

Wenn ich aktualisiere, interagiert jeder Punkt nur mit Punkten in Liniensegmenten.

Wenn ich einen Punkt verschiebe, registriert er die Liniensegmente, zu denen er gehört, und hebt die Registrierung auf.

Answer 3

Sie können eine für Schleife verwenden, um das Ziel des Objekts zu überprüfen.

Verwenden Sie die folgende Formel: GROSSACDICETAGCODECODE

x1, y1, z1, wobei der erste Punkt in der Gattungsstätte in der Gattungsstätte ist und der X2, Y2, Z2 die Punkte des Objekts, das Sie überprüfen, sind.Dadurch wird Ihr bekannter Punkt gegen alle anderen Punkte überprüft.Wenn der Abstand (d) weniger als der gewünschte Distanzgürtungsgrafiketicetagcode ist, dann tun Sie, was Sie möchten, dass Sie programmieren möchten.