Kvadramenttre

Et kvadramenttre , [1] ofte referert til som " quadtree ", er en ubalansert tredatastruktur der alle interne noder har nøyaktig fire underordnede noder. Quadtrees brukes ofte til å dele et todimensjonalt rom ved rekursivt å dele det inn i fire kvadranter, ofte referert til som Northeast , Northwest , Southeast , Southwest .

Vanlige bruksområder for denne typen strukturer er følgende:

Representasjon av bilder;
Romlig indeksering;
bestemmelse av kollisjoner i to dimensjoner;
Sparsom datalagring, for eksempel lagring av formateringsinformasjon for et regneark eller matriseberegninger.

Kvadramenttrær er de todimensjonale korrespondentene til oktale trær (også kalt "oktre").

Quadtrees er tredatastrukturer der bildet er delt inn i 4 kvadranter; fortsetter du med klokken og starter fra den øverst til venstre, for hver kvadrant sjekkes det om den er ensartet: hvis den ikke er det, gjentas prosedyren for den kvadranten til ensartede områder er nådd (høyst kommer du til enkeltpikselen) .

Kvadramenttrær som 2D romlige representasjoner

Kvadramenttrærne PR (Region Point) representerer et sett med punkter i to dimensjoner som dekomponerer regionen som inneholder dem til fire underkvadranter, som igjen kan dekomponeres, og så videre opp til bladnodene. Stoppkriteriene som vanligvis brukes er to:

Bladet inneholder et antall poeng lavere enn et forhåndsbestemt maksimalt antall
Bladet har et minimalt areal

Pseudokode

QuadTree klasse

Denne klassen representerer både et kvadramenttre og en node der den er forankret.

klasse QuadTree { // Vilkårlig konstant for å indikere hvor mange elementer som kan lagres i denne firkantede trenoden konstant int QT_NODE_CAPACITY = 4; // Aksejustert avgrensningsboks lagret som et senter med halve dimensjoner // for å representere grensene til denne firkanttre AABB -grensen; // Poeng i denne firkantede trenoden Array av XY [størrelse = QT_NODE_CAPACITY] poeng; // Barn QuadTree * nordvest; QuadTree * nordøst; QuadTree * sørvest; QuadTree * sørøst; // Metoder funksjon __konstruksjon ( AABB _grense) {...} funksjon sett inn ( XY p) {...} funksjon subdivide () {...} // lag fire underordnede barn som deler denne kvadraten i fire kvadrater med likt areal funksjon queryRange ( AABB- område ) {...} }

Innsetting

Følgende metode setter inn et punkt innenfor den ønskede sonen til et kvadramenttre.

klasse QuadTree { ... // Sett inn et punkt i QuadTree- funksjonsinnsettingen ( XY p) { // Ignorer objekter som ikke hører hjemme i dette quad-treet hvis (! Boundary.containsPoint (p)) returnerer false ; // objekt kan ikke legges til // Hvis det er plass i dette quad-treet, legg til objektet her if (points.size <QT_NODE_CAPACITY) { poeng.vedlegg (p); return true ; } // Ellers, del inn og legg til punktet til den noden som godtar det hvis (nordvest == null ) dele opp (); if (nordvest → sett inn (p)) return true ; hvis (nordøst → sett inn (p)) return true ; if (sørvest → sett inn (p)) return true ; if (sørøst → sett inn (p)) return true ; // Ellers kan ikke punktet settes inn av en eller annen ukjent grunn (dette bør aldri skje) return false ; } }

Spørreområde

Følgende metode finner alle punktene i et område.

klasse QuadTree { ... // Finn alle punkter som vises innenfor en rekkeviddefunksjon queryRange ( AABB- område ) { // Forbered en rekke resultater Matrise av XY pointsInRange; // Avbryt automatisk hvis området ikke skjærer denne quad hvis (! Boundary.intersectsAABB (range)) returnerer pointsInRange; // tom liste // Sjekk objekter på dette quad-nivået for ( int p: = 0; p <points.size; p ++) { if (range.containsPoint (punkter [p])) pointsInRange.append (punkter [p]); } // Avslutt her, hvis det ikke er noen barn hvis (nordvest == null ) returnerer pointsInRange; // Ellers legger du til poengene fra barna pointsInRange.appendArray (nordvest → queryRange (område)); pointsInRange.appendArray (nordØst → queryRange (område)); pointsInRange.appendArray (sørvest → queryRange (område)); pointsInRange.appendArray (sørøst → queryRange (område)); return pointsInRange; } }

Merknader

^ Daniela Cancilia og Stefano Mazzanti, The encyclopedic dictionary of data science ( PDF ), Zanichelli, s. 647. Hentet 4. januar 2018 .