Quadtree (også quadtree , 4-tree , engelsk quadtree ) er et træ , hvor hver intern node har præcis 4 efterkommere. Quadtrees bruges ofte til rekursivt at opdele et 2D-rum i 4 kvadranter (regioner). Områder er firkanter, rektangler eller har en vilkårlig form. Det engelske udtryk quadtree blev opfundet af Raphael Finkel og John Bentley .i 1974. En lignende opdeling af rummet er kendt som et Q-træ. Fælles træk ved forskellige typer quadtrees:
Quadtrees kan klassificeres efter den type data, de repræsenterer - rum, punkter, linjer, kurver. De kan også opdeles efter, om træets form afhænger af den rækkefølge, dataene behandles i. Nogle typer quadtrees:
Region quadtree repræsenterer enhver del af et todimensionelt rum ved at opdele det i 4 kvadranter, underkvadranter og så videre, hvor hvert blad af træet svarer til et bestemt område . Hver knude i træet har enten 4 børn eller slet ingen (blade). Space-partitionerende quadtrees er ikke fuldt ud træer, fordi positionen af underkvadranterne er uafhængig af dataene. Et mere korrekt navn er præfikstræer ( eng. trie ).
Et træ med højden n kan bruges til at repræsentere et billede bestående af 2n × 2n pixels, hvor hver pixel har en værdi på 0 eller 1. Træets rod repræsenterer hele billedets område. Hvis ikke alle pixels kun er nuller eller kun enere, går den i stykker. I dette tilfælde svarer hvert ark til et sæt pixels - enten kun nuller eller kun en.
Rumbrydende quadtrees kan også bruges til at repræsentere den variable opløsning af et datasæt. Temperaturinformation kan f.eks. lagres som et quadtree, hvor hver knude gemmer den gennemsnitlige temperatur for sine underknudepunkter.
Hvis træet bruges til at repræsentere et sæt punkter (for eksempel bredde- og længdegraden af positionerne i nogle byer), underinddeles regionerne, indtil bladene ikke indeholder mere end ét punkt.
Point quadtree er en type binært træ , der bruges til at gemme information om punkter på et plan . Træets form afhænger af den rækkefølge, dataene er angivet i. Brugen af sådanne træer er meget effektiv til at sammenligne ordnede punkter i planet, og behandlingstiden er O(log n) .
NodestrukturKnuden på quadtreeet, der gemmer information om planets punkter, ligner knudepunktet i et binært træ, med det eneste forbehold, at den første knude har fire børn (en for hver kvadrant) i stedet for to ("højre" og " venstre"). Node-nøglen har to komponenter (for x- og y -koordinater ). Således indeholder en træknude følgende information:
Quadtrees, der gemmer information om linjer ( kant quadtree ), bruges til at beskrive lige linjer og kurver . Kurverne beskrives ved nøjagtige tilnærmelser ved at opdele cellerne i meget små. Dette kan få træet til at blive ubalanceret, hvilket betyder indekseringsproblemer.
Quadtrees, der gemmer information om polygoner ( eng. polygonal map quadtree/PMQuadtree ) kan indeholde information om polygoner, inklusive degenererede (der har isolerede hjørner eller ansigter) [1] .
Quadtrees er en todimensionel analog af oktanttræer ( eng. octree ).
Den følgende kode demonstrerer brugen af quadtrees til at gemme punktinformation. Andre tilgange til byggeri er også mulige.
Følgende datastrukturer forventes at blive brugt.
// En simpel struktur til at repræsentere et punkt eller vektorstruktur XY { flyde x; flyde y; funktion __construct( float _x, float _y) {...} } // Axis-aligned bounding box (AABB), halvdimension centreret struktur AABB { XY center; XY halvdimension; funktion __construct( XY center, XY halfDimension) {...} funktion indeholderPunkt( XY p) {...} funktion skærer AABB( AABB anden) {...} }Klassen repræsenterer selve 4-træet og rodnoden.
klasse QuadTree { // Konstant - antallet af elementer, der kan lagres i en node konstant int QT_NODE_CAPACITY = 4; // En akse-justeret afgrænsningsboks // viser grænserne for træets AABB - grænse; // Points Array af XY [størrelse = QT_NODE_CAPACITY] punkter; // Efterkommere af QuadTree* nordvest; QuadTree* nordøst; QuadTree* sydvest; QuadTree* sydøst; // Methods function __construct( AABB _boundary) {...} function insert( XY p) {...} function subdivide() {...} // Opret 4 børn, der deler kvadranten i 4 lige dele funktion queryRange( AABB- område) {...} }Følgende metode indsætter et punkt i den relevante kvadrant af træet, opdeling om nødvendigt.
Den følgende metode finder alle punkter inden for et bestemt interval.
klasse QuadTree { ... // Find punkter inden for rækkevidde funktion queryRange( AABB range) { // Forbered et array for resultatet Array af XY pointsInRange; // Annuller hvis rækkevidde ikke matcher kvadrant hvis (!grænse.insersectsAABB(område)) returnerer pointInRange; // Tom liste // Tjek aktuelle niveauobjekter for ( int p := 0; p < points.size; p++) { if (range.containsPoint(point[p])) pointsInRange.append(points[p]); } // Stop hvis der ikke er flere børn hvis (nordvest == null ) returnerer pointInRange; // Tilføj alle underordnede point pointsInRange.appendArray(nordvest->queryRange(interval)); pointsInRange.appendArray(nordØst->queryRange(interval)); pointsInRange.appendArray(sydvest->queryRange(interval)); pointsInRange.appendArray(sydøst->queryRange(interval)); returnere pointInRange; } }Quadtrees] (juli 1985). Dato for adgang: 23. marts 2012. Arkiveret fra originalen 2. oktober 2012.
| Træ (datastruktur) | |
|---|---|
| Binære træer | |
| Selvbalancerende binære træer |
|
| B-træer | |
| præfiks træer |
|
| Binær opdeling af rummet | |
| Ikke-binære træer |
|
| At bryde rummet op |
|
| Andre træer |
|
| Algoritmer |
|