Can R-Bäume aufrechtzuerhalten z-Ordnung, wenn 2-Dimensionen?

Question

Ich schreibe eine Implementierung eines R-Baum basierend auf Originalpapier des Guttman. Ich dachte an einen R-Tree für ein Programm schreibe ich, dass eine Menge Rechtecke auf dem Bildschirm beinhaltet, die bewegt werden können / die Größe neu mit der Maus.

Ich möchte effizient nur Rechtecke auszuwählen, die in einem bestimmten Rechteck und ziehen sie (statt potenziell mehr als 100 Artikel Iterieren durch und überprüft, ob Grenzen schneiden). Das Problem, dass ich zu finden bin nach ein paar Guttman Papier liest, ist, dass z-Ordnung nicht aufrecht erhalten werden kann für 2D-Objekte.

Zum Beispiel, wenn ich ein Objekt bewegen, würde sie gelöscht wird und dann wieder eingefügt. Wenn es wieder eingesetzt, der Knoten es würde eingefügt wird nicht in der Lage sein, den Überblick über die richtige Reihenfolge zu halten. Die meisten Implementierung ist ein R-Baum, dass ich ein Array gesehen habe und nur die leere Position finden. Die Reinsertion würde im Wesentlichen jede z-Positionierung, um zerstören.

Wenn ich also gehen alle Rechtecke zu zeichnen, dass schneiden mit einem Rechteck, das um sie zurück sind, ist nicht unbedingt richtig.

Bin ich falsch auf dieser Annahme? Ich dachte stattdessen ein Array zu verwenden, ich einen AVL oder Rot-Schwarz-Baum verwenden könnte und eine Comparer verwenden, die in den Baum eingefügt wird auf z-Index vergleicht. Auf diese Weise z-Ordnung wird immer beibehalten (und es ist der wichtigste Faktor).

Ich war auch nur denken, sie zu sortieren, wenn sie zurückgegeben sind, aber dies könnte teurer sein ich bin denken.

Answer 1

R-Baum ist nicht anzunehmen, um Antwortdatensätze irgendwie.

Beantworten Sie einfach sortieren. Es ist nicht zu langsam.

BTW, kann ich Ihnen mein r Baum Code Mail. Es funktioniert gut für mich, aber es wäre sehr hilfreich, wenn jemand überprüfen würde, ist es, was Guttman oder Beckman in ihren Papieren geschrieben ...

Reihenfolge der räumlichen Indizierung unterscheidet sich wesentlich von der strengen Ordnung ... es die Differenz zwischen der räumlichen Indizierung und nur B + -Baum.

Sie können auch zwei Indizes haben und sich anzuschließen. Sind Sie wirklich shure Sie Index benötigen? Etwas funktioniert langsam?