Quadtree

A Quadtree (más néven quadtree , 4-tree , angolul  quadtree ) egy olyan fa , amelyben minden belső csomópontnak pontosan 4 leszármazottja van. A négyfákat gyakran használják egy 2D-s tér rekurzív felosztására 4 kvadránsra (régióra). A területek négyzetek, téglalapok vagy tetszőleges alakúak. Az angol quadtree kifejezést Raphael Finkel és John Bentley alkotta meg.1974-ben. A térnek egy hasonló partíciója Q-fa néven ismert. A különböző típusú négyfák közös jellemzői:

Osztályozás

A négyfák osztályozhatók az általuk képviselt adatok típusa szerint - tér, pontok, vonalak, görbék. Feloszthatók azzal is, hogy a fa alakja függ-e az adatok feldolgozási sorrendjétől. Néhány quadfa típus:

Region quadtree

A régiónégyfa a kétdimenziós tér bármely részét reprezentálja úgy, hogy 4 kvadránsra, alnegyedre és így tovább osztja úgy, hogy a fa minden levele egy adott területnek felel meg .  A fa minden csomópontjához vagy 4 gyermek tartozik, vagy nincs is (levél). A térfelosztó négyfák nem teljesen fák, mert az alnegyedek helyzete független az adatoktól. Helyesebb név a prefix trees ( eng. trie ).  

Egy n magasságú fa 2n × 2n pixelből álló kép ábrázolására használható , ahol minden pixel értéke 0 vagy 1. A fa gyökere a kép teljes területét reprezentálja. Ha nem minden pixel csak nulla vagy csak egyes, akkor elromlik. Ebben az esetben minden lap egy pixelkészletnek felel meg – vagy csak nullák, vagy csak egyesek.

A tértörő négyfák is használhatók egy adatkészlet változó felbontásának ábrázolására. Például a hőmérséklet információ tárolható négyfaként, amelynek minden csomópontja tárolja gyermekcsomópontjainak átlaghőmérsékletét.

Ha a fát egy ponthalmaz ábrázolására használjuk (például egyes városok pozícióinak szélességi és hosszúsági fokát), a régiók fel vannak osztva addig, amíg a levelek nem tartalmaznak egynél több pontot.

pont quadtree

A pontnégyfa egyfajta bináris fa , amelyet a síkon lévő pontokról szóló információk tárolására használnak .  A fa alakja az adatok megadásának sorrendjétől függ. Az ilyen fák használata nagyon hatékony a sík rendezett pontjainak összehasonlításában, és a feldolgozási idő O(log n) .

Csomópont szerkezete

A négyes fa csomópontja, amely a sík pontjairól információt tárol, hasonló egy bináris fa csomópontjához, azzal az egyetlen figyelmeztetéssel, hogy az első csomópontnak négy gyermeke van (minden negyedhez egy) kettő helyett ("jobb" és " bal"). A csomópont kulcsnak két összetevője van ( x és y koordinátákhoz ). Így egy fa csomópont a következő információkat tartalmazza:

  • 4 mutató: quad['NW'] , quad['NE'] , quad['SW'] és quad['SE'] ,
  • pont a következőképpen írható le:
    • kulcsbillentyű , általában x és y koordinátákat fejez ki ,
    • az érték értéke , például egy név.

Edge quadtree

A vonalakkal kapcsolatos információkat tároló négyfák ( élnégyfa ) az egyenesek és görbék leírására szolgálnak .  A görbéket pontos közelítéssel írjuk le úgy, hogy a cellákat nagyon kicsikre bontjuk. Ez a fa kiegyensúlyozatlanságát okozhatja, ami indexelési problémákat jelent.

Sokszögű térkép négyfa

A sokszögekről információt tároló négyfák ( eng.  polygonal map quadtree/PMQuadtree ) tartalmazhatnak információkat sokszögekről, beleértve a degeneráltakat is (amelyek izolált csúcsai vagy lapjai vannak) [1] .

Használati esetek

A négyfák az oktáns fák ( eng.  octree ) kétdimenziós analógjai .

Pszeudokód

A következő kód a négyfák használatát mutatja be pontinformációk tárolására. Az építkezés más megközelítései is lehetségesek.

Adatstruktúrák

A következő adatstruktúrák használata várható.

// Egyszerű struktúra egy XY pont- vagy vektorstruktúra ábrázolására { float x; float y; függvény __construct( float _x , float _y) {...} } // Tengelyhez igazított határolókeret (AABB), féldimenziós központú struktúra AABB { XY központ; XY féldimenzió; function __construct( XY center, XY halfDimension) {...} függvény tartalmazzaPont( XY p) {...} függvény metszi AABB( AABB egyéb) {...} }

A QuadTree osztály

Az osztály magát a 4-fát és a gyökércsomópontot képviseli.

osztályú QuadTree { // Konstans - az egy csomópontban tárolható elemek száma állandó int QT_NODE_CAPACITY = 4; // Egy tengelyhez igazított határoló doboz // mutatja a fa AABB határvonalának határait; // Pontok XY [méret = QT_NODE_CAPACITY] pontok tömbje; // QuadTree* leszármazottai északnyugat; QuadTree* északkelet; QuadTree* délnyugat; QuadTree* délkelet; // Methods function __construct( AABB _boundary) {...} function insert( XY p) {...} function subdivide() {...} // Hozzon létre 4 gyermeket, amelyek a kvadránst 4 egyenlő részre osztják function queryRange( AABB tartomány) {...} }

Beszúrás

A következő módszer beszúr egy pontot a fa megfelelő negyedébe, szükség esetén felosztva.


class QuadTree { ... // Pont funkció beszúrása( XY p) { // A fában nem szereplő objektumok figyelmen kívül hagyása if (!boundary.containsPoint(p)) return false ; // Az objektum nem adható hozzá // Beszúrás, ha van hely if (points.size < QT_NODE_CAPACITY) { pontok hozzáfűzik(p); return true ; } // Ezután fel kell osztania a területet, és egy pontot kell hozzáadnia bármely csomóponthoz , ha (északnyugat == null ) felosztás(); if (northWest->insert(p)) return true ; if (északkelet->insert(p)) return true ; if (southWest->insert(p)) return true ; if (southEast->insert(p)) return true ; // Valamilyen oknál fogva előfordulhat, hogy a beillesztés meghiúsul (aminek tényleg nem szabadna) visszatérnie false ; } }

Belépés a tartományba

A következő módszer minden pontot megtalál egy bizonyos tartományon belül.

osztályú QuadTree { ... // Pontok keresése a tartományon belül function queryRange( AABB tartomány) { // Tömb készítése az eredményhez Array of XY pointsInRange; // Mégse, ha a tartomány nem egyezik a kvadránssal if (!boundary.insersectsAABB(tartomány)) return pointsInRange; // Üres lista // Az aktuális szintű objektumok ellenőrzése a következőhöz: ( int p := 0; p < points.size; p++) { if (tartomány.containsPoint(pontok[p])) pointInRange.append(pontok[p]); } // Leállítás, ha nincs több gyermek if (northWest == null ) return pointsInRange; // Minden gyermekpont hozzáadása pointsInRange.appendArray(northWest->queryRange(tartomány)); pointsInRange.appendArray(northEast->queryRange(tartomány)); pointsInRange.appendArray(southWest->queryRange(tartomány)); pointsInRange.appendArray(southEast->queryRange(tartomány)); return pointsInRange; } }

Lásd még

Linkek

Jegyzetek

  1. ↑ Hanan Samet és Robert Webber. „Sokszöggyűjtemény tárolása négyfák segítségével”. ACM Transactions on Graphics 1985. július: 182-222. infolab . Web. 2012. március 23
  2. ↑ Tomas G. Rokicki. Algoritmus a tér és idő tömörítésére (2006. április 1.). Letöltve: 2009. május 20. Az eredetiből archiválva : 2012. október 2..
  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, Egyesült Királyság, 2010. július.

Források

  1. Raphael Finkel és JL Bentley. Quad Trees: Adatstruktúra az összetett kulcsokon történő visszakereséshez  //  Acta Informatica : folyóirat. - 1974. - 1. évf. 4 , sz. 1 . - 1-9 . o . - doi : 10.1007/BF00288933 .
  2. Mark de Berg, Marc van Kreveld, Mark Overmars és Otfried Schwarzkopf. Számítógépes geometria  (határozatlan) . — 2. revízió. - Springer-Verlag , 2000. - ISBN 3-540-65620-0 . 14. fejezet: Quadfák: pp. 291–306.
  3. Samet, Hanan; Webber, Robert [ http://infolab.usc.edu/csci585/Spring2008/den_ar/p182-samet.pdf Sokszöggyűjtemény tárolása

Quadtrees] (1985. július). Hozzáférés dátuma: 2012. március 23. Az eredetiből archiválva : 2012. október 2.

Külső linkek