QuadTree

Aus Das Sopra Wiki
Wechseln zu: Navigation, Suche

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

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

This is a graph with borders and nodes. Maybe there is an Imagemap used so the nodes may be linking to some Pages.

Es kann durchaus sinnvoll sein, zu leere Quads wieder zu einem zusammenzufügen. Auch sollte man sich Gedanken machen, nach welchen Kriterium man Objekte in der Welt speichert. Da gibt es typischerweise drei Möglichkeiten:

Rein positionsbasiert
Da man die Positions und Größe jedes Quads kennt kann man relativ leicht prüfen, in welchen Quad ein Objekt liegt.
Position und Objektgröße
Man schiebt das Objekt in dem Baum so lange nach oben, bis es von den Ausmaßen vollständig in ein Quad passt.
Position und Objektgröße nur in Blättern
Man hat eine Referenz auf ein Objekt in allen Quads, die von einem Objekt berührt werden.
Vergleich
Rein positionsbasiert Position und Objektgröße Position und Objektgröße nur in Blättern
Raycast schwer, da man alle Quads durchsuchen muss um sicher zu sein, daß man ein Objekt trifft mittel, da man schauen kann, ob der Ray ein Quad trifft und nur diese anschauen muss einfach, man kann die Quads nacheinander in der Richtung des Rays durchgehen
sichtbare Objekte suchen schwer, da man alle Quads durchsuchen muss einfach, da man prüfen kann, ob ein Quad sichtbar ist und dann nur die enthaltenen Objekte prüfen muß mittel, da man auch prüfen kann, ob ein Quad sichtbar ist, man aber prüfen muß, ob ein Objekt in mehreren sichtbaren Quads liegt.
Objekte verschieben sehr einfach, da man es direkt in das passende Quad legen kann mittel, man muss wieder prüfen, ob das Objekt in das aktuelle Quad passt schwer, man man alle berührten Quads aktualisieren muss

Referenzen

  1. Wikipedia Artikel zu QuadTrees