Kvadratno stablo

Regionsko kvadratno stablo

Kvadratno stablo je vrsta binarnog stabla čiji svaki unutrašnji čvor ima tačno četvoro dece. Kvadratna stabla najčešće se koriste za podelu dvodimenzionalnog prostora rekurzivnom paralelizacijom u četiri kvadranta ili regije. Regije mogu biti kvadratnog ili pravougaonog oblika, ili mogu imati proizvoljne oblike. Rafael Finkel i Džon Bentli dali su naziv ovoj strukturi podataka,Kvadratno stablo, 1974. godine. Kvadratno stablo je takođe poznato i kao Q-stablo.

Sve forme kvadratnog stabla dele neke zajedničke karakteristike:

• Razlažu prostor u prilagodljive ćelije
• Svaka ćelija ima maksimalni kapacitet. Kada se dostigne maksimalni kapacitet,ćelija se deli
• Stablo direktorijum prati prostornu dekompoziciju kvadratnog stabla

Vrste

Kvadratna stabla mogu se klasifikovati prema vrsti podataka koje oni predstavljaju,uključujući regije,tačke,prave i krive. Kvadratna stabla takođe mogu biti klasifikovana po tome da li je oblik stabla nezavisan od redosleda podataka koji obrađuje. Neki uobičajeni tipovi su:

Regionsko kvadratno stablo

Regionsko kvadratno stablo predstavlja podelu prostora u dve dimenzije tako što razlaže regiju na četiri jednaka kvadranta,podkvadranta i tako dalje, svaki lisni čvor sadrži podatke koji odgovaraju određenom podregionu. Svaki čvor u stablu ili ima tačno četvoro dece, ili nema decu (lisni čvor).

Regionsko kvadratno stablo je vrsta stabla. Regionsko kvadratno stablo dubine n može biti korišćeno za predstavljanje slike 2ⁿ x 2ⁿ piksela, gde je svaki piksel vrednosti 0 ili 1. Koreni čvor predstavlja ceo region slike. Ako pikseli u bilo kojoj regiji nisu isključivo nule ili jedinice,ona je podeljena. U ovoj prijavi,svaki lisni čvor predstavlja blok piksela koji su sve nule ili sve jedinice.

Regionsko kvadratno stablo takođe moze biti korišćeno kao reprezentacija promenljive rezolucije polja podataka.Ako se regionsko kvadratno stablo koristi pri predstavljanju skupa tačaka podataka(kao što su geografska širina i dužina skupa gradova),regioni su podeljeni dok jedan list sadrži najviše jednu tačku.

Tačkasto kvadratno stablo

Tačkasto kvadratno stablo kombinuje pristup grid struktura sa višedimenzionalnom generalizacijom stabla binarnog pretraživanja. Svaki granski(ne-lisni) čvor je povezan sa podatkovnim zapisom sa lokacijom tačke i ima četiri sledbenika (NW,NE,SW i SE). Svaka kvadrantska podela je centrirana nad podatkovnom tačkom. Vreme razvoja(izrade) kvadratnog stabla je O(n log n), a vreme traženja je O(log n).

Struktura čvora za Tačkasto kvadratno stablo

Čvor tačkastog kvadratnog stabla je sličan čvoru binarnog stabla, sa glavnom razlikom u tome što ima četiri pokazivača(jedan za svaki kvadrant) umesto dva("levi" i "desni") kao u uobičajenom binarnom stablu. Takođe,ključ se obično dekomponuje na dva dela,koje se odnose na x i y koordinate. Zato čvor sadrži sledeće podatke:

• četiri pokazivača:['NW'],['NE'],['SW'], i ['SE']
• tačku; što zauzvrat sadrži:
  • ključ, obično izražen kao x,y koordinate
  • vrednost; na primer ime

Rubno kvadratno stablo

Rubna kvadratna stabla se obično koriste za čuvanje linija više nego za čuvanje tačaka. Krive su aproksimirane paralelizacijom ćelija u veoma fine rezolucije. Ovo može dovesti do izuzetno neuravnoteženih stabala koja mogu anulirati svrhu indeksiranja.

Poligonalna mapa kvadratnog stabla

Poligonalna mapa kvadratnog stabla (ili PM Kvadratno stablo) je varijacija kvadratnog stabla, koja se koristi za skladištenje kolekcije poligona koja mogu biti degenerisana(što znači da su izolovana temena ili ivice). Postoje tri glavne klase PM Kvadratnih stabala koje variraju u zavisnosti od toga koje informacije čuvaju unutar svakog crnog čvora. PM3 kvadratna stabla mogu da skladište bilo koju veličinu ivica koje se ne seku i najviše jednu tačku. PM2 kvadratna stabla su ista kao PM3 kvadratna stabla, osim što sve ivice moraju da dele istu krajnju tačku. Konačno,PM1 kvadratna stabla slična su PM2, ali u ovom slučaju crni čvorovi mogu da ili sadrže tačku i njegove ivice, ili da sadrže skup ivica koje dele jednu tačku , ali ne može imati tačku i skup ivica koje ne sadrže tu tačku.

• Reprezentacija Kvadratnog stabla
  
• Prostorno indeksiranje
• Efikasno otkrivanje sudara u dve dimenzije
• Conway's Game of Life program.
• Kvadratna stabla se takođe koriste u oblasti fraktalne analize slike

Pseudokod

Sledeći pseudokod pokazuje jedan način implementacije kvadratnog stabla koji koristi samo tačke. Postoje i drugi pristupi na raspolaganju.

Preduslovi

Pretpostavlja se da su ove strukture korišćene.

struct XY
{
  float x;
  float y;

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

struct AABB
{
  XY center;
  XY halfDimension;

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

Klasa kvadratnog stabla

Ova klasa predstavlja i kvadratno stablo i čvor gde je ukorenjen

class QuadTree
{
  constant int QT_NODE_CAPACITY = 4;
  AABB boundary;

  Array of XY [size = QT_NODE_CAPACITY] points;

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

  // Metode
  function __construct(AABB _boundary) {...}
  function insert(XY p) {...}
  function subdivide() {...} 
  function queryRange(AABB range) {...}
}

Umetanje

Sledeći metod ubacuje tačku u odgovarajući kvadrat kvadratnog stabla.

class QuadTree
{
  ...

  // Ubacujemo tačku u kvadratno stablo
  function insert(XY p)
  {
    // Zanemarujemo objekte koji ne pripadaju ovom kvadratnom stablu
    if (!boundary.containsPoint(p))
      return false;

    // Ako ima mesta u ovom kvadratnom stablu,dodajemo objekat ovde
    if (points.size < QT_NODE_CAPACITY)
    {
      points.append(p);
      return true;
    }

    // U suprotnom,moramo podeliti na manje delove,zatim dodati tačku bilo kojem čvoru koji će to prihvatiti
    if (northWest == null)
      subdivide();

    if (northWest->insert(p)) return true;
    if (northEast->insert(p)) return true;
    if (southWest->insert(p)) return true;
    if (southEast->insert(p)) return true;

    // Inače,tačka neće biti ubačena iz nekog nepoznatog razloga
    return false;
  }
}

Ispitivanje opsega

Sledeći metod pronalazi sve tačke koje se nalaze u opsegu.

class QuadTree
{
  ...

  //Pronalazimo sve tačke koje se pojavljuju unutar opsega 
  function queryRange(AABB range)
  {
    // Priprema se niz rezultata
    Array of XY pointsInRange;

    // Automatski prekid ukoliko se opseg ne podudara sa ovim kvadratom
    if (!boundary.intersectsAABB(range))
      return pointsInRange; // empty list

    // Provera objekata
    for (int p := 0; p < points.size; p++)
    {
      if (range.containsPoint(points[p]))
        pointsInRange.append(points[p]);
    }

    // Prekida se ovde,ako nema dece
    if (northWest == null)
      return pointsInRange;

    // U suprotnom,dodajemo tačke koje pripadaju deci
    pointsInRange.appendArray(northWest->queryRange(range));
    pointsInRange.appendArray(northEast->queryRange(range));
    pointsInRange.appendArray(southWest->queryRange(range));
    pointsInRange.appendArray(southEast->queryRange(range));

    return pointsInRange;
  }
}  
 

Reference

Glavne reference

• Finkel, Raphael; J.L. Bentley (1974). „Quad Trees: A Data Structure for Retrieval on Composite Keys”. Acta Informatica. 4 (1): 1—9. doi:10.1007/BF00288933. 
• Mark de Berg; et al. (2000). „Quadtrees”. Computational Geometry (2nd revised изд.). Springer-Verlag. стр. 291–306. ISBN 978-3-540-65620-3. 
• Samet, Hanan; Webber, Robert (jul 1985). „Storing a Collection of Polygons Using Quadtrees” (PDF). Архивирано из оригинала (PDF) 17. 06. 2012. г. Приступљено 23. 3. 2012. 

Spoljašnje veze

• Diskusija o kvadratnom stablu
• Javascript implementacija kvadratnog stabla korišćena za detekciju kolizije
• Java Implementacija
• C++ implementacija kvadratnog stabla koje se koristi za prostorno indeksiranje trouglova