Sortieren/Suchen im zweidimensionalen Raum

hustbaer

Ist sie doch wenn ich ihn richtig verstehe, ist ja nur eine Optimierung.
D.h. es dauert ggf. ein wenig länger, aber es kommt dasselbe raus.

Sebastian Pizer

crt32 schrieb:

Ich habe eine (unsortierte) Liste mit beliebig vielen Objekten, deren Position im zweidimensionalen Raum durch Bounding Boxes (dh X,Y,Länge,Breite) bestimmt ist.

Nimm einen "Loose Quadtree" (2D Version eines "Loose Octree"). Es handelt sich dabei um eine hierarchische Datenstruktur, die Dein Problem lösen kann. Nachdem Du den Baum aufgebaut hast, kannst Du die Suche rekursiv programmieren. Jeder Knoten hält dabei eine Liste von Objekten. Ein Objekt ist in höchstens einem Knoten gespeichert.

Pseudocode:

void ausgeben(Objekt const& o);

void ausgeben(LQT_Knoten* k) {
  für alle objekte o aus l->objlist {
    ausgeben(o);
  }
  für alle Kinder-Zeiger c aus k->children {
    ausgeben(c);
  }
}

void ausgeben(LQT_Knoten* k, Rechteck const& r) {

  Rechteck schnitt = schnittmenge(k->boundingbox, r);

  if (empty(schnitt))
    return;

  if (schnitt == k->boundingbox)
    return ausgeben(k);

  // Ok, nichtleerer Schnitt, aber bounding box des knotens nicht
  // komplett in r drin --> weiter testen

  für alle objekte o aus l->objlist {
    if (ist_im_rechteck(o,r))
      ausgeben(o);
  }
  für alle Kinder-Zeiger c aus k->children {
    ausgeben(c,r);
  }
}

Damit müsste der Aufwand irgendwas wie O(log(n)+g) sein, wenn Du n Objekte im Baum speicherst und g davon ausgegeben werden. (habe ich jetzt eher geraten -- kannst Du ja mal nachgucken).

knivil

Es gibt noch eine nette Variante des "Octree"s bzw "Quadtree"s, falls man "Objekte mit Ausdehnung" und keine Punkte speichern will. --> "Loose Octree".

Dafuer habe ich auch ein Quadtree verwendet (inklusive bewegender Objekte).

Bei einem Loose Octree enthält jeder Knoten (nicht nur die Blätter) eine Liste von Objekten, welche nicht mehr in die Kind-Knoten reingepasst haben (weil zu groß) oder einfach schon auf der untersten Ebene des Baums hängen. Objekte fallen beim Einfügen "tief genug", weil ich die Boundingboxen der Knoten überlappen.

Das ist ein normaler Quadtree.

Selbst mit dem aufbauen des Trees, was in unoptimiertem Zustand in jedem Frame geschieht

Warum soll das bei jedem Frame neu geschehen? Das macht ja alle Vorteile kaputt.

Ich denke, dass das ebenfalls einen enormen Performance Schub geben kann.

Deine beschriebenen Optimierungen sind eine vernuenftige Implementation und nicht bloss ein Feature.

Sebastian Pizer

knivil schrieb:

Es gibt noch eine nette Variante des "Octree"s bzw "Quadtree"s, falls man "Objekte mit Ausdehnung" und keine Punkte speichern will. --> "Loose Octree".

Dafuer habe ich auch ein Quadtree verwendet (inklusive bewegender Objekte).

Bei einem Loose Octree enthält jeder Knoten (nicht nur die Blätter) eine Liste von Objekten, welche nicht mehr in die Kind-Knoten reingepasst haben (weil zu groß) oder einfach schon auf der untersten Ebene des Baums hängen. Objekte fallen beim Einfügen "tief genug", weil ich die Boundingboxen der Knoten überlappen.

Das ist ein normaler Quadtree.

Es gibt schon Unterschiede zwischen "loose" und "nicht-loose", auf die ich aber gar nicht genau eingegangen bin.

Es ist auch die Frage, was der Fragesteller genau haben möchte. Möchte er alle Objekte aufzählen, deren Bounding-Boxen das Abfragerechteck schneiden, oder möchte er nur die Objekte aufzählen, deren Bounding-Boxen komplett im Abfragerechekt enthalten sind? Ich bin einfach mal vom ersten Fall ausgegangen.

Das Problem mit "normalen Quadtrees" ist, dass auch winzig kleine Objekte noch in den obersten Ebenen des Baums hängen bleiben, wenn sie genau auf der Grenze zwischen Bounding-Boxen benachbarter Knoten liegen. Bei der "loose"-Variante kann entsprechend der Größe des Objekts eine Mindesttiefe garantiert werden (je kleiner desto tiefer hängt's im Baum), weil sich die Bounding-Boxen der Knoten überlappen. Diese Änderung beeinflusst auch die Anzahl der erforderlichen Objekt<->Rechteck Abfragen.

drakon

knivil schrieb:

Selbst mit dem aufbauen des Trees, was in unoptimiertem Zustand in jedem Frame geschieht

Warum soll das bei jedem Frame neu geschehen? Das macht ja alle Vorteile kaputt.

Wenn sich die Objekte ständig verschieben, dann braucht man das, sofern man die genannte Optimierung nicht macht, was ich in der ersten Version natürlich noch nicht hatte.

Ich denke, dass das ebenfalls einen enormen Performance Schub geben kann.

Deine beschriebenen Optimierungen sind eine vernuenftige Implementation und nicht bloss ein Feature.

Das das so üblich ist wusste ich nicht, weil ich das mehr oder weniger intuitiv so gemacht und nicht gross Theorie dahinter gelesen habe. Und da ich es noch nicht ausprobiert habe (weil ich noch an anderen Ecken arbeite), habe ich gesagt, dass ich mir das gut vorstellen kann.

Wenn wir schon dabei sind. Hast du einen guten Link mit anderen möglichen Optimierungen?

crt32

In meiner bisherigen Implementierung ist das Neuberechnen vom gesamten Baum in jedem Frame deutlich schneller als das löschen und wieder einfügen von verschobenen Objekten.
Ich hab letzteres zwar noch nicht optimiert, bin mir aber relativ sicher, dass welche Methode schneller ist davon abhängt, wieviele Objekte pro Frame verschoben werden. (wird sich aber noch zeigen ;))
/edit: Ok, bringt tatsächlich eine merkbare Verbesserung

Gibt es zum loose quadtree/octtree irgendwo genauere Informationen? Ich habe bisher nur herausgefunden, dass es dazu wohl einen Artikel in Game Programming Gems 1 gibt, aber ich hab zur zeit keinen Zugang zur UB wo ich das besorgen könnte. Außerdem hab ich das hier gefunden, woraus ich aber bisher noch nicht ganz schlau werde.

knivil

Wenn wir schon dabei sind. Hast du einen guten Link mit anderen möglichen Optimierungen?

Nein (Obwohl in Game Programming Gems X stand mal was zu Loose Octrees drin). Ich habe das auch intuitiv so gemacht. Was man sich aber noch fuer Kollisionserkennung ueberlegen kann:
- Hat man ein Gebiet mit z.B. grossen statischen Objekten, so braucht man dort keine Verfeinerung des Gitters, da sowieso nur das grosse statische Objekt dort ist. So hat man ein nicht homogenes Gitter und spart Speicherplatz (da Knotenzahl mit der Tiefe exponetiell zunimmt).
- Grosse statische Objekte kann man auch in die unterste Ebene druecken und mehreren Knoten zuordnen (wobei dazugesagt sei, dass ich bei Kollisionserkennung eines Objektes immer nur gegen Objekte des aktuellen Knotens und Kind- (Kind-, Kind- ...)knoten teste. (Dabei kann es passieren, dass Kollisionsereignisse doppelt auftreten -> Hashset loest das Problem).

In meiner bisherigen Implementierung ist das Neuberechnen vom gesamten Baum in jedem Frame deutlich schneller als das löschen und wieder einfügen von verschobenen Objekten.

Kommt drauf an, mein Quadtree ist statisch. Fuer Bewegende Objekte: Ich teste in jedem Frame, ob sich das Objekt noch in dem entsprechenden Bereich des Knotens befindet, falls nicht, so wird es eine Ebene hoeher verschoben. Wiederholt wird das eben solange bis es passt (up). Dann wird geschaut, ob das Objekt eins der 4 Kindknoten zugeordnet werden kann. Solange wiederholt, bis es nicht mehr geht (down). Das alles liegt in O(1) und nutzt die Lokalitaet der Objekte aus. In einem kleinen Zeitschritt veraendert sich eben auch wenig. Im schlimmsten Fall ist es doppelt so teuer, wie Loeschen und Einfuegen, aber das kommt vergleichsweise recht selten vor.

Link: Loose Octree in Game Programming Gems(selbst aber noch nicht gelesen)

Idee:

Ginge es nicht auch so, dass man mit vier sortierten Listen arbeitet, je eine für x-upperleft, y-upperleft, x-lowerright, y-lowerright. Dann benötigt jedes Objekt noch eine ID so dass man in den Listen suchen kann (List hier im Sinne der passenden Datenstruktur gemeint). Das ist m.E. effizienter als die Lösung mit den Kacheln, da ich hier nur die Koordinaten betrachte, die wirklich die Ausdehnung des Rechecks bestimmen.

Frage:

Kennt jemand ein _gutes_ Buch zu "Computational Geometry" wo diese Sachen eigentlich drin stehen sollten? Die Gedanken haben sich sicherlich schon schlauere Leute als ich gemacht.

Habe gerade, den http://compgeom.cs.uiuc.edu/~jeffe/compgeom/books.htmlLink gefunden

drakon

knivil schrieb:

In meiner bisherigen Implementierung ist das Neuberechnen vom gesamten Baum in jedem Frame deutlich schneller als das löschen und wieder einfügen von verschobenen Objekten.

Kommt drauf an, mein Quadtree ist statisch. Fuer Bewegende Objekte: Ich teste in jedem Frame, ob sich das Objekt noch in dem entsprechenden Bereich des Knotens befindet, falls nicht, so wird es eine Ebene hoeher verschoben. Wiederholt wird das eben solange bis es passt (up). Dann wird geschaut, ob das Objekt eins der 4 Kindknoten zugeordnet werden kann. Solange wiederholt, bis es nicht mehr geht (down). Das alles liegt in O(1) und nutzt die Lokalitaet der Objekte aus. In einem kleinen Zeitschritt veraendert sich eben auch wenig. Im schlimmsten Fall ist es doppelt so teuer, wie Loeschen und Einfuegen, aber das kommt vergleichsweise recht selten vor.

Genau so habe ich mir das auch vorgestellt und denke ich eigentlich auch vorhin mal beschrieben.
Der Fall, dass es teurer werden kann ist mir ebenfalls durch den Kopf, aber wie du auch sagst bin ich zum Schluss gekommen, dass es wohl kaum vorkommen wird und wenn schon, dann lohnt es sich dennoch im Gesamten das so zu machen.

Statische Objekte werden dann natürlich ein einem seperaten Tree eingefügt, welcher niemals neu geordnet wird (ausser in Ausnahmefällen natürlich).

knivil

Statische Objekte werden dann natürlich ein einem seperaten Tree eingefügt, welcher niemals neu geordnet wird (ausser in Ausnahmefällen natürlich).

Ich habe mich bewusst gegen diese Variante entschieden, da ich statische Objekte bei der Kollisionserkennung genauso behandeln moechte wie sich bewegende.

drakon

knivil schrieb:

Statische Objekte werden dann natürlich ein einem seperaten Tree eingefügt, welcher niemals neu geordnet wird (ausser in Ausnahmefällen natürlich).

Ich habe mich bewusst gegen diese Variante entschieden, da ich statische Objekte bei der Kollisionserkennung genauso behandeln moechte wie sich bewegende.

Ja. Ich bin mir nicht 100% sicher, ob ich das wirklich so mache, weil es wirklich kaum etwas ausmacht, wenn die Objekte nicht neu eingeteilt werden müssen.

Die Behandlung wäre denke ich nicht so gross anderst.

life

Hier steht übrigens auch was über Loose-Octrees drin (letzten 24 Seiten):

http://wwwhni.uni-paderborn.de/fileadmin/hni_alg/lehre/SS2009/algocg/algocgTrees.pdf