QuadTree/Einleitung: Unterschied zwischen den Versionen
Aus Das Sopra Wiki
Justus (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
Justus (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
||
Zeile 5: | Zeile 5: | ||
[[Bild:QuadTeilen.png|none|Quad teilen]] | [[Bild:QuadTeilen.png|none|Quad teilen]] | ||
Dabei | 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> |
Version vom 22. April 2009, 10:48 Uhr
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
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>