Quadtree (și quadtree , 4-tree , engleză quadtree ) este un arbore în care fiecare nod intern are exact 4 descendenți. Quadtrees sunt adesea folosiți pentru a partiționați recursiv un spațiu 2D în 4 cadrane (regiuni). Zonele sunt pătrate, dreptunghiuri sau au o formă arbitrară. Termenul englezesc quadtree a fost inventat de Raphael Finkel și John Bentley .în 1974. O partiție similară a spațiului este cunoscută sub numele de Q-tree. Caracteristici comune ale diferitelor tipuri de quadtrees:
Quadtrees pot fi clasificate în funcție de tipul de date pe care le reprezintă - spațiu, puncte, linii, curbe. Ele pot fi, de asemenea, împărțite dacă forma arborelui depinde de ordinea în care sunt prelucrate datele. Câteva tipuri de quadtrees:
Regiunea quadtree reprezintă orice parte a unui spațiu bidimensional, împărțind-o în 4 cadrane, sub-cadrante și așa mai departe, fiecare frunză a arborelui corespunzând unei anumite zone . Fiecare nod al arborelui are fie 4 copii, fie nici unul (frunze). Arborii pătrați cu partiții spațiale nu sunt arbori complet deoarece poziția subcadranelor este independentă de date. Un nume mai corect este arbori de prefix ( eng. trie ).
Un arbore de înălțime n poate fi utilizat pentru a reprezenta o imagine formată din 2n × 2n pixeli, unde fiecare pixel are o valoare de 0 sau 1. Rădăcina arborelui reprezintă întreaga zonă a imaginii. Dacă nu toți pixelii sunt doar zerouri sau numai uni, se rupe. În acest caz, fiecare coală corespunde unui set de pixeli - fie numai zerouri, fie numai uni.
Arborele patru care sparge spațiul pot fi, de asemenea, utilizați pentru a reprezenta rezoluția variabilă a unui set de date. De exemplu, informațiile despre temperatură pot fi stocate ca un quadtree, fiecare nod memorând temperatura medie a nodurilor sale secundare.
Dacă arborele este folosit pentru a reprezenta un set de puncte (de exemplu, latitudinea și longitudinea pozițiilor unor orașe), regiunile sunt subdivizate până când frunzele nu conțin mai mult de un punct.
Point quadtree este un tip de arbore binar folosit pentru a stoca informații despre punctele dintr-un plan . Forma arborelui depinde de ordinea în care sunt specificate datele. Utilizarea unor astfel de arbori este foarte eficientă în compararea punctelor ordonate din plan, iar timpul de procesare este O(log n) .
Structura noduluiNodul arborelui quadtree care stochează informații despre punctele planului este similar cu nodul unui arbore binar, cu singura avertizare că primul nod are patru copii (câte unul pentru fiecare cadran) în loc de doi ("dreapta" și " stânga"). Cheia de nod are două componente (pentru coordonatele x și y ). Astfel, un nod de arbore conține următoarele informații:
Quadtrees care stochează informații despre linii ( edge quadtree ) sunt utilizați pentru a descrie linii drepte și curbe . Curbele sunt descrise prin aproximări exacte prin împărțirea celulelor în unele foarte mici. Acest lucru poate duce la dezechilibrarea arborelui, ceea ce înseamnă probleme de indexare.
Quadtrees care stochează informații despre poligoane ( eng. polygonal map quadtree/PMQuadtree ) pot conține informații despre poligoane, inclusiv cele degenerate (având vârfuri sau fețe izolate) [1] .
Quadtrees sunt un analog bidimensional al copacilor octanți ( eng. octree ).
Următorul cod demonstrează utilizarea quadtrees pentru a stoca informații despre puncte. Sunt posibile și alte abordări ale construcției.
Următoarele structuri de date sunt de așteptat să fie utilizate.
// O structură simplă pentru a reprezenta un punct sau o structură vectorială XY { float x; float y; funcția __construct( float _x, float _y) {...} } // Casetă de delimitare aliniată pe axă (AABB), structură centrată pe jumătate de dimensiune AABB { centru XY ; semidimensiune XY ; function __construct( XY center, XY halfDimension) {...} function containsPoint( XY p) {...} function intersectsAABB( AABB other) {...} }Clasa reprezintă arborele 4 în sine și nodul rădăcină.
clasa QuadTree { // Constant - numărul de elemente care pot fi stocate într-un singur nod constant int QT_NODE_CAPACITY = 4; // O casetă de delimitare aliniată la axă // arată limitele limitei arborelui AABB ; // Points Array of XY [size = QT_NODE_CAPACITY] points; // Descendenții lui QuadTree* nord- vest; QuadTree* nord-est; QuadTree * sud- vest; QuadTree * sud- est; // Metode funcția __construct( AABB _boundary) {...} function insert( XY p) {...} function subdivide() {...} // Creați 4 copii care împart cadranul în 4 părți egale function queryRange( gama AABB ) {...} }Următoarea metodă inserează un punct în cadranul corespunzător al arborelui, împărțind dacă este necesar.
Următoarea metodă găsește toate punctele dintr-un anumit interval.
clasa QuadTree { ... // Găsiți puncte în intervalul funcției queryRange ( interval AABB ) { // Pregătește o matrice pentru rezultatul Array de XY pointsInRange; // Anulează dacă intervalul nu se potrivește cu cadranul dacă (!boundary.insersectsAABB(range)) returnează pointsInRange; // Listă goală // Verificați obiectele de nivel curent pentru ( int p := 0; p < points.size; p++) { dacă (range.containsPoint(puncte[p])) pointsInRange.append(puncte[p]); } // Opreste daca nu mai sunt copii daca (northWest == null ) returneaza puncteInRange; // Adăugați toate punctele copil pointsInRange.appendArray(northWest->queryRange(interval)); pointsInRange.appendArray(northEast->queryRange(interval)); pointsInRange.appendArray(southWest->queryRange(gamă)); pointsInRange.appendArray(southEast->queryRange(gamă)); return pointInRange; } }Quadtrees] (iulie 1985). Data accesului: 23 martie 2012. Arhivat din original pe 2 octombrie 2012.
| Arborele (structura de date) | |
|---|---|
| Arbori binari | |
| Arbori binari cu auto-echilibrare |
|
| B-copaci |
|
| arbori de prefix |
|
| Partiționarea binară a spațiului | |
| Arbori non-binari |
|
| Despărțirea spațiului |
|
| Alți copaci |
|
| Algoritmi | |