- Quadtree
-
Quadtree: Die Farbe eines Quadranten in der grafischen Darstellung (links) entspricht der Farbe des zugehörigen Blatts im Baum (rechts).
Ein Quadtree, der aus Konturdaten erstellt wurde.Ein Quadtree ist in der Informatik eine spezielle Baum-Struktur, in der jeder innere Knoten genau vier Kinder hat. Das Wort Quadtree leitet sich von der Zahl der Kinder eines inneren Knotens ab (quad (vier) + tree (Baum) = Quadtree).
Diese Struktur wird hauptsächlich zur Organisation zweidimensionaler Daten im Bereich der Computergrafik eingesetzt. Die Wurzel des Baumes repräsentiert dabei eine quadratische Fläche. Diese wird rekursiv in je vier gleich große Quadranten zerlegt bis die gewünschte Auflösung erreicht ist und die Rekursion in einem Blatt endet. Durch rekursive Anwendung dieser Zerteilung kann die vom Wurzelknoten repräsentierte Fläche beliebig fein aufgelöst werden. Für dreidimensionale Daten verwendet man gewöhnlich Octrees.
Da ein Blatt unter Umständen eine verhältnismäßig große Fläche abdecken kann, ist die Datenstruktur relativ speichersparend und schnell nach einem Blatt, das einen bestimmten Punkt beinhaltet, zu durchsuchen.
Allgemeine Anwendungsgebiete für Quadtrees sind:
- Bildrepräsentation
- Flächenindizierung (zum Beispiel in GIS-Programmen)
- Effiziente Kollisionserkennung (Collision Detection) im Zweidimensionalen
- Hidden Surface Removal von Terraindaten.
- Bei der Gittererzeugung werden Quadtrees für die Generierung der 2D-Triangulierung verwendet.
Literatur
- Hanan Samet, The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading, MA, 1990. ISBN 0-201-50255-0.
- Hanan Samet, Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS. Addison-Wesley, Reading, MA, 1990. ISBN 978-0201503005.
Weblinks
Wikimedia Foundation.
