Begrepet Quadtree , eller kvaternært tre, brukes for å beskrive klasser av hierarkiske datastrukturer hvis felles egenskap er at de er basert på prinsippet om rekursiv dekomponering av rom. I et QuadTree av punkter er sentrum av en underavdeling alltid ved et punkt. Ved innsetting av nytt element deles plassen i fire. [ 1 ] Ved å gjenta prosessen deler kvadranten opp i fire igjen, og så videre.
Et bredt utvalg av hierarkiske strukturer eksisterer for å representere romlige data. En vanlig teknikk er Quadtree. Utviklingen av disse var motivert av behovet for å lagre data som er satt inn med identiske eller lignende verdier. Denne artikkelen omhandler representasjon av data i todimensjonalt rom. Quadtree brukes også for datarepresentasjon i tredimensjonale rom eller med opptil 'n' dimensjoner.
Begrepet Quadtree brukes til å beskrive en klasse hierarkiske strukturer hvis felles eiendom er rekursjonsprinsippet for romnedbrytning.
Disse klassene baserer forskjellen på følgende krav:
Quadtree-familien brukes til å representere punkter, områder, kurver, overflater og volumer. Dekomponeringen kan gjøres på de samme delene på hvert nivå (den vanlige dekomponeringen), eller den kan avhenge av inndataene. Oppløsningen av dekomponeringen, med andre ord, antall ganger dekomponeringsprosessen brukes, kan være forhåndsbestemt, eller kan avhenge av egenskapene til inngangsdataene.
Det første eksemplet på et Quadtree er relatert til representasjonen av et todimensjonalt område. Quadtree-regionen som representerer områdene er den mest studerte typen. Dette eksemplet er basert på den suksessive inndelingen av plass i fire kvadranter av samme størrelse. Underkvadranten som inneholder data kalles ganske enkelt det svarte området , og de som ikke inneholder data kalles det hvite området . En underkvadrant som inneholder deler av begge kalles Ask -området . Ask - underkvadrantene , som inneholder hvite og svarte (tom og data) områder, må deles opp i rekkefølge inntil bare svarte og hvite kvadranter ... (data og tomme) gjenstår.
Hver kvadrant representerer en node av Quadtree, de svarte og hvite områdene er alltid på bladene, mens alle de indre nodene representerer de grå områdene.
Flerdimensjonene til punkter kan representeres på forskjellige måter. Den valgte representasjonen avhenger av den spesifikke oppgaven man ønsker å utføre med en gruppe punkter. To av de vanligste oppgavene som utføres med en poenggruppe er:
Quadtreet, dets varianter og også kd-treet, representerer ganske effektive former for å representere punktene. De to vanligste typene Quadtree for å representere poeng er "Point Quadtree" og "PR Quadtree (regionens Quadtree-variant)".
PR-Quadtree er en tilpasning av Quadtree for representasjon av punkter i en region. Hvert punkt er knyttet til kvadranten. I motsetning til Point Quadtree hvor inndelingen av kvadrantene avhenger av inndataene, gjøres delingen alltid på en vanlig måte. Bladnodene som inneholder et punkt vil bli kalt Black , og hvis de er tomme White . Alle noder som ikke har blader kalles Ask .
Hver node lagres i en post som inneholder fem felt. Den første inneholder en vektor av indikatorer for de fire barna til noden (tilsvarende de fire kvadrantene), den andre, fargen på noden (hvit, svart eller grå), et tredje felt kan reserveres for noe informasjon relatert til node.
struct PRNo { PRNo *barn[4]; int farge; // blank = 0; grå = 1; svart = 2; charinfo[20]; intx; int og; };Poeng settes inn på en måte som ligner på den som brukes i Point Quadtree. Først gjøres et søk for å finne subkvadranten som noden tilhører (noden går). Hvis denne underkvadranten allerede er okkupert av en annen node B med forskjellige koordinater, må denne kvadranten deles inn i de nødvendige delene slik at nodene A og B ikke opptar samme kvadrant. Dette kan forårsake et stort antall underinndelinger, spesielt hvis de to punktene er inneholdt i en veldig liten blokk med plass. Innvendige noder lagrer ikke data, fra punktet som tidligere okkuperte kvadranten (punkt B) hvis det blir søsken til det nye punktet (punkt A). Som et resultat er det observert at alle de grå nodene har to etterkommere som inneholder dataene i det minste. Skjemaet som resulterer fra et PR-Quadtree er uavhengig av rekkefølgen punktene settes inn i.
Merk: Hvis noden forlater og hvor P skal settes inn er tomt (HVIT), settes P inn.
I tilfelle den er opptatt, må punktet som nå er i node (R) gjenopprettes. I tilfelle P og R tilhører forskjellige underkvadranter, settes de ganske enkelt inn i sine respektive posisjoner. I tilfelle de tilhører de samme kvadrantene, må påfølgende underinndelinger gjøres til kvadrantene er forskjellige. I hver underavdeling må det opprettes en grå node.
De kan klassifiseres i henhold til typen data de representerer, inkludert områder, punkter, linjer og kurver. Quadtrees kan også klassifiseres uavhengig av formen den har på grunn av informasjonen den inneholder. Noen vanlige typer quadtrees er:
Punkt quadtree er en tilpasning av et binært tre som brukes til å representere todimensjonale punktdata. Det deler egenskapene til alle quadtrees, men er et ekte tre ettersom midten av en underavdeling alltid er på et punkt. Formen på treet behandles avhenger av ordredataene. Det er ofte svært effektivt å sammenligne de forespurte todimensjonale referansepunktene, vanligvis kjører i O(log n) tid.
Nodestruktur for et firetre med punkter
-Navn -(x,y) Koordinater
Et binært bilde er normalt representert som en serie med binære innganger, det vil si; hver av oppføringene i serien har en verdi på 0 eller 1. For å lagre det binære bildet, brukes vanligvis den velkjente quadtree-partisjonen. For en N*N-serie, N<=512 og N=2i for et positivt heltall i, hvis oppføringene ikke har samme verdi, del deretter opp i 4 N/2*N/2-serier. Hvis en serie N/2*N/2 ikke har samme binære verdi, for eksempel øverst til høyre og nederst til høyre i serien N/2*N/2, kan vi dele den i fire N/4*N/4 måter igjen. Disse N/4*N/4-skjemaene kan også ved behov deles inn i 4 N/8*N/8-skjemaer mv. quadtree-partisjonen er fullført når hele skjemaet er partisjonert i arrays av forskjellige størrelser der hver array inneholder bare én binær verdi. I stedet for å lagre det binære bildet, trenger vi bare å lagre quadtreet med koden som refererer til inngangsbildet.
Regionkvadrantreet representerer en rompartisjon i to dimensjoner ved å dekomponere området i fire like kvadranter, underkvadranter og så videre med hver bladnode som inneholder data som tilsvarer en spesifikk underregion. Hver node i treet har nøyaktig fire barn, eller ingen barn i det hele tatt (en bladnode). Et områdefiretre med en dybde på n kan brukes til å representere et bilde som består av 2n * 2n piksler, der hver pikselverdi er 0 eller 1. Denne datastrukturen er endimensjonal og finnes bare i hovedminnet . Hver barnenode har fire noder assosiert med seg, og representerer således de seksten underkvadrantene til bildet. Når Quadtree er dannet, representerer bladnodene egenskapen til nevnte piksel, som kan være hvit eller svart, hvis de er monokrome bilder, avhengig av enhetligheten i fargen på barnetnodene (hvis alle barna deres er svarte, så sa node vil bli representert av fargen svart). Men hvis en node har undernoder med uensartede farger, er den representert av en "grå node". Et regionsquadtree kan også brukes som en representasjon med variabel oppløsning av et datafelt. For eksempel kan temperaturer i et område lagres som et quadtree, med hver bladnode som lagrer gjennomsnittstemperaturen over underregionen den representerer. Hvis et områdekvadretre brukes til å representere et punktdatasett (som breddegrad og lengdegrad til et bysystem), blir regionene delt inn til hvert blad inneholder maksimalt et enkelt punkt.
Det første som kommer til tankene for punktplasseringsproblemet er et balansert Q-tre . Den klassiske Qtree-metoden har noen ulemper når for eksempel koordinatene til et punkt får endres eller når det er mange innsettinger og slettinger.
For dette er den beste (uten tvil) kuben Qtree av følgende grunner: Den er veldig enkel å implementere og teorien om å finne det minst effektive punktet er ganske langt unna på grunn av den "implisitte balansen" i metoden (den sekvens av innsettinger av punkter har ingen innvirkning på strukturen til det endelige treet uten behov for å forklare balansen til treet). Det er ufølsomt for punktkoordinatendringer og veldig effektivt når det gjelder elimineringer. Datastrukturen til et område q-tre brukt for plassering av punkter i Delaunay-nettverket . Qtreet raffineres adaptivt under iterativ innsetting av masker og geometripunkter.