Ich schreibe eine Implementierung eines R-Trees auf der Grundlage von Guttmans Originalarbeit. Ich habe darüber nachgedacht, einen R-Tree für ein Programm zu verwenden, das ich schreibe und das eine Menge Rechtecke auf dem Bildschirm enthält, die mit der Maus verschoben und in der Größe verändert werden können.
Ich möchte effizient nur Rechtecke auswählen, die in einem bestimmten Rechteck sind und zeichnen sie (statt durch potenziell 100 + Elemente zu iterieren und prüfen, ob Grenzen schneiden). Das Problem, das ich nach einigen Lektüren von Guttmans Papier gefunden habe, ist, dass die z-Reihenfolge für 2D-Objekte nicht beibehalten werden kann.
Wenn ich zum Beispiel ein Objekt verschiebe, wird es gelöscht und dann wieder eingefügt. Wenn es wieder eingefügt wird, kann der Knoten, in den es eingefügt wurde, die richtige Reihenfolge nicht mehr nachvollziehen. Die meisten Implementierungen eines R-Trees, die ich gesehen habe, verwenden ein Array und finden einfach die leere Position. Die Wiedereinfügung würde im Wesentlichen alle z-Reihenfolge Positionierung zerstören.
Wenn ich also alle Rechtecke zeichnen will, die sich mit einem Rechteck schneiden, ist die Reihenfolge, in der sie zurückgegeben werden, nicht unbedingt korrekt.
Liege ich mit dieser Vermutung falsch? Ich dachte, statt eines Arrays könnte ich einen AVL- oder Red-Black-Baum verwenden und eine Comparer die auf z-index vergleicht, um in den Baum einzufügen. Auf diese Weise wird die z-Reihenfolge immer beibehalten (und das ist der wichtigste Faktor).
Ich habe auch daran gedacht, sie bei der Rückgabe zu sortieren, aber das könnte teurer werden, denke ich.
