Arborele cadramentului

Această intrare sau secțiune despre programare nu citează sursele necesare sau cei prezenți sunt insuficienți . Puteți îmbunătăți această intrare adăugând citate din surse de încredere în conformitate cu liniile directoare privind utilizarea surselor .

Un arbore cu cvadrament cu puncte.

Un copac quadrament, ^[1] adesea menționată ca „quadtree“, este neechilibrată structura de date arbore în care toate nodurile interne au exact patru noduri copil. Quadrees sunt adesea folosite pentru partiționarea unui spațiu bidimensional împărțindu-l recursiv în patru cadrane, denumite în mod obișnuit Nord-Est , Nord-Vest , Sud-Est , Sud- Vest .

Utilizările comune ale acestui tip de structuri sunt următoarele:

• Reprezentarea imaginilor;
• Indexarea spațială;
• determinarea coliziunilor în două dimensiuni;
• Stocare de date rare, cum ar fi stocarea informațiilor de formatare pentru o calcul tabelar sau matrice.

Copaci Quadrament sunt cei doi corespondenți dimensionale de copaci octale (numite „octree“).

Quadtrees sunt structuri de date de copac în care imaginea este împărțită în 4 cadrane; procedând în sensul acelor de ceasornic și pornind de la cel din stânga sus, pentru fiecare cadran se verifică dacă este uniform: dacă nu, procedura se repetă pentru acel cadran până când se ating zone uniforme (cel mult ajungeți la pixelul unic) .

Arborii cadramentului ca reprezentări spațiale 2D

Arborii de cvadramente PR (Punct de regiune) reprezintă un set de puncte în două dimensiuni care descompun regiunea care le conține în patru subcadrante, care pot fi, la rândul lor, descompuse și așa mai departe până la nodurile frunzei. Criteriile de oprire utilizate în general sunt două:

• Frunza conține un număr de puncte mai mic decât un număr maxim predeterminat
• Frunza are o zonă minimă

Pseudo cod

Clasa QuadTree

Această clasă reprezintă atât un arbore de cvadrament cât și un nod în care este înrădăcinată.

 clasa QuadTree
{
  // Constanta arbitrară pentru a indica câte elemente pot fi stocate în acest nod de arbore quad
  constant int QT_NODE_CAPACITY = 4;

  // Cutie de limitare aliniată la axă stocată ca un centru cu jumătăți de dimensiuni
  // pentru a reprezenta limitele acestui arbore quad
  Limita AABB ;

  // Puncte în acest nod arbore quad
  Matrice de puncte XY [size = QT_NODE_CAPACITY] ;

  // Copii
  QuadTree * nord-vest;
  QuadTree * nord-est;
  QuadTree * sud-vest;
  QuadTree * sud-est;

  // Metode
  funcție __construct ( AABB _boundary) {...}
  inserare funcție ( XY p) {...}
  function subdivide () {...} // creați patru copii care împart pe deplin acest quad în patru quads de zonă egală
  function queryRange (gama AABB ) {...}
}

Inserare

Următoarea metodă introduce un punct în zona dorită a unui arbore de cvadrament.

 clasa QuadTree
{
  ...

  // Introduceți un punct în QuadTree
  inserare funcție ( XY p)
  {
    // Ignorați obiectele care nu aparțin acestui arbore quad
    if (! borderary.containsPoint (p))
      returnează fals ; // obiectul nu poate fi adăugat

    // Dacă există spațiu în acest arbore quad, adăugați obiectul aici
    if (points.size <QT_NODE_CAPACITY)
    {
      points.append (p);
      întoarce-te adevărat ;
    }

    // În caz contrar, împărțiți și adăugați punctul oricărui nod care îl va accepta
    if (nord-vest == nul )
      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 ;

    // În caz contrar, punctul nu poate fi inserat dintr-un motiv necunoscut (acest lucru nu ar trebui să se întâmple niciodată)
    returnează fals ;
  }
}

Interval de interogare

Următoarea metodă găsește toate punctele conținute într-un interval.

 clasa QuadTree
{
  ...

  // Găsiți toate punctele care apar într-un interval
  function queryRange (gama AABB )
  {
    // Pregătiți o serie de rezultate
    Matrice de puncte XYInRange;

    // Anulați automat dacă intervalul nu intersectează acest quad
    if (! boundary.intersectsAABB (interval))
      returnează punctele ÎnRange; // listă goală

    // Verificați obiectele la acest nivel quad
    for ( int p: = 0; p <points.size; p ++)
    {
      if (range.containsPoint (points [p]))
        pointsInRange.append (puncte [p]);
    }

    // Terminați aici, dacă nu există copii
    if (nord-vest == nul )
      returnează punctele ÎnRange;

    // În caz contrar, adăugați punctele de la copii
    pointsInRange.appendArray (northWest → queryRange (range));
    pointsInRange.appendArray (northEast → queryRange (range));
    pointsInRange.appendArray (southWest → queryRange (range));
    pointsInRange.appendArray (southEast → queryRange (range));

    returnează punctele ÎnRange;
  }
}

Notă

Elemente conexe

• R-copac
• Algoritmul Barnes-Hut

Alte proiecte

• Wikimedia Commons conține imagini sau alte fișiere pe Quadtree

linkuri externe

• Spatial Index Demos , pe cs.umd.edu , Universitatea din Maryland.

Portal IT : accesați intrările Wikipedia care se ocupă cu IT