QuadTree/Einleitung

Ein QuadTree ist eine Datenstruktur mit der eine 2-Dimensionale Welt repräsentiert werden kann. Die Welt wird dazu in vier gleich große Rechtecke eingeteilt. Damit man viele Objekte effizient organisieren kann wird nur eine bestimmte Anzahl n Objekte in einer Zalle (Quad) gespeichert. Falls die gespeicherte Anzahl der Objekte n übersteigt wird das betroffene Quad in vier neue Quads geteilt und die vorhandenen Objekte auf die vier neuen Quads verteilt.

Im folgenden Beispiel wird angenommen, daß n=5

Quad teilen

Dabei entsteht ein Baum, der in etwa so aussehen könnte:

<graphviz> digraph B {

           Wurzel -> 1;
           Wurzel -> 2;
           Wurzel -> 3;
           Wurzel -> 4;
           2 -> 2.1;
           2 -> 2.2;
           2 -> 2.3;
           2 -> 2.4;

} </graphviz>