QuadTree/Einleitung: Unterschied zwischen den Versionen
Zur Navigation springen
Zur Suche springen
Justus (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
Vogty (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
||
| (3 dazwischenliegende Versionen von einem anderen Benutzer werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
Ein QuadTree<ref>[[wikipedia:de: | Ein QuadTree<ref>[[wikipedia:de:Quadtree|Wikipedia Artikel]] zu QuadTrees</ref> 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''=<tt> | Im folgenden Beispiel wird angenommen, daß ''n''=<tt>4</tt> | ||
[[Bild:QuadTeilen.png|none|Quad teilen]] | [[Bild:QuadTeilen.png|none|Quad teilen]] | ||
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