Ich habe eine 2D-Karte, die an den Rändern umschlingt. Wenn Sie sich also von der rechten Seite entfernen, werden Sie wieder auf der linken Seite der Karte angezeigt. Ebenso mit den drei anderen Kanten.
Dies ist ein Problem für den KDTree, mit dem ich Elemente im Bereich von Punkten finde. Normalerweise würden Sie prüfen, ob die Hyperkugel mit der Hyperebene kollidiert, um zu sehen, ob Sie die andere Seite des Baums weiter durchsuchen sollten, aber diese Überprüfung funktioniert nicht mit Umbruchkanten.
Gibt es eine Möglichkeit, den KD-Baum so zu modifizieren, dass er mit Donut-2D-Räumen funktioniert?
Die Datenstruktur muss sich nicht ändern, aber der Suchvorgang funktioniert. Stellen Sie jeden Punkt durch Koordinaten (x, y) in [0, w) * [0, h) dar, wobei w die Breite der Karte, h die Höhe und * ein kartesisches Produkt ist. Speichern Sie diese Punkte in einem normalen KD-Baum.
Das fundamentale Primitiv zum Suchen eines KD-Baums ist, gegeben durch einen Punkt (x, y) und ein Rechteck [a, b] * [c, d], den Abstand (quadriert) vom Punkt zum Rechteck. Normalerweise ist dies g (x, a, b) 2 + g (y, c, d) 2 , wobei
gilt %Vor%ist der eindimensionale Abstand von z zu [e, f]. In einem toroidalen Raum modifizieren wir g leicht, um den Umlauf zu berücksichtigen.
%Vor%und der Abstand zum Quadrat ist g (x, a, b, w) 2 + g (y, c, d, h) 2 . Ich erwarte, dass die Laufzeiten für diese Variante vergleichbar sind. (Ich würde die Wiederholungen wiederholen, aber der schlimmste Fall für normale KD-Bäume ist viel schlimmer als die Praxis - O (n 1/2 )), um den nächsten Nachbarn in 2D unter n zu identifizieren Punkte.)
Jitamaro schlug vor, erklärte aber keine Methode, die auf einem Quadtree "2x Größe" basierte. Es ist ein vernünftiger Vorschlag, außer dass der Quadtree viermal so viele Knoten als zwei verwendet, wie ich unten erklären werde, bevor ich versuchsweise eine alternative Methode vorschlage.
Angenommen, jede Koordinate (x, y) hat -.5 < x <= .5 und -.5 < y <= .5 , und wenn j, k ganze Zahlen sind, ist der Punkt (x + j, y + k) identisch mit dem Punkt (x, y). Lassen Sie Quadtree T über Punkte mit Koordinaten im Bereich -1 < x,y <= 1 liegen. Jedes Mal, wenn Sie ein Element bei (x, y) zu T hinzufügen, wobei -.5 < x,y <= .5 gilt, lassen Sie x' = {x-1 if x>0 else x+1} und y' = {y-1 if y>0 else y+1} . Fügen Sie auch das Element bei (x, y '), (x', y ') und (x', y) hinzu. [Wenn Sie Punkte später löschen, berechnen Sie erneut (x ', y') usw. und löschen sie auch.] Es ist leicht zu erkennen, dass die Suche nach dem nächstgelegenen Punkt ordnungsgemäß funktioniert, solange die Nachschlagkoordinaten außerhalb des Intervalls (-.5,.5] angepasst werden richtig.
Wenn die vierfache Anzahl von Knoten ein Deal-Breaker ist, beachten Sie, dass, wenn die oben beschriebenen Koordinaten in Teilbäumen oberhalb der Ebene k=3 verwendet werden und relative Koordinaten unterhalb der Ebene k gespeichert werden, es möglich sein sollte um einzelne Kopien von Unterbäumen unter dem Level k zu erhalten. Das heißt, jeder Unterbaum auf der Ebene k würde vier Eltern haben. (Ich habe nicht genug darüber nachgedacht, um zu wissen, ob das völlig funktioniert; werde die Antwort bearbeiten, wenn ich es nicht finde.)
Tags und Links algorithm c# data-structures space-partitioning