QuadTree/Einleitung: Unterschied zwischen den Versionen

Aus Das Sopra Wiki
Keine Bearbeitungszusammenfassung
Keine Bearbeitungszusammenfassung
Zeile 5: Zeile 5:
[[Bild:QuadTeilen.png|none|Quad teilen]]
[[Bild:QuadTeilen.png|none|Quad teilen]]


Dabei versucht man eine gewisse Größe der einzelnen Quads nicht zu unterschreiten.
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

Quad teilen
Quad teilen

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>