Raumindex für Rechtecke mit schnellem Einfügen

Question

Ich suche eine Datenstruktur, die Indizierung für Rechtecke bietet. Ich benötige den Einfügealgorithmus so schnell wie möglich, da sich die Rechtecke auf dem Bildschirm bewegen werden (stellen Sie sich vor, ein Rechteck mit der Maus an eine neue Position zu ziehen).

Ich habe mich mit R-Trees, R+Trees, kD-Trees, Quad-Trees und B-Trees beschäftigt, aber meiner Meinung nach sind Einfügungen in der Regel langsam. Ich hätte es lieber, dass Einfügungen eine sublineare Zeitkomplexität aufweisen, also kann mir vielleicht jemand das Gegenteil über eine der aufgeführten Datenstrukturen beweisen.

Ich sollte die Datenstruktur abfragen können, welche Rechtecke sich am Punkt (x, y) oder welche Rechtecke das Rechteck (x, y, Breite, Höhe) schneiden.

EDIT: Der Grund, warum ich eine schnelle Einfügung wünsche, ist, dass, wenn man sich vorstellt, dass ein Rechteck über den Bildschirm bewegt wird, sie entfernt und dann wieder eingefügt werden müssen.

Danke!

Answer 1

Ich würde einen Multi-Skalen-Gitteransatz verwenden (entsprechend Quad-Bäumen in irgendeiner Form).

Ich gehe davon aus, dass Sie ganzzahlige Koordinaten (d. h. Pixel) verwenden und genügend Platz haben, um alle Pixel zu speichern.

Haben Sie ein Array von Listen von Rechtecken, eins für jedes Pixel. Dann fügen Sie zwei mal zwei ein und machen es wieder. Und wieder, und wieder, und wieder, bis Sie ein Pixel haben, das alles abdeckt.

Jetzt ist der Schlüssel, dass Sie Ihre Rechtecke auf der Ebene einfügen, die gut zur Größe des Rechtecks passt. Das wird ungefähr wie (Pixelgröße) ~= min(Höhe, Breite)/2 sein. Nun haben Sie nur eine Handvoll Einfügungen in die Listen zu machen (Sie könnten es nach oben durch eine Konstante begrenzen, z. B. etwas zwischen 4 und 16 Pixel wählen).

Wenn Sie alle Rechtecke bei x,y suchen möchten, suchen Sie in der Liste des kleinsten Pixels und dann in der Liste des 2x2 gebinnten Pixels, der es enthält, und dann in der 4x4 usw.; Sie sollten log2(# der Pixel) Schritte durchsuchen müssen. (Für größere Pixel müssen Sie dann überprüfen, ob (x,y) wirklich im Rechteck war; Sie erwarten, dass ungefähr die Hälfte von ihnen an den Grenzen erfolgreich ist, und alle im Inneren des Rechtecks erfolgreich sind, sodass Sie nicht mit mehr als der doppelten Arbeit rechnen müssen, als wenn Sie das Pixel direkt nachschauen.)

Und was ist mit Einfügen? Das ist sehr kostengünstig - O(1), um sich selbst an den Anfang einer Liste zu setzen.

Was ist mit Löschen? Das ist teurer; Sie müssen sich durch jede Liste kämpfen und für jedes Pixel, in das Sie eingetreten sind, die Heilung durchführen. Das entspricht ungefähr O(n) in der Anzahl der sich überschneidenden Rechtecke an dieser Position im Raum und ungefähr derselben Größe. Wenn Sie wirklich große Zahlen von Rechtecken haben, sollten Sie dann eine andere Datenstruktur verwenden, um sie zu halten (Hash-Set, RB-Baum usw.).

(Beachten Sie, dass, wenn Ihr kleinstes Rechteck größer sein muss als ein Pixel, Sie die Multiskalenstruktur nicht tatsächlich bis auf die Pixelebene bilden müssen; gehen Sie einfach so weit hinunter, bis das kleinste Rechteck nicht hoffnungslos in Ihrem gebinnten Pixel verloren geht.)

Answer 2

Dies ist vielleicht eher ein ausführlicher Kommentar als eine Antwort.

Ich bin ein wenig verwirrt darüber, was du wirklich möchtest. Ich könnte vermuten, dass du eine Datenstruktur möchtest, die schnelle Antworten auf Fragen wie "Gegeben die ID eines Rechtecks, gib seine aktuellen Koordinaten zurück" unterstützt. Ist das richtig?

Oder möchtest du die Frage beantworten "Welches Rechteck befindet sich an der Position (x, y)"? In diesem Fall könnte ein Array mit Dimensionen, die der Höhe und Breite deines Bildschirms entsprechen, ausreichen, wobei jedes Element im Array eine (vermutlich kurze) Liste der Rechtecke auf diesem Pixel ist.

Aber dann stellst du fest, dass du einen Einfügealgorithmus benötigst, der so schnell wie möglich ist, um mit ständig bewegten Rechtecken umgehen zu können. Wenn du beispielsweise nur 10 Rechtecke auf dem Bildschirm hättest, könntest du einfach ein 10-elementiges Array haben, das die Koordinaten jedes Rechtecks enthält. Ihre Positionen zu aktualisieren würde dann keine Einfügungen in die Datenstruktur erfordern.

Wie viele Rechtecke? Wie schnell werden sie erstellt? und zerstört? Wie möchtest du mit Überlappungen umgehen? Ist ein Rechteck nur eine Begrenzung oder umfasst es auch das Innere?

Answer 3

Die von Ihnen erwähnten Datenstrukturen sind ziemlich gemischt: Insbesondere sollten B-Bäume schnell sein (die Kosten für das Einfügen wachsen mit dem Logarithmus der Anzahl der vorhandenen Elemente), beschleunigen jedoch Ihre Schnittabfragen nicht.

Ignorieren wir das - und hoffen das Beste - die räumlichen Datenstrukturen bestehen aus zwei Teilen. Der erste Teil sagt Ihnen, wie Sie eine Baumstruktur aus den Daten erstellen. Der zweite Teil sagt Ihnen, wie Sie Informationen an jedem Knoten verfolgen, die die darunter gespeicherten Elemente beschreiben, und wie Sie diese verwenden können, um Abfragen zu beschleunigen.

Sie können normalerweise die Ideen zur Verfolgung von Informationen an jedem Knoten übernehmen, ohne die (kostspieligen) Ideen zur genauen Gestaltung des Baums zu verwenden. Beispielsweise könnten Sie einen Schlüssel für jedes Rechteck erstellen, indem Sie die Koordinaten seiner Punkte bitweise verschachteln, und dann eine völlig gewöhnliche Baumstruktur (wie einen B-Baum oder einen AVL-Baum oder einen Rot-Schwarz-Baum) verwenden, um sie zu speichern, während Sie weiterhin Informationen an jedem Knoten behalten. Dies könnte Ihre Abfragen in der Praxis genug beschleunigen - obwohl Sie das erst sagen könnten, wenn Sie es implementiert und an echten Daten getestet haben. Der Zweck der Baum-Aufbauanweisungen in den meisten Schemata ist die Bereitstellung von Leistungsgarantien.

Zwei Nachschriften:

1) Ich mag Patricia-Bäume dafür - sie sind ziemlich einfach zu implementieren, und das Hinzufügen oder Löschen von Einträgen stört die Baumstruktur nicht so sehr, sodass Sie nicht viel Arbeit damit haben, Informationen an Knoten zu aktualisieren.

2) Als ich mir das letzte Mal ein Fenstersystem angesehen habe, hat es sich überhaupt nicht um all diese cleveren Dinge gekümmert - es hat einfach eine lineare Liste von Elementen gespeichert und ist durch sie hindurchsucht, wenn es musste: das war schnell genug.