QuadTree
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=4
Dabei entsteht ein Baum, der in etwa so aussehen könnte:
- ↑ Wikipedia Artikel zu QuadTrees