Quadtree mit Duplikaten

Ich implementiere einen Quadtree. Für diejenigen, die diese Datenstruktur nicht kennen, füge ich die folgende kleine Beschreibung hinzu:

Ein Quadtree ist eine Datenstruktur und befindet sich in der euklidischen Ebene wie ein Octree in einem dreidimensionalen Raum. Eine häufige Verwendung von Quadtrees ist die räumliche Indizierung.

Um zusammenzufassen, wie sie funktionieren, ist ein Quadtree eine Sammlung - sagen wir hier Rechtecke - mit einer maximalen Kapazität und einem anfänglichen Begrenzungsrahmen. Beim Versuch, ein Element in einen Quadtree einzufügen, der seine maximale Kapazität erreicht hat, wird der Quadtree in 4 Quadtrees unterteilt (eine geometrische Darstellung hat vor dem Einfügen eine viermal kleinere Fläche als der Baum). Jedes Element wird in den Teilbäumen entsprechend seiner Position neu verteilt, d. h. Die obere linke Grenze beim Arbeiten mit Rechtecken.

Ein Quadtree ist also entweder ein Blatt und hat weniger Elemente als seine Kapazität oder ein Baum mit 4 Quadtrees als Kinder (normalerweise Nordwesten, Nordosten, Südwesten, Südosten).

Ich mache mir Sorgen, dass Quadtrees ein grundlegendes Problem beim Umgang mit den Kanten haben, wenn Sie versuchen, Duplikate hinzuzufügen, sei es mehrmals dasselbe Element oder mehrere verschiedene Elemente mit derselben Position.

Wenn Sie beispielsweise mit einem Quadtree mit einer Kapazität von 1 und dem Einheitsrechteck als Begrenzungsrahmen arbeiten:

[(0,0),(0,1),(1,1),(1,0)]

Und Sie versuchen, zweimal ein Rechteck einzufügen, dessen obere linke Grenze der Ursprung ist: (oder ähnlich, wenn Sie versuchen, es N + 1 Mal in einen Quadtree mit einer Kapazität von N> 1 einzufügen)

quadtree->insert(0.0, 0.0, 0.1, 0.1)
quadtree->insert(0.0, 0.0, 0.1, 0.1)

Der erste Einsatz wird kein Problem sein:

Aber dann löst die erste Einfügung eine Unterteilung aus (weil die Kapazität 1 ist):

Beide Rechtecke werden somit in den gleichen Teilbaum gestellt.

Andererseits werden die beiden Elemente im selben Quadtree ankommen und eine Unterteilung auslösen…

Und so weiter und so fort wird die Unterteilungsmethode auf unbestimmte Zeit ausgeführt, da sich (0, 0) immer im selben Teilbaum der vier erstellten befindet, was bedeutet, dass ein unendliches Rekursionsproblem auftritt.

Ist es möglich, einen Quadtree mit Duplikaten zu haben? (Wenn nicht, kann man es als implementieren Set)

Wie können wir dieses Problem lösen, ohne die Architektur eines Quadtree vollständig zu zerstören?

Sie implementieren eine Datenstruktur, müssen also Implementierungsentscheidungen treffen.

Sofern der Quadtree nichts Spezielles über die Einzigartigkeit zu sagen hat - und mir ist nicht bewusst, dass dies der Fall ist -, ist dies eine Implementierungsentscheidung. Es ist orthogonal zur Definition eines Quadtree und Sie können wählen, ob Sie damit umgehen möchten, wie Sie möchten. Der Quadtree zeigt Ihnen, wie Sie Schlüssel einfügen und aktualisieren, aber nicht, ob sie eindeutig sein müssen oder was Sie an jeden Knoten anhängen können.

Implementierungsentscheidungen zu treffen bedeutet nicht, das Rad neu zu erfinden , zumindest nicht mehr als die eigene Implementierung zu schreiben.

Zum Vergleich bietet die C ++ - Standardbibliothek einen eindeutigen Satz, ein nicht eindeutiges Multiset, eine eindeutige Zuordnung (im Wesentlichen einen Satz von Schlüssel-Wert-Paaren, die nur nach dem Schlüssel geordnet und verglichen werden) und eine nicht eindeutige Multimap. Sie werden normalerweise alle mit demselben rot-schwarzen Baum implementiert, und keiner bricht die Architektur , einfach weil die Definition des rot-schwarzen Baums nichts über die Eindeutigkeit von Schlüsseln oder die in Blattknoten gespeicherten Typen zu sagen hat.

Wenn Sie der Meinung sind, dass diesbezüglich Nachforschungen angestellt sind, finden Sie es, und dann können wir darüber diskutieren. Vielleicht gibt es eine Quadtree-Invariante, die ich übersehen habe, oder eine zusätzliche Einschränkung, die eine bessere Leistung ermöglicht.

Ich denke, hier gibt es ein Missverständnis.

So wie ich es verstehe, enthält jeder Quadtree-Knoten einen Wert, der durch einen Punkt indiziert ist. Mit anderen Worten, es enthält das Tripel (x, y, Wert).

Es enthält auch 4 Zeiger auf untergeordnete Knoten, die null sein können. Es gibt eine algorithmische Beziehung zwischen den Schlüsseln und den untergeordneten Links.

Ihre Beilagen sollten so aussehen.

quadtree->insert(0.0, 0.0, value1)
quadtree->insert(0.0, 0.0, value2)

Die erste Einfügung erstellt einen (übergeordneten) Knoten und fügt einen Wert ein.

Die zweite Einfügung erstellt einen untergeordneten Knoten, verknüpft ihn und fügt einen Wert ein (der möglicherweise mit dem ersten Wert identisch ist).

Welcher untergeordnete Knoten instanziiert wird, hängt vom Algorithmus ab. Wenn der Algorithmus die Form [x] hat und der Koordinatenraum im Bereich [0,1] liegt, überspannt jedes Kind den Bereich [0,0,5) und der Punkt wird im NW-Kind platziert.

Ich sehe keine unendliche Rekursion.

Die übliche Lösung, auf die ich gestoßen bin (bei Visualisierungsproblemen, nicht bei Spielen), besteht darin, einen der Punkte fallen zu lassen, entweder immer zu ersetzen oder nie zu ersetzen.

Ich nehme an, der Hauptgrund dafür ist, dass es einfach ist.

Ich gehe davon aus, dass Sie Elemente indizieren, die alle ungefähr gleich groß sind, sonst wird das Leben komplex oder langsam oder beides ……

Ein Quadtree Knoten nicht braucht eine feste Kapazität haben. Die Kapazität ist gewohnt

• Ermöglichen Sie jedem Baumknoten eine feste Größe im Speicher oder auf der Festplatte - nicht erforderlich, wenn der Baumknoten einen Satz von Elementen variabler Größe enthält und Sie ein Speicherplatzzuweisungssystem verwenden, das damit fertig wird. (ZB Java / C # -Objekte im Speicher.)
• Entscheiden Sie, wann ein Knoten geteilt werden soll.
  • Sie können die Regel einfach neu definieren, sodass ein Knoten aufgeteilt wird, wenn er mehr als „n“ Distriktelemente enthält, wobei der Distrikt entsprechend der Position der Elemente definiert wird.
  • Oder verwenden Sie ein „ zusammengesetztes Element“. Wenn sich also an derselben Stelle mehrere Elemente befinden, führen Sie ein neues Element ein, das eine Liste dieser multiplizierten Elemente enthält.

Wenn Sie Probleme mit der räumlichen Indizierung haben, empfehle ich, mit einem räumlichen Hash oder meinem persönlichen Favoriten zu beginnen: dem einfachen alten Raster.

... und verstehen Sie zuerst seine Schwächen, bevor Sie zu Baumstrukturen übergehen, die spärliche Darstellungen ermöglichen.

Eine der offensichtlichen Schwächen besteht darin, dass Sie möglicherweise Speicher für viele leere Zellen verschwenden (obwohl ein anständig implementiertes Raster nicht mehr als 32 Bit pro Zelle erfordern sollte, es sei denn, Sie müssen tatsächlich Milliarden von Knoten einfügen). Ein weiterer Grund ist, dass Sie, wenn Sie mittelgroße Elemente haben, die größer als die Größe einer Zelle sind und häufig beispielsweise Dutzende von Zellen umfassen, viel Speicher verschwenden können, indem Sie diese mittelgroßen Elemente in weit mehr Zellen als ideal einfügen. Wenn Sie räumliche Abfragen durchführen, müssen Sie möglicherweise mehr Zellen überprüfen, manchmal weit mehr als ideal.

Das Einzige, was Sie mit einem Raster tun müssen, um es so optimal wie möglich gegen eine bestimmte Eingabe zu machen, ist cell size, dass Sie nicht zu viel darüber nachdenken und herumspielen müssen, und deshalb ist es meine bevorzugte Datenstruktur für räumliche Indizierungsprobleme, bis ich Gründe finde, es nicht zu verwenden. Es ist einfach zu implementieren und erfordert nicht, dass Sie mit mehr als einer einzelnen Laufzeit-Eingabe herumspielen.

Sie können viel aus einem einfachen alten Raster herausholen, und ich habe tatsächlich viele Quad-Tree- und KD-Tree-Implementierungen geschlagen, die in kommerzieller Software verwendet werden, indem ich sie durch ein einfaches altes Raster ersetzte (obwohl sie nicht unbedingt die am besten implementierten waren , aber die Autoren verbrachten viel mehr Zeit als die 20 Minuten, die ich damit verbracht habe, ein Gitter aufzupeitschen. Hier ist eine kurze Kleinigkeit, die ich zusammengestellt habe, um eine Frage an anderer Stelle mithilfe eines Rasters zur Kollisionserkennung zu beantworten (nicht einmal wirklich optimiert, nur ein paar Stunden Arbeit, und ich musste die meiste Zeit damit verbringen, zu lernen, wie die Wegfindung funktioniert, um die Frage zu beantworten und es war auch mein erstes Mal, dass ich eine solche Kollisionserkennung implementierte):

Eine weitere Schwäche von Gittern (aber sie sind allgemeine Schwächen für viele räumliche Indexierungsstrukturen) besteht darin, dass beim Einfügen vieler übereinstimmender oder überlappender Elemente, wie z. B. vieler Punkte mit derselben Position, diese in genau dieselbe Zelle (n) eingefügt werden ) und verschlechtern die Leistung beim Durchlaufen dieser Zelle. Wenn Sie viele massive Elemente einfügen , die weitaus größer als die Zellengröße sind, möchten sie in eine Schiffsladung von Zellen eingefügt werden, viel Speicherplatz verbrauchen und die für räumliche Abfragen auf der ganzen Linie erforderliche Zeit verkürzen .

Diese beiden oben genannten unmittelbaren Probleme mit zusammenfallenden und massiven Elementen sind jedoch tatsächlich für alle räumlichen Indexierungsstrukturen problematisch . Das einfache alte Gitter behandelt diese pathologischen Fälle tatsächlich ein wenig besser als viele andere, da es zumindest Zellen nicht immer wieder rekursiv unterteilen möchte.

Wenn Sie mit dem Raster beginnen und sich auf einen Quad- oder KD-Baum zuarbeiten, ist das Hauptproblem, das Sie lösen möchten, das Problem, dass Elemente in zu viele Zellen eingefügt werden, zu viele Zellen haben und / oder zu viele Zellen mit dieser Art der dichten Darstellung überprüfen müssen.

Aber wenn Sie sich einen Quad-Tree als Optimierung über ein Gitter vorstellenFür bestimmte Anwendungsfälle ist es dann hilfreich, immer noch an die Idee einer "minimalen Zellengröße" zu denken, um die Tiefe der rekursiven Unterteilung der Quad-Tree-Knoten zu begrenzen. Wenn Sie dies tun, wird das Worst-Case-Szenario des Quad-Baums immer noch in das dichte Gitter an den Blättern zerfallen, nur weniger effizient als das Gitter, da es logarithmische Zeit benötigt, um sich von der Wurzel zur Gitterzelle zu arbeiten konstante Zeit. Wenn Sie jedoch an diese minimale Zellengröße denken, wird das Endlosschleifen- / Rekursionsszenario vermieden. Für massive Elemente gibt es auch einige alternative Varianten wie lose Quad-Bäume, die sich nicht unbedingt gleichmäßig teilen und AABBs für überlappende untergeordnete Knoten haben könnten. BVHs sind auch als räumliche Indexierungsstrukturen interessant, die ihre Knoten nicht gleichmäßig unterteilen. Für übereinstimmende Elemente gegen Baumstrukturen, Die Hauptsache ist, der Unterteilung nur eine Grenze aufzuerlegen (oder, wie andere vorgeschlagen haben, sie einfach abzulehnen oder einen Weg zu finden, sie so zu behandeln, als würden sie nicht zur eindeutigen Anzahl von Elementen in einem Blatt beitragen, wenn bestimmt wird, wann das Blatt ist sollte unterteilen). Ein Kd-Baum kann auch nützlich sein, wenn Sie Eingaben mit vielen übereinstimmenden Elementen erwarten, da Sie nur eine Dimension berücksichtigen müssen, wenn Sie bestimmen, ob ein Knoten im Median aufgeteilt werden soll.