Octree
Ein Octree ist in der Informatik eine Datenstruktur, genauer ein Baum, in der jeder innere Knoten bis zu acht Kinder haben kann. Das Wort Octree leitet sich von der Zahl der Kinder eines inneren Knotens ab (oct (acht) + tree (Baum) = Octree).
Diese Struktur wird hauptsächlich zur Organisation dreidimensionaler Daten im Bereich der Computergrafik eingesetzt. Jeder Knoten des Baumes repräsentiert in diesem Fall ein kubisches Volumen. Jeder interne Knoten hat acht Kinder, die das Volumen des Elternknotens in acht gleich große Kuben zerlegen. Durch rekursive Anwendung dieser Zerteilung kann das vom Wurzelknoten repräsentierte Volumen beliebig fein aufgelöst werden. Für zweidimensionale Daten verwendet man gewöhnlich Quadtrees.
Allgemeine Anwendungsgebiete für Quadtrees sind:
- Bildrepräsentation
- Raumindizierung (z. B. in Geografischen Informationssystemen)
- Hidden Surface Removal von Terraindaten.