Quadtree
Quadtree | ||||
---|---|---|---|---|
Typ | Träd | |||
Uppfunnet | 1974 | |||
Uppfunnet av | Raphael Finkel och JL Bentley | |||
Tidskomplexitet i stor O-notation | ||||
|
Ett quadtree är en träddatastruktur där varje intern nod har exakt fyra barn. Quadtrees är den tvådimensionella analogen av oktrees och används oftast för att dela upp ett tvådimensionellt utrymme genom att rekursivt dela upp det i fyra kvadranter eller regioner. Data som är associerade med en bladcell varierar beroende på tillämpning, men bladcellen representerar en "enhet av intressant rumslig information".
De uppdelade områdena kan vara kvadratiska eller rektangulära, eller kan ha godtyckliga former. Denna datastruktur kallades ett quadtree av Raphael Finkel och JL Bentley 1974. En liknande partitionering är också känd som ett Q-tree . Alla former av quadtrees delar några gemensamma egenskaper:
- De bryter ner rymden till anpassningsbara celler
- Varje cell (eller hink) har en maximal kapacitet. När maximal kapacitet uppnås delas skopan
- Trädkatalogen följer den rumsliga nedbrytningen av quadtreet.
En trädpyramid ( T-pyramid ) är ett "komplett" träd; varje nod i T-pyramiden har fyra barnnoder utom bladnoder; alla blad är på samma nivå, nivån som motsvarar enskilda pixlar i bilden. Data i en trädpyramid kan lagras kompakt i en array som en implicit datastruktur som liknar hur ett komplett binärt träd kan lagras kompakt i en array .
Typer
Quadtrees kan klassificeras enligt vilken typ av data de representerar, inklusive områden, punkter, linjer och kurvor. Quadtrees kan också klassificeras efter huruvida formen på trädet är oberoende av i vilken ordning data behandlas. Följande är vanliga typer av quadtrees.
Region quadtree
Regionkvadrträdet representerar en uppdelning av rymden i två dimensioner genom att sönderdela regionen i fyra lika stora kvadranter, subkvadranter och så vidare med varje lövnod som innehåller data som motsvarar en specifik subregion. Varje nod i trädet har antingen exakt fyra barn, eller har inga barn (en lövnod). Höjden på quadtrees som följer denna nedbrytningsstrategi (dvs. dela upp subkvadranter så länge det finns intressanta data i subkvadranten för vilka mer förfining önskas) är känslig för och beroende av den rumsliga fördelningen av intressanta områden i det utrymme som bryts ned. Regionen quadtree är en typ av trie .
Ett områdesquadtree med ett djup på n kan användas för att representera en bild som består av 2 n × 2 n pixlar, där varje pixelvärde är 0 eller 1. Rotnoden representerar hela bildområdet. Om pixlarna i någon region inte är helt 0:or eller 1:or, delas den upp. I den här applikationen representerar varje bladnod ett block med pixlar som alla är 0:or eller alla 1:or. Notera de potentiella besparingarna i form av utrymme när dessa träd används för att lagra bilder; bilder har ofta många områden av betydande storlek som har samma färgvärde genomgående. Istället för att lagra en stor 2-D-array av varje pixel i bilden, kan ett quadtree fånga samma information som potentiellt många uppdelningsnivåer är högre än de pixelupplösningsstorlekar som vi annars skulle behöva. Trädupplösningen och den totala storleken begränsas av pixel- och bildstorlekarna.
Ett områdesquadtree kan också användas som en representation med variabel upplösning av ett datafält. Till exempel kan temperaturerna i ett område lagras som ett fyrträd, där varje lövnod lagrar medeltemperaturen över den delregion den representerar.
Punkt quadtree
Punktkvadrträdet är en anpassning av ett binärt träd som används för att representera tvådimensionella punktdata. Den delar egenskaperna hos alla quadtrees men är ett sant träd eftersom mitten av en underavdelning alltid är på en punkt. Det är ofta mycket effektivt att jämföra tvådimensionella, ordnade datapunkter, vanligtvis i O(log n) -tid. Point quadtrees är värda att nämna för fullständighetens skull, men de har överträffats av k -d-träd som verktyg för generaliserad binär sökning.
Punkt quadtrees är konstruerade enligt följande. Med tanke på nästa punkt att infoga hittar vi cellen där den ligger och lägger till den i trädet. Den nya punkten läggs till så att cellen som innehåller den delas in i kvadranter av de vertikala och horisontella linjerna som går genom punkten. Följaktligen är celler rektangulära men inte nödvändigtvis kvadratiska. I dessa träd innehåller varje nod en av ingångspunkterna.
Eftersom indelningen av planet bestäms av punktinsättningsordningen är trädets höjd känslig för och beroende av insättningsordningen. Att infoga i en "dålig" ordning kan leda till ett träd med höjd linjär i antalet inmatningspunkter (vid vilken punkt det blir en länkad lista). Om punktuppsättningen är statisk kan förbearbetning göras för att skapa ett träd med balanserad höjd.
Nodstruktur för ett punktfyrträd
En nod i ett punktkvadrant liknar en nod i ett binärt träd , med den stora skillnaden är att den har fyra pekare (en för varje kvadrant) istället för två ("vänster" och "höger") som i ett vanligt binärt träd . Också en nyckel är vanligtvis uppdelad i två delar, med hänvisning till x- och y-koordinater. Därför innehåller en nod följande information:
- fyra pekare: quad['NW'], quad['NE'], quad['SW'] och quad['SE']
- punkt; som i sin tur innehåller:
- nyckel; uttrycks vanligtvis som x, y-koordinater
- värde; till exempel ett namn
Punkt-region (PR) quadtree
Punkt-region (PR) quadtrees är mycket lika region quadtrees. Skillnaden är vilken typ av information som lagras om cellerna. I en region quadtree lagras ett enhetligt värde som gäller för hela arean av cellen i ett blad. Cellerna i ett PR-quadtree lagrar dock en lista över punkter som finns i cellen i ett blad. Som tidigare nämnts, för träd som följer denna nedbrytningsstrategi beror höjden på den rumsliga fördelningen av punkterna. Liksom punktkvadrträdet kan PR-kvadrträdet också ha en linjär höjd när det ges en "dålig" uppsättning.
Edge quadtree
Edge quadtrees (ungefär som PM quadtrees) används för att lagra linjer snarare än punkter. Kurvor approximeras genom att dela upp celler till en mycket fin upplösning, speciellt tills det finns ett enda linjesegment per cell. Nära hörn/hörn kommer kantfyrträd fortsätta att dela sig tills de når sin maximala nedbrytningsnivå. Detta kan resultera i extremt obalanserade träd som kan motverka syftet med indexering.
Polygonal karta (PM) quadtree
Den polygonala kartan quadtree (eller PM Quadtree) är en variant av quadtree som används för att lagra samlingar av polygoner som kan vara degenererade (vilket betyder att de har isolerade hörn eller kanter). En stor skillnad mellan PM-quadtrees och edge-quadtrees är att den aktuella cellen inte delas upp om segmenten möts vid en vertex i cellen.
Det finns tre huvudklasser av PM Quadtrees, som varierar beroende på vilken information de lagrar inom varje svart nod. PM3 quadtrees kan lagra valfri mängd icke-korsande kanter och högst en punkt. PM2 quadtrees är samma som PM3 quadtrees förutom att alla kanter måste dela samma slutpunkt. Slutligen liknar PM1-quadtrees PM2, men svarta noder kan innehålla en punkt och dess kanter eller bara en uppsättning kanter som delar en punkt, men du kan inte ha en punkt och en uppsättning kanter som inte innehåller punkten.
Komprimerade quadtrees
Det här avsnittet sammanfattar ett underavsnitt från en bok av Sariel Har-Peled .
Om vi skulle lagra varje nod som motsvarar en uppdelad cell, kan det sluta med att vi lagrar många tomma noder. Vi kan skära ner på storleken på sådana glesa träd genom att bara lagra underträd vars löv har intressanta data (dvs. "viktiga underträd"). Vi kan faktiskt skära ner på storleken ytterligare. När vi bara behåller viktiga underträd kan beskärningsprocessen lämna långa vägar i trädet där de mellanliggande noderna har grad två (en länk till en förälder och ett barn). Det visar sig att vi bara behöver lagra noden i början av denna sökväg (och associera lite metadata till den för att representera de borttagna noderna) och fästa underträdet som är rotat i dess ände till u . Det är fortfarande möjligt för dessa komprimerade träd att ha en linjär höjd när de ges "dåliga" ingångspunkter.
Även om vi trimmar mycket av trädet när vi utför den här komprimeringen, är det fortfarande möjligt att uppnå logaritmisk tidssökning, infogning och radering genom att dra fördel av Z -ordningskurvor . Z - ordningens kurva mappar varje cell i det fullständiga fyrträdet (och därmed även det komprimerade fyrträdet) i tid till en endimensionell linje (och mappar tillbaka den i tid också), vilket skapar en total ordning på elementen. Därför kan vi lagra quadtree i en datastruktur för ordnade uppsättningar (där vi lagrar trädets noder).
Vi måste ange ett rimligt antagande innan vi fortsätter: vi antar att givet två reella tal uttryckt som binärt, kan vi beräkna i tid indexet för den första biten där de skiljer sig åt. Vi antar också att vi i kan beräkna den lägsta gemensamma förfadern för två punkter/celler i fyrträdet och fastställa deras relativa Z -ordning, och vi kan beräkna golvfunktionen i tid.
Med dessa antaganden kan punktplacering av en given punkt (dvs. bestämma cellen som skulle innehålla ), infogning och raderingsoperationer alla utföras i tid (dvs tiden det tar att göra en sökning i den underliggande ordnade uppsättningsdatastrukturen).
För att utföra en punktplacering för (dvs hitta dess cell i det komprimerade trädet):
- Hitta den befintliga cellen i det komprimerade trädet som kommer före i Z -ordningen. Kalla denna cell .
- Om , returnera .
- Annars, hitta vad som skulle ha varit den lägsta gemensamma förfadern till punkten och cellen i ett okomprimerat quadtree. Kalla denna förfadercell .
- Hitta den befintliga cellen i det komprimerade trädet som kommer före i Z -ordningen och returnera den.
Utan att gå in på specifika detaljer, för att utföra infogning och radering gör vi först en punktplacering för det vi vill infoga/ta bort och sedan infogar/raderar det. Försiktighet måste vidtas för att omforma trädet efter behov, skapa och ta bort noder efter behov.
Några vanliga användningsområden för quadtrees
- Bildrepresentation
- Bildbehandling
- Mesh generation
- Rumslig indexering , punktpositionsfrågor och intervallfrågor
- Effektiv kollisionsdetektering i två dimensioner
- Visa frustum utrangering av terrängdata
- Lagring av glesa data, till exempel formateringsinformation för ett kalkylblad eller för vissa matrisberäkningar [ citat behövs ]
- Lösning av flerdimensionella fält ( beräkningsvätskedynamik , elektromagnetism )
- Conways Game of Life- simuleringsprogram.
- Statlig uppskattning
- Quadtrees används också inom området fraktal bildanalys
- Maximala disjunkta uppsättningar
Bildbehandling med quadtrees
Quadtrees, särskilt regionen quadtree , har lämpat sig väl för bildbehandlingstillämpningar. Vi kommer att begränsa vår diskussion till binära bilddata, även om regionsquadtrees och bildbehandlingsoperationerna som utförs på dem är lika lämpliga för färgbilder.
Bildförening/korsning
En av fördelarna med att använda quadtrees för bildmanipulation är att inställningsoperationerna union och intersection kan göras enkelt och snabbt. Givet två binära bilder, producerar bildunionen (även kallad överlagring ) en bild där en pixel är svart om någon av ingångsbilderna har en svart pixel på samma plats. Det vill säga, en pixel i utmatningsbilden är vit endast när motsvarande pixel i båda ingångsbilderna är vit, annars är utdatapixeln svart. Istället för att göra operationen pixel för pixel, kan vi beräkna unionen mer effektivt genom att utnyttja quadtreeets förmåga att representera flera pixlar med en enda nod. För diskussionsändamål nedan, om ett underträd innehåller både svarta och vita pixlar kommer vi att säga att roten till det underträdet är färgad grå.
Algoritmen fungerar genom att korsa de två ingående kvadträden ( och ) samtidigt som utdatakvadrträdet . Informellt är algoritmen följande. Betrakta noderna och som motsvarar samma region i bilderna .
- Om eller är svart, skapas motsvarande nod i och färgas svart. Om bara en av dem är svart och den andra är grå, kommer den grå noden att innehålla ett underträd under. Detta underträd behöver inte passeras.
- Om (respektive ) är vit, (respektive ) och underträdet under det (om det finns) kopieras till .
- Om både och är grå, då är motsvarande barn till och övervägs.
Även om den här algoritmen fungerar, garanterar den inte i sig ett fyrträd i minimal storlek. Tänk till exempel på resultatet om vi skulle förena ett schackbräde (där varje bricka är en pixel) med storleken med dess komplement. Resultatet är en gigantisk svart fyrkant som ska representeras av ett fyrträd med bara rotnoden (färgad svart), men istället producerar algoritmen ett helt 4-arigt träd med djup k {\displaystyle . För att fixa detta utför vi en genomgång nerifrån och upp av det resulterande fyrträdet där vi kontrollerar om de fyra barnnoderna har samma färg, i så fall ersätter vi deras förälder med ett löv av samma färg.
Skärningspunkten mellan två bilder är nästan samma algoritm. Ett sätt att tänka på skärningspunkten mellan de två bilderna är att vi gör en förening med avseende på de vita pixlarna. Som sådan byter vi omnämnanden av svart och vitt i unionsalgoritmen för att utföra korsningen.
Märkning av anslutna komponenter
Betrakta två angränsande svarta pixlar i en binär bild. De ligger intill om de delar en avgränsande horisontell eller vertikal kant. I allmänhet är två svarta pixlar anslutna om den ena kan nås från den andra genom att endast flytta till intilliggande pixlar (dvs. det finns en väg av svarta pixlar mellan dem där varje på varandra följande par är intill). Varje maximal uppsättning anslutna svarta pixlar är en ansluten komponent . Med hjälp av quadtree-representationen av bilder Samet hur vi kan hitta och märka dessa anslutna komponenter i tid proportionell mot storleken på quadtree. Denna algoritm kan också användas för polygonfärgning.
Algoritmen fungerar i tre steg:
- fastställa närliggande relationer mellan svarta pixlar
- bearbeta ekvivalensrelationerna från det första steget för att erhålla en unik etikett för varje ansluten komponent
- märk de svarta pixlarna med etiketten som är kopplad till deras anslutna komponent
För att förenkla diskussionen, låt oss anta att barnen i en nod i quadtree följer Z -ordningen (SW, NW, SE, NE). Eftersom vi kan lita på denna struktur, vet vi för alla celler hur vi navigerar i fyrträdet för att hitta de intilliggande cellerna i hierarkins olika nivåer.
Steg ett uppnås med en post-order genomgång av quadtree. För varje svart blad tittar vi på noden eller noderna som representerar celler som är norra grannar och östra grannar (dvs. de norra och östra cellerna som delar kanter med cellen i ). Eftersom trädet är organiserat i Z -ordning, har vi den invariant som de södra och västra grannarna redan har tagits om hand och redovisats för. Låt den norra eller östra grannen som för närvarande övervägs vara . Om representerar svarta pixlar:
- Om bara en av eller har en etikett, tilldela den etiketten till den andra cellen
- Om ingen av dem har etiketter, skapa en och tilldela dem båda
- Om och har olika etiketter, registrera denna etikettekvivalens och gå vidare
Steg två kan utföras med hjälp av union-find-datastrukturen . Vi börjar med varje unik etikett som en separat uppsättning. För varje ekvivalensrelation som noteras i det första steget förenar vi motsvarande uppsättningar. Efteråt kommer varje distinkt återstående uppsättning att associeras med en distinkt ansluten komponent i bilden.
Steg tre utför ytterligare en genomgång efter beställning. Den här gången, för varje svart nod använder vi union-finds sökoperation (med den gamla etiketten ) för att hitta och tilldela dess nya etikett (associerad med den anslutna komponenten som är en del av).
Mesh-generering med quadtrees
Detta avsnitt sammanfattar ett kapitel från en bok av Har-Peled och de Berg et al.
Mesh-generering är i huvudsak trianguleringen av en punktuppsättning för vilken ytterligare bearbetning kan utföras. Som sådan är det önskvärt att den resulterande trianguleringen har vissa egenskaper (som olikformighet, trianglar som inte är "för smala", stora trianglar i glesa områden och små trianglar i täta, etc.) för att göra vidare bearbetning snabbare och mindre felbenägen. Quadtrees byggda på punktuppsättningen kan användas för att skapa maskor med dessa önskade egenskaper.
Betrakta ett blad av quadtree och dess motsvarande cell . Vi säger att är balanserad (för mesh-generering) om cellens sidor skärs av hörnpunkterna för närliggande celler högst en gång på varje sida. Detta betyder att quadtree-nivåerna för löv intill skiljer sig med högst en från nivån för . När detta är sant för alla löv, säger vi att hela quadtree är balanserat (för mesh-generering).
Betrakta cellen och -området för celler av samma storlek centrerade på . Vi kallar denna stadsdel för det utökade klustret . Vi säger att fyrträdet är välbalanserat om det är balanserat, och för varje blad som innehåller en punkt i punktuppsättningen, är dess utökade kluster också i fyrträdet och det utökade klustret innehåller ingen annan punkt i punktuppsättning.
Att skapa nätet görs på följande sätt:
- Bygg ett quadtree på ingångspunkterna.
- Se till att quadtree är balanserad. För varje löv, om det finns en granne som är för stor, dela upp grannen. Detta upprepas tills trädet är balanserat. Vi ser också till att för ett löv med en spets i, är noderna för varje blads förlängda kluster i trädet.
- För varje lövnod som innehåller en punkt, om det utökade klustret innehåller ytterligare en punkt, delar vi upp trädet ytterligare och balanserar om efter behov. Om vi behövde dela upp, för varje barn av säkerställer vi att noderna för s utökade kluster finns i trädet (och balanserar om efter behov).
- Upprepa föregående steg tills trädet är välbalanserat.
- Förvandla quadtree till en triangulering.
Vi betraktar trädcellernas hörnpunkter som hörn i vår triangulering. Innan transformationssteget har vi ett gäng lådor med poäng i några av dem. Transformationssteget görs på följande sätt: för varje punkt, förvräng det närmaste hörnet av dess cell för att möta den och triangulera de resulterande fyra fyrkanterna för att göra "fina" trianglar (den intresserade läsaren hänvisas till kapitel 12 i Har-Peled för att mer information om vad som gör "fina" trianglar).
De återstående rutorna trianguleras enligt några enkla regler. För varje vanlig kvadrat (inga punkter inom och inga hörnpunkter på dess sidor), introducera diagonalen. Observera att på grund av det sätt på vilket vi separerade punkter med den välbalanserande egenskapen, är ingen kvadrat med ett hörn som skär en sida en som var skev. Som sådan kan vi triangulera kvadrater med korsande hörn enligt följande. Om det finns en genomskuren sida blir kvadraten tre trianglar genom att lägga till de långa diagonalerna som förbinder skärningen med motsatta hörn. Om det finns fyra korsade sidor delar vi kvadraten på mitten genom att lägga till en kant mellan två av de fyra skärningspunkterna och kopplar sedan samman dessa två ändpunkter med de återstående två skärningspunkterna. För de andra kvadraterna introducerar vi en punkt i mitten och kopplar den till alla fyra hörn av kvadraten samt varje skärningspunkt.
I slutet av det hela har vi ett fint triangulerat nät av vår punktuppsättning byggd av ett quadtree.
Pseudokod
Följande pseudokod visar ett sätt att implementera ett quadtree som endast hanterar punkter. Det finns andra tillvägagångssätt.
Förutsättningar
Det antas att dessa strukturer används.
// Enkelt koordinatobjekt för att representera punkter och vektorer struktur XY { float x; flyta y; function __construct( float _x, float _y) {...} } // Axis-aligned bounding box med halvdimension och center struct AABB { XY center; flyta halvdimension; funktion __construct( XY center, float halfDimension) {...} funktion innehållerPoint( XY point) {...} funktion skär AABB( AABB annan) {...} }
QuadTree klass
Den här klassen representerar både ett quad-träd och noden där den är rotad.
class QuadTree { // Godtycklig konstant för att indikera hur många element som kan lagras i denna quad tree nod konstant int QT_NODE_CAPACITY = 4; // Axeljusterad begränsningsruta lagrad som ett centrum med halvdimensioner // för att representera gränserna för denna fyrkantiga AABB -gräns; // Poäng i denna quad tree nod Array av XY [size = QT_NODE_CAPACITY] punkter; // Barn QuadTree* nordväst; QuadTree* nordost; QuadTree* sydväst; QuadTree* sydost; // Methods function __construct( AABB _boundary) {...} function insert( XY p) {...} function subdivide() {...} // skapa fyra barn som helt delar upp denna quad i fyra quads med lika area function queryRange( AABB range) {...} }
Införande
Följande metod infogar en punkt i lämplig quad i ett quadtree, delar upp om det behövs.
class QuadTree { ... // Infoga en punkt i QuadTree- funktionen insert( XY p) { // Ignorera objekt som inte hör hemma i detta quad-träd om (!boundary.containsPoint(p)) returnerar false ; // objekt kan inte läggas till // Om det finns utrymme i detta quad-träd och om det inte har underavdelningar, lägg till objektet här if (points.size < QT_NODE_CAPACITY && northWest == null ) { points.append(p); returnera sant ; } // Annars, dela upp och lägg sedan till punkten till den nod som accepterar den if (nordväst == null ) subdivide(); // Vi måste lägga till punkterna/data som finns i denna quad-array till de nya quads om vi bara vill att // den sista noden ska innehålla data om (nordväst->insert(p)) returnerar true ; if (nordöst->insert(p)) returnerar sant ; if (sydväst->insert(p)) returnerar true ; if (sydöst->insert(p)) returnerar sant ; // Annars kan punkten inte infogas av någon okänd anledning (detta bör aldrig hända) return false ; } }
Frågeintervall
Följande metod hittar alla punkter som finns inom ett intervall.
class QuadTree { ... // Hitta alla punkter som visas inom en intervallfunktion queryRange ( AABB range) { // Förbered en array av resultat Array av XY pointsInRange; // Avbryt automatiskt om intervallet inte skär denna quad om (!boundary.intersectsAABB(range)) returnerar pointsInRange; // tom lista // Kontrollera objekt på denna quad-nivå för ( int p = 0; p < points.size; p++) { if (range.containsPoint(points[p])) pointsInRange.append(points[p]); } // Avsluta här, om det inte finns några barn om (nordväst == null ) returnerar pointsInRange; // Annars, lägg till punkterna från underordnade pointsInRange.appendArray(northWest->queryRange(range)); pointsInRange.appendArray(northEast->queryRange(range)); pointsInRange.appendArray(southWest->queryRange(range)); pointsInRange.appendArray(southEast->queryRange(range)); return pointsInRange; } }
Se även
- Adaptiv nätförfining
- Binär rymduppdelning
- Binär plattsättning
- Kd-träd
- Octree
- R-träd
- UB-träd
- Rumslig databas
- Delbeläggning
- Z-ordningskurva
Undersökningar av Aluru och Samet ger en fin överblick över fyrträd.
Anteckningar
Allmänna referenser
- Raphael Finkel och JL Bentley (1974). "Quad Trees: En datastruktur för hämtning på sammansatta nycklar". Acta Informatica . 4 (1): 1–9. doi : 10.1007/BF00288933 . S2CID 33019699 .
-
Mark de Berg , Marc van Kreveld , Mark Overmars och Otfried Schwarzkopf (2000). Computational Geometry (2:a reviderade upplagan). Springer-Verlag . ISBN 3-540-65620-0 .
{{ citera bok }}
: CS1 underhåll: flera namn: lista över författare ( länk ) Kapitel 14: Quadtrees: s. 291–306. - Samet, Hanan ; Webber, Robert (juli 1985). "Lagra en samling polygoner med hjälp av Quadtrees" (PDF) . Hämtad 23 mars 2012 .