QuadTree/Einleitung: Unterschied zwischen den Versionen
Zur Navigation springen
Zur Suche springen
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, 14: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