Quadtree - Quadtree

Et firkantet punktområde med punktdata. Skuffekapasitet 1.

Firetre komprimering av et bilde trinn for trinn. Venstre viser det komprimerte bildet med treboksene, mens det høyre viser bare det komprimerte bildet

Et firkantet tre er en tre datastruktur der hver interne node har nøyaktig fire barn. Firetre er den todimensjonale analogen av oktre og brukes oftest til å dele et todimensjonalt rom ved rekursivt å dele det inn i fire kvadranter eller regioner. Dataene knyttet til en bladcelle varierer etter applikasjon, men bladcellen representerer en "enhet med interessant romlig informasjon".

De inndelte områdene kan være firkantede eller rektangulære, eller kan ha vilkårlige former. Denne datastrukturen ble kåret til et firetre av Raphael Finkel og JL Bentley i 1974. En lignende partisjonering er også kjent som et Q-tre . Alle former for firetre deler noen vanlige trekk:

• De bryter ned plass i tilpasningsdyktige celler
• Hver celle (eller bøtte) har en maksimal kapasitet. Når maksimal kapasitet er nådd, deler skuffen seg
• Trekatalogen følger den romlige nedbrytningen av firtreet.

En trepyramide ( T-pyramide ) er et "komplett" tre; hver node i T-pyramiden har fire barne noder bortsett fra bladnoder; alle bladene er på samme nivå, nivået som tilsvarer individuelle piksler i bildet. Dataene i en trepyramide kan lagres kompakt i en matrise som en implisitt datastruktur som ligner måten et komplett binært tre kan lagres kompakt i en matrise .

Typer

Firetre kan klassifiseres i henhold til typen data de representerer, inkludert områder, punkter, linjer og kurver. Firetre kan også klassifiseres etter om treets form er uavhengig av rekkefølgen dataene behandles i. Følgende er vanlige typer firetrær.

Region firetre

Regionens kvadrant representerer en partisjon av plass i to dimensjoner ved å dekomponere regionen i fire like kvadranter, subkvadranter, og så videre med hver bladnode som inneholder data som tilsvarer en bestemt subregion. Hver node i treet har enten nøyaktig fire barn, eller har ingen barn (en bladnode). Høyden på firetrær som følger denne dekomponeringsstrategien (dvs. å dele underkvadranter så lenge det er interessante data i delkvadranten som det ønskes mer forfining for) er følsom for og avhengig av den romlige fordelingen av interessante områder i rommet som dekomponeres. Regionen firtreet er en type trie .

Et firkantet område med en dybde på n kan brukes til å representere et bilde som består av 2 ⁿ × 2 ⁿ piksler, hvor hver pikselverdi er 0 eller 1. Rotnoden representerer hele bildeområdet. Hvis pikslene i et område ikke er helt 0 eller 1, er det delt inn. I denne applikasjonen representerer hver bladnode en blokk med piksler som alle er 0s eller alle 1s. Legg merke til de potensielle besparelsene når det gjelder plass når disse trærne brukes til lagring av bilder; bilder har ofte mange områder med betydelig størrelse som har samme fargeverdi gjennomgående. I stedet for å lagre et stort 2-D-utvalg av hver piksel i bildet, kan et firtre fange den samme informasjonen potensielt mange delingsnivåer høyere enn cellene med pikseloppløsning som vi ellers ville kreve. Treoppløsningen og den totale størrelsen er begrenset av piksel- og bildestørrelsene.

Et regiontree kan også brukes som en representasjon med variabel oppløsning av et datafelt. For eksempel kan temperaturene i et område lagres som et firetre, hvor hver bladnode lagrer gjennomsnittstemperaturen over delregionen den representerer.

Hvis et regiontreetre brukes til å representere et sett med punktdata (for eksempel breddegrad og lengdegrad for et sett med byer), blir regioner delt inn til hvert blad inneholder høyst et enkelt punkt.

Point quadtree

Point quadtree er en tilpasning av et binært tre som brukes til å representere todimensjonale punktdata. Den deler egenskapene til alle firetrær, men er et ekte tre ettersom sentrum av en underavdeling alltid er på et punkt. Det er ofte veldig effektivt i å sammenligne todimensjonale, ordnede datapunkter, som vanligvis opererer i O (log n) tid. Point quadtrees er verdt å nevne for fullstendighet, men de har blitt overgått av k -d trær som verktøy for generalisert binært søk.

Point quadtrees er konstruert som følger. Gitt det neste punktet å sette inn, finner vi cellen den ligger i og legger den til treet. Det nye punktet legges til slik at cellen som inneholder det er delt inn i kvadranter av de vertikale og horisontale linjene som går gjennom punktet. Følgelig er celler rektangulære, men ikke nødvendigvis firkantede. I disse trærne inneholder hver node ett av inngangspunktene.

Siden delingen av flyet bestemmes av rekkefølgen på punktinnsetting, er treets høyde følsom for og avhengig av innsettingsrekkefølge. Innsetting i en "dårlig" rekkefølge kan føre til et tre med høyde lineært i antall inngangspunkter (på hvilket tidspunkt det blir en lenket liste). Hvis punktsettet er statisk, kan forbehandling gjøres for å lage et tre med balansert høyde.

Nodestruktur for et punkt -firetre

En node på et punkttre -tre ligner en node i et binært tre , med den største forskjellen at den har fire pekere (en for hver kvadrant) i stedet for to ("venstre" og "høyre") som i et vanlig binært tre . Også en nøkkel er vanligvis dekomponert i to deler, med henvisning til x- og y -koordinater. Derfor inneholder en node følgende informasjon:

• fire pekere: quad ['NW'], quad ['NE'], quad ['SW'] og quad ['SE']
• punkt; som igjen inneholder:
  • nøkkel; vanligvis uttrykt som x, y koordinater
  • verdi; for eksempel et navn

Point-region (PR) firetre

Point-region (PR) quadtrees er veldig like region quadtrees. Forskjellen er typen informasjon som er lagret om cellene. I en firkantet region lagres en ensartet verdi som gjelder hele området i cellen til et blad. Cellene i et PR -firetre lagrer imidlertid en liste over punkter som finnes i cellen i et blad. Som nevnt tidligere, er høyden avhengig av den romlige fordelingen av punktene for trær som følger denne nedbrytingsstrategien. I likhet med quadtree, kan PR quadtree også ha en lineær høyde når den får et "dårlig" sett.

Edge quadtree

Edge quadtrees (omtrent som PM quadtrees) brukes til å lagre linjer i stedet for punkter. Kurver tilnærmes ved å dele celler til en veldig fin oppløsning, spesielt til det er et enkelt linjesegment per celle. Nær hjørner/hjørner vil kantkvadretre fortsette å dele til de når sitt maksimale nedbrytningsnivå. Dette kan resultere i ekstremt ubalanserte trær som kan ødelegge formålet med indeksering.

Polygonal map (PM) quadtree

Det polygonale kartet quadtree (eller PM Quadtree) er en variant av quadtree som brukes til å lagre samlinger av polygoner som kan være degenererte (noe som betyr at de har isolerte hjørner eller kanter). En stor forskjell mellom PM quadtrees og edge quadtrees er at cellen som er vurdert ikke blir delt inn hvis segmentene møtes ved et toppunkt i cellen.

Det er tre hovedklasser av PM Quadtrees, som varierer avhengig av hvilken informasjon de lagrer i hver svart node. PM3 quadtrees kan lagre en mengde ikke-kryssende kanter og høyst ett punkt. PM2 quadtrees er de samme som PM3 quadtrees bortsett fra at alle kanter må dele det samme sluttpunktet. Endelig ligner PM1 -firetrær på PM2, men svarte noder kan inneholde et punkt og kantene eller bare et sett med kanter som deler et punkt, men du kan ikke ha et punkt og et sett med kanter som ikke inneholder punktet.

Komprimerte firetre

Denne delen oppsummerer en underseksjon fra en bok av Sariel Har-Peled .

Hvis vi skulle lagre hver node som tilsvarer en celledelt, kan vi ende opp med å lagre mange tomme noder. Vi kan kutte ned på størrelsen på slike sparsomme trær ved bare å lagre undertrær hvis blader har interessante data (dvs. "viktige undertrær"). Vi kan faktisk redusere størrelsen ytterligere. Når vi bare beholder viktige undertrær, kan beskjæringsprosessen etterlate lange stier i treet der mellomnodene har grad to (en kobling til en forelder og ett barn). Det viser seg at vi bare trenger å lagre noden i begynnelsen av denne banen (og knytte noen metadata til den for å representere de fjernede nodene) og feste undertreet som er forankret på slutten . Det er fortsatt mulig for disse komprimerte trærne å ha en lineær høyde når de får "dårlige" inngangspunkter. ${\ displaystyle u}$${\ displaystyle u}$

Selv om vi trimmer mye av treet når vi utfører denne komprimeringen, er det fortsatt mulig å oppnå logaritmisk tidssøk , innsetting og sletting ved å dra fordel av Z -ordenskurver . Den Z -Bestill kurve kartlegger hver celle av den fulle firertreet (og dermed også den komprimerte firertre) i tid til en endimensjonal linje (og tilordner den tilbake i tid også), og skaper en total orden på elementene. Derfor kan vi lagre firetreet i en datastruktur for bestilte sett (der vi lagrer nodene til treet). ${\ displaystyle O (1)}$${\ displaystyle O (1)}$

Vi må angi en rimelig antagelse før vi fortsetter: vi antar at gitt to reelle tall uttrykt som binære, kan vi med tiden beregne indeksen til den første biten der de er forskjellige. Vi antar også at vi i tid kan beregne den laveste felles stamfar til to punkter/celler i firetreet og etablere deres relative Z -ordning, og vi kan beregne gulvfunksjonen i tide. ${\ displaystyle \ alpha, \ beta \ in [0,1)}$${\ displaystyle O (1)}$${\ displaystyle O (1)}$${\ displaystyle O (1)}$

Med disse forutsetningene kan punktlokalisering av et gitt punkt (dvs. å bestemme cellen som vil inneholde ), innsetting og sletting operasjoner utføres i tide (dvs. tiden det tar å gjøre et søk i den underliggende ordnet sett datastrukturen). ${\ displaystyle q}$${\ displaystyle q}$${\ displaystyle O (\ logg {n})}$

For å utføre et punktsted for (dvs. finne cellen i det komprimerte treet): ${\ displaystyle q}$

1. Finn den eksisterende cellen i det komprimerte treet som kommer før i Z -orden. Ring denne cellen .${\ displaystyle q}$${\ displaystyle v}$
2. Hvis , returner .${\ displaystyle q \ in v}$${\ displaystyle v}$
3. Ellers finner du det som ville ha vært den laveste felles stamfar til punktet og cellen i et ukomprimert firetre. Kall denne stamcellen .${\ displaystyle q}$${\ displaystyle v}$${\ displaystyle u}$
4. Finn den eksisterende cellen i det komprimerte treet som kommer før i Z -rekkefølgen, og returner den.${\ displaystyle u}$

Uten å gå inn på spesifikke detaljer, for å utføre innsetting og sletting, gjør vi først et punktsted for det vi vil sette inn/slette, og deretter sette inn/slette det. Det må utvises forsiktighet for å omforme treet etter behov, opprette og fjerne noder etter behov.

Noen vanlige bruksområder for firetrær

• Bilde representasjon
  
• Bildebehandling
• Mesh generasjon
• Romlig indeksering , søk etter punktlokalisering og rekkevidde
• Effektiv kollisjonsdeteksjon i to dimensjoner
• Se frustum sletting av terrengdata
• Lagre sparsomme data, for eksempel en formateringsinformasjon for et regneark eller for noen matriseberegninger
• Løsning av flerdimensjonale felt ( beregningsvæskedynamikk , elektromagnetisme )
• Conways Game of Life -simuleringsprogram.
• Statlig estimering
• Quadtrees brukes også innen fraktal bildeanalyse
• Maksimal usammenhengende sett

Bildebehandling ved bruk av firetre

Quadtrees, spesielt regionen quadtree , har lånt seg godt til bildebehandlingsprogrammer. Vi vil begrense diskusjonen til binære bildedata, selv om regionens firetrær og bildebehandlingsoperasjonene som utføres på dem er like egnet for fargebilder.

Bildeforening / kryss

En av fordelene med å bruke quadtrees for bildemanipulering er at de angitte operasjonene for union og kryss kan gjøres enkelt og raskt. Gitt to binære bilder, produserer bildeforeningen (også kalt overlegg ) et bilde der en piksel er svart hvis et av inngangsbildene har en svart piksel på samme sted. Det vil si at en piksel i utgangsbildet bare er hvit når den tilsvarende piksel i begge inngangsbildene er hvit, ellers er utgangspikslen svart. I stedet for å gjøre operasjonen pixel for pixel, kan vi beregne unionen mer effektivt ved å utnytte firetreets evne til å representere flere piksler med en enkelt node. For diskusjonene nedenfor, hvis et undertre inneholder både svarte og hvite piksler, vil vi si at roten til subtreet er farget grå.

Algoritmen fungerer ved å krysse de to input quadtrees ( og ) mens du bygger output quadtree . Uformelt er algoritmen som følger. Vurder nodene og tilsvarer den samme regionen i bildene. ${\ displaystyle T_ {1}}$${\ displaystyle T_ {2}}$${\ displaystyle T}$${\ displaystyle v_ {1} \ i T_ {1}}$${\ displaystyle v_ {2} \ i T_ {2}}$

• Hvis eller er svart, opprettes den tilsvarende noden i og er svart. Hvis bare en av dem er svart og den andre er grå, vil den grå noden inneholde et undertre under. Dette undertreet trenger ikke krysses.${\ displaystyle v_ {1}}$${\ displaystyle v_ {2}}$${\ displaystyle T}$
• Hvis (henholdsvis ) er hvitt, (henholdsvis, ) og undertreet under det (hvis noen) kopieres til .${\ displaystyle v_ {1}}$${\ displaystyle v_ {2}}$${\ displaystyle v_ {2}}$${\ displaystyle v_ {1}}$${\ displaystyle T}$
• Hvis begge og er grå, blir de tilsvarende barna til og vurdert.${\ displaystyle v_ {1}}$${\ displaystyle v_ {2}}$${\ displaystyle v_ {1}}$${\ displaystyle v_ {2}}$

Selv om denne algoritmen fungerer, garanterer den ikke i seg selv et firetre med minimal størrelse. Vurder for eksempel resultatet hvis vi skulle forene et sjakkbrett (hvor hver flis er en piksel) av størrelse med komplementet. Resultatet er en gigantisk svart firkant som skal representeres av et firetre med bare rotnoden (farget svart), men i stedet produserer algoritmen et fullt dybde på fire år . For å fikse dette, utfører vi en bottom-up traversal av det resulterende firetreet hvor vi sjekker om de fire barneknuter har samme farge, i så fall erstatter vi foreldrene deres med et blad av samme farge. ${\ displaystyle 2^{k} \ times 2^{k}}$${\ displaystyle k}$

Skjæringspunktet mellom to bilder er nesten den samme algoritmen. En måte å tenke på skjæringspunktet mellom de to bildene er at vi gjør en forening med hensyn til de hvite pikslene. Som sådan bytter vi omtaler av svart og hvitt i fagforeningsalgoritmen for å utføre krysset.

Tilkoblet komponentmerking

Tenk på to tilgrensende sorte piksler i et binært bilde. De er tilstøtende hvis de deler en avgrensende horisontal eller vertikal kant. Generelt er to svarte piksler forbundet hvis den ene kan nås fra den andre ved bare å flytte til tilstøtende piksler (dvs. det er en bane med svarte piksler mellom dem der hvert påfølgende par er tilstøtende). Hvert maksimalt sett med tilkoblede svarte piksler er en tilkoblet komponent . Ved å bruke kvadrertrepresentasjonen av bilder, viste Samet hvordan vi kan finne og merke disse tilkoblede komponentene i tid proporsjonalt med størrelsen på firetreet. Denne algoritmen kan også brukes til polygonfarging.

Algoritmen fungerer i tre trinn:

• etablere tilknytningsforhold mellom svarte piksler
• behandle ekvivalensforholdene fra det første trinnet for å få en unik etikett for hver tilkoblede komponent
• merke de svarte pikslene med etiketten som er knyttet til den tilkoblede komponenten

For å forenkle diskusjonen, la oss anta at barna til en node i firetreet følger Z -rekkefølgen (SW, NW, SE, NE). Siden vi kan stole på denne strukturen, vet vi for hvilken som helst celle hvordan vi skal navigere i firetreet for å finne de tilstøtende cellene i de forskjellige nivåene i hierarkiet.

Trinn ett oppnås med en etterbestillingskryssing av firetreet. For hvert svart blad ser vi på noden eller nodene som representerer celler som er nordlige naboer og østlige naboer (dvs. de nordlige og østlige cellene som deler kanter med cellen til ). Siden treet er organisert i Z -order, har vi invarianten som de sørlige og vestlige naboene allerede har blitt tatt vare på og redegjort for. La den nordlige eller østlige naboen for øyeblikket vurderes . Hvis representerer svarte piksler: ${\ displaystyle v}$${\ displaystyle v}$${\ displaystyle u}$${\ displaystyle u}$

• Hvis bare én av eller har en etikett, tilordner du den andre cellen den etiketten${\ displaystyle u}$${\ displaystyle v}$
• Hvis ingen av dem har etiketter, må du lage en og tildele den til dem begge
• Hvis og har forskjellige etiketter, registrer du denne etikettekvivalensen og fortsett${\ displaystyle u}$${\ displaystyle v}$

Trinn to kan utføres ved å bruke datastrukturen for fagforeninger . Vi starter med hver unik etikett som et eget sett. For hvert ekvivalensforhold som ble notert i det første trinnet, forbinder vi de tilsvarende settene. Etterpå vil hvert distinkte gjenværende sett være knyttet til en distinkt tilkoblet komponent i bildet.

Trinn tre utfører en annen post-order traversal. Denne gangen, for hver svart node, bruker vi union-find's find- operasjonen (med den gamle etiketten ) for å finne og tildele den nye etiketten (assosiert med den tilkoblede komponenten som er en del). ${\ displaystyle v}$${\ displaystyle v}$${\ displaystyle v}$${\ displaystyle v}$

Nettinggenerering ved bruk av firetrær

Denne delen oppsummerer et kapittel fra en bok av Har-Peled og de Berg et al.

Nettinggenerering er i hovedsak trianguleringen av et punktsett som det kan utføres ytterligere behandling for. Som sådan er det ønskelig at den resulterende trianguleringen har visse egenskaper (som ujevnhet, trekanter som ikke er "for tynne", store trekanter i sparsomme områder og små trekanter i tette, etc.) for å gjøre videre behandling raskere og mindre utsatt for feil. Quadtrees bygget på poengsett kan brukes til å lage masker med disse ønskede egenskapene.

Et balansert blad har høyst ett hjørne i en side.

Tenk på et blad av firetreet og tilhørende celle . Vi sier at det er balansert (for maskegenerering) hvis cellens sider krysses av hjørnepunktene til naboceller høyst en gang på hver side. Dette betyr at firetre nivåer av blader ved siden av for å avvike med høyst en fra nivået av . Når dette er sant for alle blader, sier vi at hele firetreet er balansert (for maskegenerering). ${\ displaystyle v}$${\ displaystyle v}$${\ displaystyle v}$${\ displaystyle v}$

Tenk på cellen og nabolaget til celler av samme størrelse sentrert på . Vi kaller dette nabolaget for den utvidede klyngen . Vi sier at firetreet er godt balansert hvis det er balansert, og for hvert blad som inneholder et punkt i poengsett, er dets utvidede klynge også i firetreet og den utvidede klyngen inneholder ikke noe annet punkt i settet. ${\ displaystyle v}$${\ displaystyle 5 \ times 5}$${\ displaystyle v}$${\ displaystyle u}$

Å lage masken gjøres som følger:

1. Bygg et firetre på inngangspunkter.
2. Sørg for at firetreet er balansert. Del opp naboen for hvert blad, hvis det er en for stor nabo. Dette gjentas til treet er i balanse. Vi sørger også for at for et blad med et punkt i det, er nodene for hvert blads utvidede klynge i treet.
3. For hver bladnode som inneholder et punkt, hvis den utvidede klyngen inneholder et annet punkt, deler vi treet videre og balanserer det etter behov. Hvis vi trengte å dele oss, sørger vi for hvert barn av at nodene til den utvidede klyngen er i treet (og balanserer etter behov).${\ displaystyle v}$${\ displaystyle u}$${\ displaystyle v}$${\ displaystyle u}$
4. Gjenta forrige trinn til treet er godt balansert.
5. Gjør firetreet til en triangulering.

Vi betrakter hjørnepunktene til trecellene som hjørner i trianguleringen vår. Før transformasjonstrinnet har vi en haug med esker med punkter i noen av dem. Transformasjonstrinnet utføres på følgende måte: for hvert punkt, vrir du det nærmeste hjørnet av cellen for å møte den og triangulerer de resulterende firkantene for å lage "fine" trekanter (den interesserte leseren henvises til kapittel 12 i Har-Peled for flere detaljer om hva som gjør "fine" trekanter).

De resterende firkantene er triangulert i henhold til noen enkle regler. For hver vanlig firkant (ingen punkter inne og ingen hjørnepunkter i sidene), innfør diagonalet. Vær oppmerksom på at på grunn av måten vi separerte punkter på med den velbalanserende egenskapen, er ingen firkant med et hjørne som krysser en side en som ble vridd. Som sådan kan vi triangulere firkanter med kryssende hjørner som følger. Hvis det er en krysset side, blir kvadratet til tre trekanter ved å legge til de lange diagonaler som forbinder krysset med motsatte hjørner. Hvis det er fire kryssede sider, deler vi torget i to ved å legge til en kant mellom to av de fire kryssene, og kobler deretter disse to endepunktene til de to gjenværende skjæringspunktene. For de andre rutene introduserer vi et punkt i midten og kobler det til alle fire hjørner av torget samt hvert skjæringspunkt.

På slutten av det hele har vi et fint triangulert nett av vårt punktsett bygget av et firtre.

Pseudokode

Den følgende pseudokoden viser en måte å implementere et firetre som bare håndterer poeng. Det finnes andre tilnærminger.

Forutsetninger

Det antas at disse strukturene brukes.

// Simple coordinate object to represent points and vectors
struct XY
{
    float x;
    float y;

    function __construct(float _x, float _y) {...}
}

// Axis-aligned bounding box with half dimension and center
struct AABB
{
    XY center;
    float halfDimension;

    function __construct(XY center, float halfDimension) {...}
    function containsPoint(XY point) {...}
    function intersectsAABB(AABB other) {...}
}

QuadTree klasse

Denne klassen representerer både ett firetre og noden der det er forankret.

class QuadTree
{
    // Arbitrary constant to indicate how many elements can be stored in this quad tree node
    constant int QT_NODE_CAPACITY = 4;

    // Axis-aligned bounding box stored as a center with half-dimensions
    // to represent the boundaries of this quad tree
    AABB boundary;

    // Points in this quad tree node
    Array of XY [size = QT_NODE_CAPACITY] points;

    // Children
    QuadTree* northWest;
    QuadTree* northEast;
    QuadTree* southWest;
    QuadTree* southEast;

    // Methods
    function __construct(AABB _boundary) {...}
    function insert(XY p) {...}
    function subdivide() {...} // create four children that fully divide this quad into four quads of equal area
    function queryRange(AABB range) {...}
}

Innsetting

Følgende metode setter inn et punkt i den passende kvadraten i et firetre, og deler opp om nødvendig.

class QuadTree
{
    ...
  
    // Insert a point into the QuadTree
    function insert(XY p)
    {
        // Ignore objects that do not belong in this quad tree
        if (!boundary.containsPoint(p))
            return false; // object cannot be added
    
        // If there is space in this quad tree and if doesn't have subdivisions, add the object here
        if (points.size < QT_NODE_CAPACITY && northWest == null)
        {
            points.append(p);
            return true;
        }
    
        // Otherwise, subdivide and then add the point to whichever node will accept it
        if (northWest == null)
            subdivide();
        //We have to add the points/data contained into this quad array to the new quads if we only want 
        //the last node to hold the data 
    
        if (northWest->insert(p)) return true;
        if (northEast->insert(p)) return true;
        if (southWest->insert(p)) return true;
        if (southEast->insert(p)) return true;
    
        // Otherwise, the point cannot be inserted for some unknown reason (this should never happen)
        return false;
    }
}

Spørreområde

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

class QuadTree
{
    ...
  
    // Find all points that appear within a range
    function queryRange(AABB range)
    {
        // Prepare an array of results
        Array of XY pointsInRange;
    
        // Automatically abort if the range does not intersect this quad
        if (!boundary.intersectsAABB(range))
            return pointsInRange; // empty list
    
        // Check objects at this quad level
        for (int p = 0; p < points.size; p++)
        {
            if (range.containsPoint(points[p]))
                pointsInRange.append(points[p]);
        }
    
        // Terminate here, if there are no children
        if (northWest == null)
            return pointsInRange;
    
        // Otherwise, add the points from the children
        pointsInRange.appendArray(northWest->queryRange(range));
        pointsInRange.appendArray(northEast->queryRange(range));
        pointsInRange.appendArray(southWest->queryRange(range));
        pointsInRange.appendArray(southEast->queryRange(range));
    
        return pointsInRange;
    }
}

Se også

• Adaptiv mesh -forfining
• Partisjonering av binært rom
• Binær flislegging
• Kd-tre
• Oktre
• R-treet
• UB-tre
• Romlig database
• Subpaving
• Z-ordenskurve

Referanser

Undersøkelser av Aluru og Samet gir en fin oversikt over firetrær.

Merknader

Generelle referanser

1. Raphael Finkel og JL Bentley (1974). "Quad Trees: En datastruktur for henting på sammensatte nøkler". Acta Informatica . 4 (1): 1–9. doi : 10.1007/BF00288933 . S2CID  33019699 .
2. Mark de Berg , Marc van Kreveld , Mark Overmars og Otfried Schwarzkopf (2000). Computational Geometry (2. revidert utgave). Springer-Verlag . ISBN 3-540-65620-0.CS1 -vedlikehold: flere navn: forfatterliste ( lenke ) Kapittel 14: Firetre: s. 291–306.
3. Samet, Hanan ; Webber, Robert (juli 1985). "Lagre en samling av polygoner ved hjelp av firetre" (PDF) . Hentet 23. mars 2012 .