Quadtree

Quadtree (myös quadtree , 4-tree , englanniksi  quadtree ) on puu , jossa jokaisella sisäisellä solmulla on täsmälleen 4 jälkeläistä. Nelipuita käytetään usein jakamaan rekursiivisesti 2D-avaruus 4 kvadranttiin (alueeseen). Alueet ovat neliöitä, suorakulmioita tai niillä on mielivaltainen muoto. Englanninkielisen termin quadtree loivat Raphael Finkel ja John Bentley .vuonna 1974. Samanlainen avaruusosio tunnetaan Q-puuna. Eri tyyppisten nelipuiden yhteisiä piirteitä:

Luokitus

Nelospuut voidaan luokitella niiden edustaman datatyypin mukaan - avaruus, pisteet, viivat, käyrät. Ne voidaan myös jakaa sillä, riippuuko puun muoto tietojen käsittelyjärjestyksestä. Joitakin nelipuita:

Alueen quadtree

Alueneljäspuu edustaa mitä tahansa kaksiulotteisen avaruuden osaa jakamalla se 4 kvadranttiin, alaneljännekseen ja niin edelleen, jolloin jokainen puun lehti vastaa tiettyä aluetta .  Jokaisella puun solmulla on joko 4 lasta tai ei ollenkaan (lehtiä). Avaruutta jakavat nelipuut eivät ole täysin puita, koska osakvadranttien sijainti on tiedosta riippumaton. Oikeampi nimi on etuliitepuut ( eng. trie ).  

Puuta, jonka korkeus on n , voidaan käyttää kuvaamaan 2n × 2n pikselistä koostuvaa kuvaa , jossa jokaisen pikselin arvo on 0 tai 1. Puun juuri edustaa koko kuvan aluetta. Jos kaikki pikselit eivät ole vain nollia tai vain ykkösiä, se rikkoutuu. Tässä tapauksessa jokainen arkki vastaa pikselien joukkoa - joko vain nollia tai vain ykkösiä.

Tilaa rikkovia nelipuita voidaan käyttää myös esittämään tietojoukon muuttuvaa resoluutiota. Esimerkiksi lämpötilatiedot voidaan tallentaa nelipuuna, jonka jokainen solmu tallentaa lapsisolmujensa keskilämpötilan.

Jos puuta käytetään edustamaan pistejoukkoa (esimerkiksi joidenkin kaupunkien sijaintien leveys- ja pituusaste), alueet jaetaan alaryhmiin, kunnes lehdet sisältävät enintään yhden pisteen.

point quadtree

Pisteneliöpuu on eräänlainen binääripuu, jota käytetään tallentamaan tietoja tason pisteistä .  Puun muoto riippuu siitä, missä järjestyksessä tiedot on määritetty. Tällaisten puiden käyttö on erittäin tehokasta tason järjestellisten pisteiden vertailussa ja käsittelyaika on O(log n) .

Solmurakenne

Nelipuun solmu, joka tallentaa tietoja tason pisteistä, on samanlainen kuin binääripuun solmu, ja ainoa varoitus, että ensimmäisellä solmulla on neljä lasta (yksi jokaiselle neljännekselle) kahden sijaan ("oikea" ja " vasemmalle”). Solmuavaimessa on kaksi komponenttia ( x- ja y -koordinaateille ). Siten puusolmu sisältää seuraavat tiedot:

  • 4 osoitinta: quad['NW'] , quad['NE'] , quad['SW'] ja quad['SE'] ,
  • kohta kuvataan seuraavasti:
    • näppäin , ilmaisee yleensä x - ja y - koordinaatit ,
    • arvon arvo , esimerkiksi nimi.

Edge quadtree

Nelipuita, jotka tallentavat tietoja viivoista ( reunaneliöpuu ), käytetään kuvaamaan suoria viivoja ja käyriä .  Käyrät kuvataan tarkoilla approksimaatioilla jakamalla solut hyvin pieniksi. Tämä voi aiheuttaa puun epätasapainon, mikä tarkoittaa indeksointiongelmia.

Monikulmiokarttaneliöpuu

Nelosipuut, jotka tallentavat tietoa polygoneista ( eng.  polygonal map quadtree/PMQuadtree ), voivat sisältää tietoa monikulmioista, mukaan lukien rappeutuneet (joilla on eristetyt kärjet tai pinnat) [1] .

Käyttötapaukset

Quadtrees on kaksiulotteinen analogi oktanttipuille ( eng.  octree ).

Pseudokoodi

Seuraava koodi osoittaa nelipuiden käytön pistetietojen tallentamiseen. Myös muut lähestymistavat rakentamiseen ovat mahdollisia.

Tietorakenteet

Seuraavia tietorakenteita odotetaan käytettävän.

// Yksinkertainen rakenne edustamaan piste- tai vektorirakennetta XY { kellua x; kellua y; funktio __construct( float _x, float _y) {...} } // Axis-aligned bounding box (AABB), puolimittainen keskitetty rakenne AABB { XY- keskus; XY puolimitta; funktio __construct( XY center, XY halfDimension) {...} funktio sisältääPiste( XY p) {...} funktio leikkaaAABB ( AABB muu) {...} }

QuadTree-luokka

Luokka edustaa itse 4-puuta ja juurisolmua.

luokan QuadTree { // Vakio - yhteen solmuun tallennettavien elementtien määrä vakio int QT_NODE_CAPACITY = 4; // Akselilinjattu rajauslaatikko // näyttää puun AABB rajan rajat; // Pisteet XY [koko = QT_NODE_CAPACITY] pisteen ryhmä; // QuadTreen* luoteisjälkeläiset; QuadTree* koilliseen; QuadTree* lounaaseen; QuadTree* kaakkois; // Metodit function __construct( AABB _boundary) {...} function insert( XY p) {...} function subdivide() {...} // Luo 4 alaosaa, jotka jakavat kvadrantin 4 yhtä suureen osaan function queryRange( AABB- alue) {...} }

Lisää

Seuraava menetelmä lisää pisteen sopivaan puun neljännekseen ja halkaisee tarvittaessa.


luokka QuadTree { ... // Lisää pistefunktion lisäys( XY p) { // Ohita objektit, jotka eivät ole puussa, jos (!boundary.containsPoint(p)) palauttaa false ; // Objektia ei voi lisätä // Lisää jos on tilaa if (points.size < QT_NODE_CAPACITY) { pisteet append(p); return true ; } // Seuraavaksi sinun on jaettava alue ja lisättävä piste mihin tahansa solmuun if (northWest == null ) subdivide(); if (northWest->insert(p)) return true ; if (koillis->lisää(p)) return true ; if (lounas->lisää(p)) return true ; if (southEast->insert(p)) return true ; // Jostain syystä lisäys saattaa epäonnistua (mitä sen ei todellakaan pitäisi) palauttaa false ; } }

Alueen syöttäminen

Seuraava menetelmä löytää kaikki pisteet tietyltä alueelta.

luokan QuadTree { ... // Etsi pisteitä alueen sisällä funktio queryRange( AABB range) { // Valmistele taulukko tulokselle Array of XY pointsInRange; // Peruuta, jos alue ei vastaa kvadranttia if (!boundary.insersectsAABB(alue)) return pointsInRange; // Tyhjä lista // Tarkista nykyisen tason kohteet ( int p := 0; p < points.size; p++) { if (alue.containsPoint(points[p])) pointsInRange.append(points[p]); } // Pysäytä, jos lapsia ei ole enää if (northWest == null ) return pointsInRange; // Lisää kaikki alipisteet pointsInRange.appendArray(northWest->queryRange(range)); pointsInRange.appendArray(northEast->queryRange(range)); pointsInRange.appendArray(southWest->queryRange(alue)); pointsInRange.appendArray(southEast->queryRange(alue)); return pointsInRange; } }

Katso myös

Linkit

Muistiinpanot

  1. ↑ Hanan Samet ja Robert Webber. "Monikulmioiden kokoelman tallentaminen nelipuiden avulla". ACM Transactions on Graphics Heinäkuu 1985: 182-222. infolab . Web. 23. maaliskuuta 2012
  2. ↑ Tomas G. Rokicki. Algoritmi tilan ja ajan pakkaamiseen (1. huhtikuuta 2006). Haettu 20. toukokuuta 2009. Arkistoitu alkuperäisestä 2. lokakuuta 2012.
  3. ↑ Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, Density Trees for Efficient Nonlinear State Estimation , Proceedings of the 13th International Conference on Information Fusion, Edinburgh, Yhdistynyt kuningaskunta, heinäkuu 2010.

Lähteet

  1. Raphael Finkel ja JL Bentley. Quad Trees: Tietorakenne yhdistelmäavainten hakua varten  //  Acta Informatica : päiväkirja. - 1974. - Voi. 4 , ei. 1 . - s. 1-9 . - doi : 10.1007/BF00288933 .
  2. Mark de Berg, Marc van Kreveld, Mark Overmars ja Otfried Schwarzkopf. Laskennallinen geometria  (epämääräinen) . - 2. tarkistettu. - Springer-Verlag , 2000. - ISBN 3-540-65620-0 . Luku 14: Quadtrees: s. 291-306.
  3. Samet, Hanan; Webber, Robert [ http://infolab.usc.edu/csci585/Spring2008/den_ar/p182-samet.pdf Polygonien kokoelman tallentaminen käyttäen

Quadtrees] (heinäkuu 1985). Käyttöpäivä: 23. maaliskuuta 2012. Arkistoitu alkuperäisestä 2. lokakuuta 2012.

Ulkoiset linkit