Wie kann ich feststellen, welche einen Punkt Quader ist, ohne alle über sie iterieren?

Question

Ich habe eine Reihe von Quadern, deren Positionen und Größen mit mindestens gegeben sind und die maximale x, y und z Koordinaten (sie sind also parallel zu den Hauptachsen).

z. Ich könnte die folgenden 3 Quadern haben:

10.5 <= x <= 39.4,  90.73 <= y <= 110.2, 90.23 <= z <= 95.87
20.1 <= x <= 30.05,  9.4  <= y <=  37.6,  0.1  <= z <= 91.2
10.2 <= x <= 10.3,   0.1  <= y <=  99.8, 23.7  <= z <= 24.9

Wenn ich dann einen Punkt geben (z (25.3,10.2,90.65)), ist es eine Möglichkeit, schnell zu bestimmen, welche Quader (s) Ich bin in?

• Natürlich konnte ich gerade durchlaufen alle Quadern, aber es gibt möglicherweise Millionen von ihnen, und ich brauche diese schneller zu gehen als einfache Iteration (etwas O (log n) oder besser wäre gut).

• Das klingt für mich wie ein "fuzzy matching" Typen Problem, und ich merke, dass Apache Lucene unterstützt Bereichsabfragen , aber dies scheint das Gegenteil umgekehrt (die Suche nach einem Punkt in einem Quader eher als ein Quader, die einen Punkt).

arbeiten

• Um etwas Erschwerend kommt hinzu, könnte die Anzahl der Dimensionen als 3 größer sein (es könnte bis zu 20 sein); das heißt, ich könnte für "hypercuboids" suchen, anstatt Quader.)

Answer 1

Eine einfache Möglichkeit, diese Abfrage zu beschleunigen, indem Sie die folgenden einheitlichen Gitter Konstruktion Datenstruktur (häufig auch als Bins) als Vorverarbeitungsschritt: Setzen Sie ein n x n x n (in 3d) Raster über die Szene und für jeden Zelle des Gitters speichert einen Zeiger zu allen Quadern diese Zelle schneiden. Nun, für eine Abfrage Punkt können Sie direkt in berechnen, die Zelle, um sie in das einheitliche Gitter ist, und dann muss man nur die Quadern zu dieser Zelle zugeordnet überprüfen, und nicht alle Quadern.

Je nachdem, wie groß der Raum ist und wie die Quader Größen variiert werden diese Methode nicht sehr effizient sein könnte, weil Sie es schwierig sein könnte, eine gute n Auflösung zu beschleunigen genug und nicht brauchen eine enorme Menge an Zellen zu wählen. Um dies zu überwinden mögen Sie vielleicht versuchen, in mehr adaptiven Wege zu suchen, um den Raum, wie zum Beispiel kd-Bäume (kd-Bäume bei wikipedia) , die mit Achse ausgerichtet Ebenen Partitionieren des Raumes grundsätzlich binäre Bäume sind: hier für ein Beispiel sehen, wo die rote Ebene, die die Box in zwei Teile teilt und dann die grüne in kleinere Teile, dann die blaue ...

Eine Abfrage kd-Baum unter Verwendung würde zuerst zu dem Blatt des kd-Baumes durchquert nach unten, wo denen der Abfrage Punkt befindet und dann mit den lokalen Quadern in dieser Zelle zu prüfen. Andere Raumaufteilung Datenstruktur Optionen können hier .

Eine andere Möglichkeit wäre die Verwendung Begrenzungsvolumen Hierarchien , die Gruppe zusammen Volumina in begrenzenden Objekte, und dann Gruppenbegrenzungsvolumen in größere Begrenzungsvolumina und so weiter ... eine Hierarchie von Begrenzungsvolumen zu erhalten . Dies passen besser zu einer Szene und kann einfache Szenen behandeln, in denen die Objekte bewegen, aber ich würde denken, für Ihre Einstellung Raumaufteilung könnte gut funktionieren ... Wie auch immer, für weitere Informationen siehe dieses Buch Kapitel .

Answer 2

Sie grenzend in das Gebiet von „Binary Space Partitioning“ und „Collision Detection“; im wesentlichen sind die Ideen zu speichern grundsätzlich die Quader in eine Baumtyp-Struktur, die den Raum teilt sie in ordentliche kleine Kästen besetzen. Die Entscheidung darüber, welche „ein Teil des Raumes“ belegt jeden Quaders während des Einsetzens in den Baum strucutre hergestellt wird.

Führen Sie eine Google-Suche auf Octrees.

efficently 3D-Raum unterteilt, und die Objekte in diesem Raum enthalten ist, ist ein ziemlich großer Teil der Informatik; vor allem in der Entwicklung von Computerspielen verwendet. Einige der Algorithmen berücksichtigen einen Zeitfaktor, das heißt, dass die Objekte zwischen Teilungsräumen bewegen.