Oktre

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 19. maj 2016; checks kræver 13 redigeringer .

En okttræ ( oktanttræ , oktaltræ , engelsk  okttræ ) er en type trædatastruktur , hvor hver intern knude har præcis otte "børn". Oktale træer bruges mest til at underinddele 3D-rum ved rekursivt at opdele det i otte celler. Octrees er 3D-analogen af ​​quadtrees . Det engelske navn "octree" er dannet af okt + træ og staves normalt "octree" i stedet for "octtree".

Rumrepræsentation efter oktre

Hver node i  oktanttræet deler rummet op i otte nye oktanter . Ved punktregionen  (PR ) af oktreet gemmer knudepunktet et eksplicit 3D-punkt, der er "centret" af ruminddelingen for den knude. Dette punkt definerer et af hjørnerne af hvert af de otte underordnede rum. I et MX-oktræ er splitpunktet det implicitte centrum af det rum, som noden repræsenterer. Rodknudepunktet i et PR-oktræ kan repræsentere et uendeligt rum. Rodknudepunktet for et MX-oktræ skal repræsentere et afgrænset område af rummet, så implicitte centre er veldefinerede. Oktræer kan ikke betragtes som k-dimensionelle træer , da k-dimensionelle træer deler sig langs en dimension, mens oktræer deler sig omkring et punkt. Også k-dimensionelle træer er altid binære , hvilket ikke er sandt for oktre.

Generel brug af oktre

Ansøgning om farvekvantisering

Octree-algoritme til farvekvantisering, opfundet af Gerwauz og Purgathofer i 1988, koder billedfarvedata som en oktre ni niveauer dyb. Brugen af ​​oktreet forklares ved, at der i RGB -systemet er tre farvekomponenter. Denne algoritme er meget hukommelseseffektiv, fordi træets størrelse kan begrænses. Oktreets nederste (basis)niveau består af bladknuder , som akkumulerer farvedata, som ikke er repræsenteret i træet ; disse noder indeholder oprindeligt 1 bit. Hvis en meget større mængde farvepalet end ønsket er indtastet i oktreet, så kan størrelsen af ​​oktreet reduceres kontinuerligt ved at søge efter en node på det lavere (basis)niveau og midlerne dens bitdata til et nodeblad, krympende del af træet. Når hentet er afsluttet, udforsker træet alle stierne ned til knudebladene, idet der tages hensyn til bits langs søgestien. Denne proces vil resultere i et omtrentligt antal nødvendige farver.  

Brug af oktre i specifikke applikationer

Eksterne links

Engelsksprogede kilder Russisksprogede kilder
  Gå til Wikidata-elementet  Ordbøger og encyklopædier