Quadtree - Quadtree

Ein Punktbereichs-Quadtree mit Punktdaten. Schaufelkapazität 1.

Quadtree-Komprimierung eines Bildes Schritt für Schritt. Links zeigt das komprimierte Bild mit den Baumbegrenzungsboxen, während rechts nur das komprimierte Bild zeigt

Ein Quadtree ist eine Baumdatenstruktur , in der jeder interne Knoten genau vier Kinder hat. Quadtrees sind das zweidimensionale Analogon von Octrees und werden am häufigsten verwendet, um einen zweidimensionalen Raum durch rekursive Unterteilung in vier Quadranten oder Regionen zu unterteilen. Die einer Blattzelle zugeordneten Daten variieren je nach Anwendung, aber die Blattzelle stellt eine "Einheit interessanter räumlicher Informationen" dar.

Die unterteilten Bereiche können quadratisch oder rechteckig sein oder können beliebige Formen haben. Diese Datenstruktur wurde 1974 von Raphael Finkel und JL Bentley als Quadtree bezeichnet . Eine ähnliche Partitionierung wird auch als Q-Tree bezeichnet . Alle Formen von Quadtrees haben einige gemeinsame Merkmale:

• Sie zerlegen den Raum in anpassungsfähige Zellen
• Jede Zelle (oder jeder Eimer) hat eine maximale Kapazität. Wenn die maximale Kapazität erreicht ist, teilt sich die Schaufel
• Das Baumverzeichnis folgt der räumlichen Zerlegung des Quadtrees.

Eine Baumpyramide ( T-Pyramide ) ist ein "vollständiger" Baum; jeder Knoten der T-Pyramide hat vier untergeordnete Knoten außer Blattknoten; alle Blätter befinden sich auf der gleichen Ebene, der Ebene, die einzelnen Pixeln im Bild entspricht. Die Daten in einer Baumpyramide können kompakt in einem Array als implizite Datenstruktur gespeichert werden, ähnlich wie ein vollständiger Binärbaum kompakt in einem Array gespeichert werden kann .

Typen

Quadtrees können nach der Art der Daten klassifiziert werden, die sie darstellen, einschließlich Flächen, Punkte, Linien und Kurven. Quadtrees können auch danach klassifiziert werden, ob die Form des Baums unabhängig von der Reihenfolge ist, in der die Daten verarbeitet werden. Die folgenden sind gängige Arten von Quadtrees.

Regionsquadtree

Der Bereichs-Quadtree stellt eine Raumaufteilung in zwei Dimensionen dar, indem der Bereich in vier gleiche Quadranten, Unterquadranten usw. zerlegt wird, wobei jeder Blattknoten Daten enthält, die einem spezifischen Unterbereich entsprechen. Jeder Knoten im Baum hat entweder genau vier Kinder oder hat keine Kinder (einen Blattknoten). Die Höhe von Quadtrees, die dieser Zerlegungsstrategie folgen (dh Unterteilung von Unterquadranten, solange interessante Daten in dem Unterquadrant vorhanden sind, für die eine weitere Verfeinerung gewünscht wird) ist empfindlich und hängt von der räumlichen Verteilung interessanter Bereiche im zu zerlegenden Raum ab. Die Region Quadtree ist eine Art Trie .

Ein Bereichsquadtree mit einer Tiefe von n kann verwendet werden, um ein Bild darzustellen, das aus 2 ⁿ × 2 ⁿ Pixeln besteht, wobei jeder Pixelwert 0 oder 1 ist. Der Wurzelknoten repräsentiert den gesamten Bildbereich. Wenn die Pixel in einem Bereich nicht vollständig 0 oder 1 sind, wird er unterteilt. In dieser Anwendung repräsentiert jeder Blattknoten einen Block von Pixeln, die alle Nullen oder alle Einsen sind. Beachten Sie die möglichen Platzeinsparungen, wenn diese Bäume zum Speichern von Bildern verwendet werden; Bilder haben oft viele Bereiche von beträchtlicher Größe, die überall den gleichen Farbwert haben. Anstatt ein großes 2D-Array jedes Pixels im Bild zu speichern, kann ein Quadtree die gleichen Informationen erfassen, die potenziell viele Trennebenen höher sind als die Zellen mit Pixelauflösung, die wir sonst benötigen würden. Die Baumauflösung und Gesamtgröße wird durch die Pixel- und Bildgrößen begrenzt.

Ein Bereichs-Quadtree kann auch als Darstellung eines Datenfelds mit variabler Auflösung verwendet werden. Beispielsweise können die Temperaturen in einem Bereich als Quadtree gespeichert werden, wobei jeder Blattknoten die Durchschnittstemperatur über die Unterregion, die er repräsentiert, speichert.

Wenn ein Regions-Quadtree verwendet wird, um einen Satz von Punktdaten darzustellen (z. B. den Breiten- und Längengrad einer Menge von Städten), werden Regionen unterteilt, bis jedes Blatt höchstens einen einzelnen Punkt enthält.

Punktquadtree

Der Punkt-Quadtree ist eine Anpassung eines binären Baums, der verwendet wird, um zweidimensionale Punktdaten darzustellen. Er teilt die Eigenschaften aller Quadtrees, ist aber ein echter Baum, da das Zentrum einer Unterteilung immer auf einem Punkt liegt. Es ist oft sehr effizient beim Vergleich zweidimensionaler, geordneter Datenpunkte, die normalerweise in O(log n) Zeit arbeiten. Punkt-Quadtrees sind der Vollständigkeit halber erwähnenswert, aber sie wurden von k -d-Bäumen als Werkzeuge für die verallgemeinerte binäre Suche übertroffen .

Punktquadtrees werden wie folgt konstruiert. Angesichts des nächsten einzufügenden Punkts suchen wir die Zelle, in der sie liegt, und fügen sie dem Baum hinzu. Der neue Punkt wird so hinzugefügt, dass die Zelle, die ihn enthält, durch die vertikalen und horizontalen Linien, die durch den Punkt verlaufen, in Quadranten unterteilt wird. Folglich sind Zellen rechteckig, aber nicht unbedingt quadratisch. In diesen Bäumen enthält jeder Knoten einen der Eingabepunkte.

Da die Unterteilung der Ebene durch die Reihenfolge der Punkteinfügung bestimmt wird, ist die Höhe des Baums empfindlich und abhängig von der Einfügungsreihenfolge. Das Einfügen in einer "schlechten" Reihenfolge kann zu einem Baum mit linearer Höhe in der Anzahl der Eingabepunkte führen (an diesem Punkt wird er zu einer verknüpften Liste). Wenn die Punktmenge statisch ist, kann eine Vorverarbeitung durchgeführt werden, um einen Baum mit ausgewogener Höhe zu erstellen.

Knotenstruktur für einen Punktquadtree

Ein Knoten eines Punkt-Quadtrees ähnelt einem Knoten eines Binärbaums , mit dem Hauptunterschied, dass er vier Zeiger (einen für jeden Quadranten) anstelle von zwei ("links" und "rechts") wie in einem gewöhnlichen Binärbaum hat . Außerdem wird ein Schlüssel normalerweise in zwei Teile zerlegt, die sich auf die x- und y-Koordinaten beziehen. Daher enthält ein Knoten die folgenden Informationen:

• vier Zeiger: quad['NW'], quad['NE'], quad['SW'] und quad['SE']
• Punkt; die wiederum enthält:
  • Schlüssel; normalerweise ausgedrückt als x, y-Koordinaten
  • Wert; zum Beispiel ein Name

Punktregion (PR) Quadtree

Punktregion-(PR)-Quadtrees sind den Region-Quadtrees sehr ähnlich. Der Unterschied besteht in der Art der über die Zellen gespeicherten Informationen. In einem Bereichsquadtree wird ein einheitlicher Wert gespeichert, der für die gesamte Fläche der Zelle eines Blattes gilt. Die Zellen eines PR-Quadtrees speichern jedoch eine Liste von Punkten, die innerhalb der Zelle eines Blattes existieren. Wie bereits erwähnt, hängt die Höhe bei Bäumen, die dieser Zerlegungsstrategie folgen, von der räumlichen Verteilung der Punkte ab. Wie der Punkt-Quadtree kann auch der PR-Quadtree eine lineare Höhe haben, wenn er einen "schlechten" Satz erhält.

Kanten-Quadtree

Kanten-Quadtrees (ähnlich wie PM-Quadtrees) werden verwendet, um Linien anstelle von Punkten zu speichern. Kurven werden angenähert, indem Zellen mit einer sehr feinen Auflösung unterteilt werden, insbesondere bis es ein einzelnes Liniensegment pro Zelle gibt. In der Nähe von Ecken/Scheitelpunkten teilen sich Kanten-Quadtrees weiter, bis sie ihren maximalen Zerlegungsgrad erreichen. Dies kann zu extrem unausgeglichenen Bäumen führen, die den Zweck der Indexierung zunichte machen können.

Polygonale Karte (PM) Quadtree

Der polygonale Karten-Quadtree (oder PM-Quadtree) ist eine Variation von Quadtree, die verwendet wird, um Sammlungen von Polygonen zu speichern, die degeneriert sein können (d. h. sie haben isolierte Scheitelpunkte oder Kanten). Ein großer Unterschied zwischen PM-Quadtrees und Kanten-Quadtrees besteht darin, dass die betrachtete Zelle nicht unterteilt wird, wenn sich die Segmente an einem Scheitelpunkt in der Zelle treffen.

Es gibt drei Hauptklassen von PM-Quadtrees, die je nachdem, welche Informationen sie in jedem schwarzen Knoten speichern, variieren. PM3-Quadtrees können eine beliebige Anzahl von sich nicht schneidenden Kanten und höchstens einen Punkt speichern. PM2-Quadtrees sind dieselben wie PM3-Quadtrees, außer dass alle Kanten denselben Endpunkt haben müssen. Schließlich ähneln PM1-Quadtrees PM2, aber schwarze Knoten können einen Punkt und seine Kanten oder nur eine Reihe von Kanten enthalten, die einen Punkt teilen, aber Sie können keinen Punkt und eine Reihe von Kanten haben, die den Punkt nicht enthalten.

Komprimierte Quadtrees

Dieser Abschnitt fasst einen Unterabschnitt aus einem Buch von Sariel Har-Peled zusammen .

Wenn wir jeden Knoten speichern würden, der einer unterteilten Zelle entspricht, könnten wir am Ende viele leere Knoten speichern. Wir können die Größe solcher spärlicher Bäume reduzieren, indem wir nur Teilbäume speichern, deren Blätter interessante Daten enthalten (dh "wichtige Teilbäume"). Wir können die Größe sogar noch weiter reduzieren. Wenn wir nur wichtige Unterbäume behalten, kann der Beschneidungsprozess lange Pfade im Baum hinterlassen, wo die Zwischenknoten Grad zwei haben (eine Verbindung zu einem Elternteil und einem Kind). Es stellt sich heraus, dass wir nur den Knoten am Anfang dieses Pfads speichern müssen (und ihm einige Metadaten zuordnen müssen, um die entfernten Knoten darzustellen) und den Teilbaum, der an seinem Ende verwurzelt ist, an anhängen . Es ist immer noch möglich, dass diese komprimierten Bäume eine lineare Höhe haben, wenn ihnen "schlechte" Eingabepunkte gegeben werden. ${\displaystyle u}$${\displaystyle u}$

Obwohl wir bei dieser Komprimierung einen Großteil des Baums trimmen, ist es immer noch möglich, eine Suche, Einfügung und Löschung in logarithmischer Zeit zu erreichen, indem Kurven der Ordnung Z genutzt werden . Die Kurve der Z- Ordnung bildet jede Zelle des vollständigen Quadbaums (und damit sogar des komprimierten Quadbaums) zeitlich auf eine eindimensionale Linie ab (und bildet sie auch zeitlich zurück), wodurch eine Gesamtordnung der Elemente entsteht. Daher können wir den Quadtree in einer Datenstruktur für geordnete Mengen speichern (in der wir die Knoten des Baums speichern). ${\displaystyle O(1)}$${\displaystyle O(1)}$

Wir müssen eine vernünftige Annahme machen, bevor wir fortfahren: Wir nehmen an, dass wir bei zwei binär ausgedrückten reellen Zahlen den Index des ersten Bits, in dem sie sich unterscheiden, rechtzeitig berechnen können . Wir nehmen auch an, dass wir den niedrigsten gemeinsamen Vorfahren von zwei Punkten/Zellen im Quadtree rechtzeitig berechnen und ihre relative Z- Ordnung festlegen können, und wir können die Bodenfunktion in der Zeit berechnen . ${\displaystyle \alpha,\beta\in [0,1)}$${\displaystyle O(1)}$${\displaystyle O(1)}$${\displaystyle O(1)}$

Mit diesen Annahmen können die Punktlokalisierung eines gegebenen Punktes (dh das Bestimmen der Zelle, die enthalten würde ), Einfüge- und Löschoperationen alle rechtzeitig durchgeführt werden (dh die Zeit, die benötigt wird, um eine Suche in der zugrunde liegenden geordneten Satzdatenstruktur durchzuführen). ${\displaystyle q}$${\displaystyle q}$${\displaystyle O(\log{n})}$

So führen Sie eine Punktpositionierung durch (dh suchen Sie ihre Zelle im komprimierten Baum): ${\displaystyle q}$

1. Suchen Sie die vorhandene Zelle im komprimierten Baum, die in der Z- Reihenfolge vorkommt. Rufen Sie diese Zelle an .${\displaystyle q}$${\displaystyle v}$
2. Wenn , zurück .${\displaystyle q\in v}$${\displaystyle v}$
3. Finden Sie andernfalls den niedrigsten gemeinsamen Vorfahren des Punktes und der Zelle in einem unkomprimierten Quadtree. Nennen Sie diese Vorfahrenzelle .${\displaystyle q}$${\displaystyle v}$${\displaystyle u}$
4. Suchen Sie die vorhandene Zelle im komprimierten Baum, die in der Z- Reihenfolge vorkommt, und geben Sie sie zurück.${\displaystyle u}$

Ohne auf spezifische Details einzugehen, machen wir zum Einfügen und Löschen zuerst eine Punktposition für das Ding, das wir einfügen/löschen möchten, und dann einfügen/löschen. Es muss darauf geachtet werden, den Baum entsprechend umzuformen und Knoten nach Bedarf zu erstellen und zu entfernen.

Einige gebräuchliche Verwendungen von Quadtrees

• Bilddarstellung
  
• Bildverarbeitung
• Netzgenerierung
• Räumliche Indizierung , Punktstandortabfragen und Bereichsabfragen
• Effiziente Kollisionserkennung in zwei Dimensionen
• Frustum-Culling von Geländedaten anzeigen
• Speichern von Daten mit geringer Dichte, z. B. Formatierungsinformationen für eine Tabellenkalkulation oder für einige Matrixberechnungen
• Lösung mehrdimensionaler Felder ( Computational Fluid Dynamics , Elektromagnetismus )
• Conways Game of Life- Simulationsprogramm.
• Zustandsschätzung
• Quadtrees werden auch im Bereich der fraktalen Bildanalyse eingesetzt
• Maximale disjunkte Mengen

Bildverarbeitung mit Quadtrees

Quadtrees, insbesondere die Region quadtree , haben sich gut für Bildverarbeitungsanwendungen geliehen. Wir werden unsere Diskussion auf binäre Bilddaten beschränken, obwohl Bereichs-Quadtrees und die an ihnen durchgeführten Bildverarbeitungsoperationen für Farbbilder genauso geeignet sind.

Bildvereinigung / Schnittmenge

Einer der Vorteile der Verwendung von Quadtrees für die Bildbearbeitung besteht darin, dass die Mengenoperationen von Vereinigung und Schnitt einfach und schnell durchgeführt werden können. Bei zwei binären Bildern erzeugt die Bildvereinigung (auch Overlay genannt ) ein Bild, bei dem ein Pixel schwarz ist, wenn eines der Eingabebilder ein schwarzes Pixel an derselben Stelle hat. Das heißt, ein Pixel im Ausgabebild ist nur dann weiß, wenn das entsprechende Pixel in beiden Eingabebildern weiß ist, andernfalls ist das Ausgabepixel schwarz. Anstatt die Operation Pixel für Pixel durchzuführen, können wir die Vereinigung effizienter berechnen, indem wir die Fähigkeit des Quadtree nutzen, mehrere Pixel mit einem einzigen Knoten darzustellen. Wenn ein Unterbaum sowohl schwarze als auch weiße Pixel enthält, sagen wir zum Zwecke der Erörterung unten, dass die Wurzel dieses Unterbaums grau gefärbt ist.

Der Algorithmus arbeitet, indem er die beiden Eingabe-Quadtrees ( und ) durchläuft, während der Ausgabe-Quadtree erstellt wird . Informell ist der Algorithmus wie folgt. Betrachten Sie die Knoten und entsprechen derselben Region in den Bildern. ${\displaystyle T_{1}}$${\displaystyle T_{2}}$${\displaystyle T}$${\displaystyle v_{1}\in T_{1}}$${\displaystyle v_{2}\in T_{2}}$

• Wenn oder schwarz ist, wird der entsprechende Knoten erstellt und schwarz gefärbt. Wenn nur einer von ihnen schwarz und der andere grau ist, enthält der graue Knoten einen Unterbaum darunter. Dieser Teilbaum muss nicht durchlaufen werden.${\displaystyle v_{1}}$${\displaystyle v_{2}}$${\displaystyle T}$
• Wenn (bzw. ) weiß ist, (bzw. ) und der darunter liegende Teilbaum (sofern vorhanden) nach kopiert wird .${\displaystyle v_{1}}$${\displaystyle v_{2}}$${\displaystyle v_{2}}$${\displaystyle v_{1}}$${\displaystyle T}$
• Wenn beide und grau sind, werden die entsprechenden Kinder von und berücksichtigt.${\displaystyle v_{1}}$${\displaystyle v_{2}}$${\displaystyle v_{1}}$${\displaystyle v_{2}}$

Obwohl dieser Algorithmus funktioniert, garantiert er allein keinen Quadtree mit minimaler Größe. Betrachten wir zum Beispiel das Ergebnis, wenn wir ein Schachbrett (wobei jede Kachel ein Pixel ist) der Größe mit seinem Komplement vereinen würden. Das Ergebnis ist ein riesiges schwarzes Quadrat, das durch einen Quadtree mit nur dem Wurzelknoten (schwarz gefärbt) dargestellt werden sollte, aber stattdessen erzeugt der Algorithmus einen vollständigen 4-ären Baum der Tiefe . Um dies zu beheben, führen wir eine Bottom-Up-Durchquerung des resultierenden Quadtree durch, bei der wir prüfen, ob die vier Kinderknoten die gleiche Farbe haben. In diesem Fall ersetzen wir ihren Elternknoten durch ein Blatt der gleichen Farbe. ${\displaystyle 2^{k}\times 2^{k}}$${\displaystyle k}$

Die Schnittmenge zweier Bilder ist fast der gleiche Algorithmus. Eine Möglichkeit, über den Schnittpunkt der beiden Bilder nachzudenken, besteht darin, dass wir eine Vereinigung in Bezug auf die weißen Pixel vornehmen. Um die Schnittmenge durchzuführen, tauschen wir die Erwähnungen von Schwarz und Weiß im Vereinigungsalgorithmus aus.

Kennzeichnung der angeschlossenen Komponenten

Betrachten Sie zwei benachbarte schwarze Pixel in einem Binärbild. Sie sind benachbart, wenn sie eine begrenzende horizontale oder vertikale Kante haben. Im Allgemeinen sind zwei schwarze Pixel verbunden, wenn eines vom anderen erreicht werden kann, indem man sich nur zu benachbarten Pixeln bewegt (dh es gibt einen Pfad von schwarzen Pixeln zwischen ihnen, wo jedes aufeinanderfolgende Paar benachbart ist). Jeder maximale Satz verbundener schwarzer Pixel ist eine verbundene Komponente . Anhand der Quadtree-Darstellung von Bildern zeigte Samet , wie wir diese zusammenhängenden Komponenten in der Zeit proportional zur Größe des Quadtree finden und beschriften können. Dieser Algorithmus kann auch für die Polygonfärbung verwendet werden.

Der Algorithmus funktioniert in drei Schritten:

• Legen Sie die Nachbarschaftsbeziehungen zwischen schwarzen Pixeln fest
• Verarbeiten Sie die Äquivalenzrelationen aus dem ersten Schritt, um ein eindeutiges Label für jede verbundene Komponente zu erhalten
• beschrifte die schwarzen Pixel mit dem Label, das ihrer verbundenen Komponente zugeordnet ist

Um die Diskussion zu vereinfachen, nehmen wir an, die Kinder eines Knotens im Quadtree folgen der Z- Ordnung (SW, NW, SE, NE). Da wir uns auf diese Struktur verlassen können, wissen wir für jede Zelle, wie wir durch den Quadtree navigieren, um die benachbarten Zellen in den verschiedenen Hierarchieebenen zu finden.

Schritt eins wird mit einer Post-Order-Traversierung des Quadtree erreicht. Für jedes schwarze Blatt betrachten wir den Knoten oder die Knoten, die Zellen darstellen, die nördliche Nachbarn und östliche Nachbarn sind (dh die nördlichen und östlichen Zellen, die Kanten mit der Zelle von teilen ). Da der Baum in Z- Reihenfolge organisiert ist, haben wir die Invariante, dass die südlichen und westlichen Nachbarn bereits berücksichtigt und berücksichtigt wurden. Seien Sie der derzeit betrachtete nördliche oder östliche Nachbar . Steht für schwarze Pixel: ${\displaystyle v}$${\displaystyle v}$${\displaystyle u}$${\displaystyle u}$

• Wenn nur eines von oder ein Label hat, weisen Sie dieses Label der anderen Zelle zu${\displaystyle u}$${\displaystyle v}$
• Wenn keines von beiden Labels hat, erstellen Sie eines und weisen Sie es beiden zu
• Wenn und unterschiedliche Labels haben, notieren Sie diese Label-Äquivalenz und fahren Sie fort${\displaystyle u}$${\displaystyle v}$

Schritt zwei kann mit der union-find-Datenstruktur durchgeführt werden . Wir beginnen mit jedem einzigartigen Etikett als separates Set. Für jede im ersten Schritt notierte Äquivalenzrelation vereinigen wir die entsprechenden Mengen. Danach wird jeder unterschiedliche verbleibende Satz mit einer unterschiedlichen verbundenen Komponente im Bild verknüpft.

Schritt drei führt eine weitere Post-Order-Traversierung durch. Dieses Mal verwenden wir für jeden schwarzen Knoten die Find- Operation von union-find (mit dem alten Label von ), um sein neues Label zu finden und zuzuweisen (das mit der verbundenen Komponente verbunden ist, von der ein Teil ist). ${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$

Netzgenerierung mit Quadtrees

Dieser Abschnitt fasst ein Kapitel aus einem Buch von Har-Peled und de Berg et al.

Die Netzgenerierung ist im Wesentlichen die Triangulation einer Punktmenge, für die eine weitere Verarbeitung durchgeführt werden kann. Daher ist es wünschenswert, dass die resultierende Triangulation bestimmte Eigenschaften hat (wie Ungleichmäßigkeit, Dreiecke, die nicht "zu dünn sind", große Dreiecke in spärlichen Bereichen und kleine Dreiecke in dichten Bereichen usw.), um die Weiterverarbeitung zu beschleunigen und weniger fehleranfällig. Quadtrees, die auf der Punktmenge erstellt wurden, können verwendet werden, um Netze mit diesen gewünschten Eigenschaften zu erstellen.

Ein ausgeglichenes Blatt hat höchstens eine Ecke an einer Seite.

Betrachten Sie ein Blatt des Quadtree und seine entsprechende Zelle . Wir sagen , ist ausgeglichen (für Netzgenerierung) , wenn die Seiten der Zelle durch die Eckpunkte von benachbarten Zellen höchstens einmal auf jeder Seite geschnitten werden. Das bedeutet, dass sich die Quadtree-Ebenen der angrenzenden Blätter um höchstens eins von der Ebene von unterscheiden . Wenn dies für alle Blätter gilt, sagen wir, dass der gesamte Quadtree ausgeglichen ist (für die Netzgenerierung). ${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$

Betrachten Sie die Zelle und die Nachbarschaft von gleich großen Zellen, die bei zentriert sind . Wir nennen diese Nachbarschaft den erweiterten Cluster . Wir sagen, der Quadtree ist ausgeglichen, wenn er ausgeglichen ist, und für jedes Blatt , das einen Punkt der Punktmenge enthält, befindet sich auch sein erweiterter Cluster im Quadtree und der erweiterte Cluster enthält keinen anderen Punkt der Punktmenge. ${\displaystyle v}$${\displaystyle 5\times 5}$${\displaystyle v}$${\displaystyle u}$

Das Erstellen des Netzes erfolgt wie folgt:

1. Erstellen Sie einen Quadtree auf den Eingabepunkten.
2. Stellen Sie sicher, dass der Quadtree ausgeglichen ist. Unterteilen Sie für jedes Blatt, wenn es einen Nachbarn gibt, der zu groß ist, den Nachbarn. Dies wird wiederholt, bis der Baum ausgeglichen ist. Wir stellen außerdem sicher, dass sich für ein Blatt mit einem Punkt darin die Knoten für den erweiterten Cluster jedes Blatts im Baum befinden.
3. Wenn der erweiterte Cluster einen weiteren Punkt enthält, unterteilen wir für jeden Blattknoten , der einen Punkt enthält, den Baum weiter und gleichen es nach Bedarf neu aus. Wenn wir unterteilen müssen, stellen wir für jedes Kind von sicher sicher, dass sich die Knoten des erweiterten Clusters von im Baum befinden (und nach Bedarf neu ausbalancieren).${\displaystyle v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle u}$
4. Wiederholen Sie den vorherigen Schritt, bis der Baum gut ausbalanciert ist.
5. Verwandle den Quadtree in eine Triangulation.

Wir betrachten die Eckpunkte der Baumzellen als Eckpunkte in unserer Triangulation. Vor dem Transformationsschritt haben wir eine Reihe von Kästchen mit Punkten in einigen von ihnen. Der Transformationsschritt wird auf folgende Weise durchgeführt: Krümmen Sie für jeden Punkt die nächste Ecke seiner Zelle, um ihn zu treffen, und triangulieren Sie die resultierenden vier Vierecke, um "schöne" Dreiecke zu erhalten (der interessierte Leser wird auf Kapitel 12 von Har-Peled verwiesen für mehr Details darüber, was "schöne" Dreiecke ausmacht).

Die restlichen Quadrate werden nach einigen einfachen Regeln trianguliert. Führe für jedes regelmäßige Quadrat (keine Punkte innerhalb und keine Eckpunkte in seinen Seiten) die Diagonale ein. Beachten Sie, dass aufgrund der Art und Weise, in der wir Punkte mit der Eigenschaft "Well-Balancing" getrennt haben, kein Quadrat mit einer Ecke, die eine Seite schneidet, verzerrt ist. Als solche können wir Quadrate mit sich schneidenden Ecken wie folgt triangulieren. Wenn es eine geschnittene Seite gibt, wird das Quadrat zu drei Dreiecken, indem die langen Diagonalen hinzugefügt werden, die den Schnittpunkt mit gegenüberliegenden Ecken verbinden. Wenn es vier sich schneidende Seiten gibt, teilen wir das Quadrat in zwei Hälften, indem wir eine Kante zwischen zwei der vier Schnittpunkte hinzufügen und dann diese beiden Endpunkte mit den verbleibenden zwei Schnittpunkten verbinden. Für die anderen Quadrate führen wir einen Punkt in der Mitte ein und verbinden ihn mit allen vier Ecken des Quadrats sowie jedem Schnittpunkt.

Am Ende haben wir ein schönes trianguliertes Netz unserer Punktmenge, das aus einem Quadtree aufgebaut ist.

Pseudocode

Der folgende Pseudocode zeigt eine Möglichkeit, einen Quadtree zu implementieren, der nur Punkte behandelt. Es gibt andere Ansätze.

Voraussetzungen

Es wird davon ausgegangen, dass diese Strukturen verwendet werden.

// Simple coordinate object to represent points and vectors
struct XY
{
    float x;
    float y;

    function __construct(float _x, float _y) {...}
}

// Axis-aligned bounding box with half dimension and center
struct AABB
{
    XY center;
    float halfDimension;

    function __construct(XY center, float halfDimension) {...}
    function containsPoint(XY point) {...}
    function intersectsAABB(AABB other) {...}
}

QuadTree-Klasse

Diese Klasse repräsentiert sowohl einen Quad-Baum als auch den Knoten, in dem er verwurzelt ist.

class QuadTree
{
    // Arbitrary constant to indicate how many elements can be stored in this quad tree node
    constant int QT_NODE_CAPACITY = 4;

    // Axis-aligned bounding box stored as a center with half-dimensions
    // to represent the boundaries of this quad tree
    AABB boundary;

    // Points in this quad tree node
    Array of XY [size = QT_NODE_CAPACITY] points;

    // Children
    QuadTree* northWest;
    QuadTree* northEast;
    QuadTree* southWest;
    QuadTree* southEast;

    // Methods
    function __construct(AABB _boundary) {...}
    function insert(XY p) {...}
    function subdivide() {...} // create four children that fully divide this quad into four quads of equal area
    function queryRange(AABB range) {...}
}

Einfügen

Die folgende Methode fügt einen Punkt in das entsprechende Quad eines Quadtree ein und teilt ihn gegebenenfalls auf.

class QuadTree
{
    ...
  
    // Insert a point into the QuadTree
    function insert(XY p)
    {
        // Ignore objects that do not belong in this quad tree
        if (!boundary.containsPoint(p))
            return false; // object cannot be added
    
        // If there is space in this quad tree and if doesn't have subdivisions, add the object here
        if (points.size < QT_NODE_CAPACITY && northWest == null)
        {
            points.append(p);
            return true;
        }
    
        // Otherwise, subdivide and then add the point to whichever node will accept it
        if (northWest == null)
            subdivide();
        //We have to add the points/data contained into this quad array to the new quads if we only want 
        //the last node to hold the data 
    
        if (northWest->insert(p)) return true;
        if (northEast->insert(p)) return true;
        if (southWest->insert(p)) return true;
        if (southEast->insert(p)) return true;
    
        // Otherwise, the point cannot be inserted for some unknown reason (this should never happen)
        return false;
    }
}

Abfragebereich

Die folgende Methode findet alle Punkte, die in einem Bereich enthalten sind.

class QuadTree
{
    ...
  
    // Find all points that appear within a range
    function queryRange(AABB range)
    {
        // Prepare an array of results
        Array of XY pointsInRange;
    
        // Automatically abort if the range does not intersect this quad
        if (!boundary.intersectsAABB(range))
            return pointsInRange; // empty list
    
        // Check objects at this quad level
        for (int p = 0; p < points.size; p++)
        {
            if (range.containsPoint(points[p]))
                pointsInRange.append(points[p]);
        }
    
        // Terminate here, if there are no children
        if (northWest == null)
            return pointsInRange;
    
        // Otherwise, add the points from the children
        pointsInRange.appendArray(northWest->queryRange(range));
        pointsInRange.appendArray(northEast->queryRange(range));
        pointsInRange.appendArray(southWest->queryRange(range));
        pointsInRange.appendArray(southEast->queryRange(range));
    
        return pointsInRange;
    }
}

Siehe auch

• Adaptive Netzverfeinerung
• Binäre Raumpartitionierung
• Binäre Kacheln
• Kd-Baum
• Octree
• R-Baum
• UB-Baum
• Räumliche Datenbank
• Unterpflasterung
• Kurve Z-Ordnung

Verweise

Umfragen von Aluru und Samet geben einen schönen Überblick über Quadtrees.

Anmerkungen

Allgemeine Referenzen

1. Raphael Finkel und JL Bentley (1974). „Quad Trees: Eine Datenstruktur zum Abrufen auf zusammengesetzten Schlüsseln“. Acta Informatica . 4 (1): 1–9. doi : 10.1007/BF00288933 . S2CID  33019699 .
2. Mark de Berg , Marc van Kreveld , Mark Overmars und Otfried Schwarzkopf (2000). Computational Geometry (2. überarbeitete Aufl.). Springer-Verlag . ISBN 3-540-65620-0.CS1-Pflege: mehrere Namen: Autorenliste ( Link ) Kapitel 14: Quadtrees: S. 291–306.
3. Samet, Hanan ; Webber, Robert (Juli 1985). "Speichern einer Sammlung von Polygonen mit Quadtrees" (PDF) . Abgerufen am 23. März 2012 .