Quadtree
Ein Quadtree ist in der Informatik eine spezielle Baum-Struktur, in der jeder innere Knoten bis zu vier Kinder haben kann. Das Wort Quadtree leitet sich von der Zahl der Kinder eines inneren Knoten 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.
Weblinks
- Spatial Index Demos
- Quadtree Applet (englisch)
- Raumunterteilungsdemos (englisch)
