QuadTree/Einleitung
Aus Das Sopra Wiki
Ein QuadTree[1] 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
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>
- ↑ wikipedia:de:QuadTree Wikipedia Artikel