Octree

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 19 mai 2016; verificările necesită 13 modificări .

Un octree ( arbore octant , arbore octal , în engleză  octree ) este un tip de structură de date arborescentă în care fiecare nod intern are exact opt ​​„copii”. Arborii octali sunt cel mai frecvent folosiți pentru a subdiviza spațiul 3D, împărțindu-l recursiv în opt celule. Octrees sunt analogul 3D al quadtrees . Numele englezesc „octree” este format din oct + tree și este de obicei scris „octree” mai degrabă decât „octtree”.

Reprezentarea spațiului de către octree

Fiecare nod din arborele  octanți împarte spațiul în opt noi octanți. În regiunea punctului (PR ) a octree-ului, nodul stochează un punct 3D explicit care este „centrul” diviziunii spațiului pentru acel nod. Acest punct definește unul dintre colțurile fiecăruia dintre cele opt spații copil. Într-un octree MX, punctul de împărțire este centrul implicit al spațiului pe care îl reprezintă nodul. Nodul rădăcină al unui octree PR poate reprezenta un spațiu infinit. Nodul rădăcină al unui octree MX trebuie să reprezinte o regiune delimitată a spațiului, astfel încât centrele implicite să fie bine definite. Octreii nu pot fi considerați arbori k-dimensionali , deoarece arborii k-dimensionali se împart de-a lungul unei dimensiuni, în timp ce octreii se împart în jurul unui punct. De asemenea, arborii k-dimensionali sunt întotdeauna binari , ceea ce nu este adevărat pentru octrees.  

Utilizarea generală a octrees

Aplicație pentru cuantificarea culorilor

Algoritm Octree pentru cuantificarea culorilor, inventat de Gerwauz și Purgathofer în 1988, codifică datele de culoare ale imaginii ca un octree de nouă nivele adâncime. Utilizarea octree-ului se explică prin faptul că în sistemul RGB există trei componente de culoare. Acest algoritm este foarte eficient în memorie deoarece dimensiunea arborelui poate fi limitată. Nivelul inferior (de bază) al octree-ului este format din noduri frunze , care acumulează date de culoare care nu sunt reprezentate în arbore; aceste noduri conțin inițial 1 biți. Dacă în octree este introdusă o cantitate mult mai mare de paletă de culori decât cea dorită, atunci dimensiunea octree poate fi redusă continuu prin căutarea unui nod la nivelul inferior (de bază) și făcând o medie a datelor sale de biți într-o frunză de nod, o parte care se micșorează. a copacului. Odată ce preluarea este completă, arborele explorează toate căile până la frunzele nodale, ținând cont de biții de-a lungul căii de căutare. Acest proces va avea ca rezultat un număr aproximativ de culori necesare.  

Utilizarea octrees în aplicații specifice

Link- uri externe

surse în limba engleză surse în limba rusă
  Accesați articolul Wikidata  Dicționare și enciclopedii