QuadTree/Einleitung: Unterschied zwischen den Versionen

Aus Das Sopra Wiki
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

Quad teilen
Quad teilen

Dabei entsteht ein Baum, der in etwa so aussehen könnte:

Ein Baum
Ein Baum
  1. Wikipedia Artikel zu QuadTrees