QuadTree/Einleitung: Unterschied zwischen den Versionen
Aus Das Sopra Wiki
Justus (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
Vogty (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
||
Zeile 6: | Zeile 6: | ||
Dabei entsteht ein Baum, der in etwa so aussehen könnte: | Dabei entsteht ein Baum, der in etwa so aussehen könnte: | ||
[[Datei:Quadtree tree.png|none|Ein Baum]] | |||
<graphviz> | <!--<graphviz> | ||
digraph B { | digraph B { | ||
Wurzel -> 1; | Wurzel -> 1; | ||
Zeile 18: | Zeile 18: | ||
2 -> 2.4; | 2 -> 2.4; | ||
} | } | ||
</graphviz> | </graphviz> --> |
Aktuelle Version vom 16. Oktober 2020, 13:42 Uhr
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