Ich frage mich, was ist die beste Datenstruktur für Gitter mit unterschiedlich großen Rechtecken / Quadrate als Spielkartensektoren. Ich muss auf das Objekt innerhalb dieses Gitters mit einfachen XYZ-Koordinaten zugreifen.
Nach KdTrees gesucht, aber sie scheinen das nächste Objekt zu finden, ich habe auch Segmentbäume / Intervallbäume gefunden, aber es gibt wenig Infos über sie Prost.
Antworten:
0 für die Antwort № 1Sie können einen Octree verwenden. Das heißt, Sie können mit einem rechteckigen Parallelepiped beginnen, das die gesamte Region ((0, 0, 0), (x, y, z)) enthält (es ist eine Wurzel des Baums). Im nächsten Schritt teilen Sie es in 8 rechteckige Parallelepipeds (((0, 0, 0), (x / 2, y / 2, z / 2)), ((0, 0, z / 2), (x / 2, y / 2, z)) und so weiter). Diese 8 rechteckigen Parallelepipeds sind Kinder der Wurzel. Erstellen Sie den Baum für jeden von ihnen rekursiv. Wenn ein rechteckiges Parallelepiped vollständig innerhalb einer Region liegt, sollte die Rekursion stoppen (so dass sie zu einem Blatt des Baumes wird).
Um eine Abfrage zu beantworten, beginne mit der Wurzel des Octrees und gehe zu einem richtigen Kind, bis du ein Blatt erreichst.
Es ist auch möglich, einen k-d-Baum anzupassen, um zu lösendieses Problem. Die Idee ist ähnlich der oben beschriebenen: Teilen Sie ein Leerzeichen in zwei Halbräume, erstellen Sie für jedes von ihnen rekursiv einen Baum. Der Basisfall für die Rekursion ist ebenfalls der gleiche: Sobald der aktuelle Unterraum nur innerhalb einer Region liegt, sollte die Rekursion stoppen.