Quadtree (även quadtree , 4-tree , engelska quadtree ) är ett träd där varje intern nod har exakt 4 avkomlingar. Quadtrees används ofta för att rekursivt dela upp ett 2D-utrymme i 4 kvadranter (regioner). Ytor är kvadrater, rektanglar eller har en godtycklig form. Den engelska termen quadtree myntades av Raphael Finkel och John Bentley .år 1974. En liknande uppdelning av rymden är känd som ett Q-träd. Vanliga egenskaper hos olika typer av quadtrees:
Quadtrees kan klassificeras efter vilken typ av data de representerar - rymd, punkter, linjer, kurvor. De kan också delas upp efter om formen på trädet beror på i vilken ordning uppgifterna behandlas. Några typer av quadtrees:
Region quadtree representerar vilken del som helst av ett tvådimensionellt utrymme genom att dela upp det i 4 kvadranter, underkvadranter och så vidare, där varje löv i trädet motsvarar ett visst område . Varje nod i trädet har antingen 4 barn, eller inga alls (löv). Space-partitionerande quadtrees är inte helt träd eftersom positionen för subkvadranterna är oberoende av data. Ett mer korrekt namn är prefix trees ( eng. try ).
Ett träd med höjden n kan användas för att representera en bild som består av 2n × 2n pixlar, där varje pixel har ett värde på 0 eller 1. Trädets rot representerar hela bildens yta. Om inte alla pixlar bara är nollor eller bara ettor går det sönder. I det här fallet motsvarar varje ark en uppsättning pixlar - antingen bara nollor eller bara ettor.
Space breaking quadtrees kan också användas för att representera den variabla upplösningen för en datamängd. Till exempel kan temperaturinformation lagras som ett quadtree, vars varje nod lagrar medeltemperaturen för sina undernoder.
Om trädet används för att representera en uppsättning punkter (till exempel latitud och longitud för positionerna för vissa städer), delas regionerna upp tills löven inte innehåller mer än en punkt.
Point quadtree är en typ av binärt träd som används för att lagra information om punkter på ett plan . Trädets form beror på i vilken ordning data specificeras. Användningen av sådana träd är mycket effektiv för att jämföra ordnade punkter i planet, och bearbetningstiden är O(log n) .
NodstrukturNoden på quadtree som lagrar information om planets punkter liknar noden i ett binärt träd, med den enda varningen att den första noden har fyra barn (en för varje kvadrant) istället för två ("höger" och " vänster"). Nodnyckeln har två komponenter (för x- och y -koordinater ). Således innehåller en trädnod följande information:
Quadtrees som lagrar information om linjer ( edge quadtree ) används för att beskriva raka linjer och kurvor . Kurvorna beskrivs med exakta approximationer genom att dela upp cellerna i mycket små. Detta kan göra att trädet blir obalanserat, vilket innebär indexeringsproblem.
Quadtrees som lagrar information om polygoner ( eng. polygonal map quadtree/PMQuadtree ) kan innehålla information om polygoner, inklusive degenererade sådana (som har isolerade hörn eller ytor) [1] .
Quadtrees är en tvådimensionell analog av oktantträd ( eng. octree ).
Följande kod visar användningen av quadtrees för att lagra punktinformation. Andra sätt att bygga är också möjliga.
Följande datastrukturer förväntas användas.
// En enkel struktur för att representera en punkt eller vektorstruktur XY { flyta x; flyta y; funktion __construct( flyta _x, flyta _y) {...} } // Axis-aligned bounding box (AABB), halvdimension centrerad struktur AABB { XY centrum; XY halvdimension; function __construct( XY center, XY halfDimension) {...} functions containsPoint( XY p) {...} functions cutsAABB( AABB other) {...} }Klassen representerar själva 4-trädet och rotnoden.
klass QuadTree { // Konstant - antalet element som kan lagras i en nodkonstant int QT_NODE_CAPACITY = 4; // En axelinriktad begränsningsruta // visar gränserna för trädets AABB- gräns; // Points Array av XY [size = QT_NODE_CAPACITY] punkter; // Ättlingar av QuadTree* nordväst; QuadTree* nordost; QuadTree* sydväst; QuadTree* sydost; // Methods function __construct( AABB _boundary) {...} function insert( XY p) {...} function subdivide() {...} // Skapa 4 barn som delar upp kvadranten i 4 lika delar funktion queryRange( AABB- intervall) {...} }Följande metod infogar en punkt i den lämpliga kvadranten av trädet, delar upp om det behövs.
Följande metod hittar alla punkter inom ett visst intervall.
klass QuadTree { ... // Hitta punkter inom intervallet funktion queryRange( AABB range) { // Förbered en array för resultatet Array av XY pointsInRange; // Avbryt om intervallet inte matchar kvadranten om (!boundary.insersectsAABB(range)) returnerar pointsInRange; // Tom lista // Kontrollera aktuella nivåobjekt för ( int p := 0; p < points.size; p++) { if (range.containsPoint(points[p])) pointsInRange.append(points[p]); } // Stoppa om det inte finns fler barn om (nordväst == null ) returnerar pointsInRange; // Lägg till alla underordnade poäng pointsInRange.appendArray(northWest->queryRange(range)); pointsInRange.appendArray(northEast->queryRange(range)); pointsInRange.appendArray(southWest->queryRange(range)); pointsInRange.appendArray(southEast->queryRange(range)); return pointsInRange; } }Quadtrees] (juli 1985). Tillträdesdatum: 23 mars 2012. Arkiverad från originalet 2 oktober 2012.
| Träd (datastruktur) | |
|---|---|
| Binära träd | |
| Självbalanserande binära träd |
|
| B-träd | |
| prefix träd |
|
| Binär uppdelning av utrymme | |
| Icke-binära träd |
|
| Bryter upp utrymmet |
|
| Andra träd |
|
| Algoritmer | |