Sortieren/Suchen im zweidimensionalen Raum

crt32

Hallo!

Folgendes Problem:
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.
Ich will jetzt möglichst effizient alle Objekte auflisten, die in einem bestimmten Rechteck liegen.
Derzeit mache ich das so, dass ich einfach durch alle Objekte in der Liste durchiteriere und jedesmal prüfe, ob die jew. Bounding Box das gegebene Rechteck schneidet.
Das Problem ist, dass mein Programm sozusagen so aussieht (aufs wesentliche beschränkt):

1. für jedes Objekt in der Liste:
1.a verschiebe Objekt
1.b konstruiere Rechteck
1.c liste alle Objekte in diesem Rechteck auf
2. zurück zu 1...

Dh die Laufzeit ist offensichtlich quadratisch, und mein Programm verbringt ca. 2/3 der Zeit in der Funktion, die die Objekte innerhalb eines Rechtecks auflistet.

Wie kann ich meine Liste so organisieren, dass ich darin effizient suchen kann?
Gleichzeitig müssen die Objekte aber immer noch effizient verschoben werden können.

Ich dachte zunächst an einen Quadtree, nur dann habe ich das Problem, dass sobald ich ein Objekt verschiebe, ich das Objekt gegebenenfalls sehr zeitaufwendig in einen anderen Knoten verschieben muss. (gibt es eventuell einen Algorithmus o.ä., mit dem man letzteres effizient lösen kann?)

Eine weitere Idee war, die Liste einfach nach X-Koordinaten zu sortieren und anschließend schön mit Intervallschachtelung zu suchen.
Daran gefällt mir aber nicht, dass das ganze dann nur effektiv ist, wenn die Objekte auch in X-Richtung verteilt sind, und klappt zB gar nicht gut, wenn die Objekte vertikal angeordnet sind, oder sogar in X- und Y-Richtung gleichermaßen verteilt sind.

Bin für jede Idee dankbar!

SeppJ

Wie wäre es damit:

Du zerlegst dem Raum in Kacheln. Für jede Kachel hast du eine Liste, die angibt, welche Objekte aus der Liste in dieser Kachel liegen. Egal ob ganz oder teilweise, das heißt ein Objekt kann durchaus in mehreren Kachellisten vertreten sein. Wenn du dann deinen Suchbereich hast, dann guckst du, in welchen Kacheln der Suchbereich liegt. Und dann brauchst du nur die Objekte in den Listen zu diesen Kacheln zu überprüfen.

Das Verschieben, Löschen oder Neuanlegen eines Objektes sollte recht einfach und zeitsparend machbar sein. Der große Performancefresser wird das erstmalige Anlegen der Kachellisten sein. Aber das muss man nur einmal machen, daher sollte das insgesamt sehr effizient sein.

Die optimale Größe der Kacheln kann ich dir nicht sagen, da muss ein Informatiker ran, ich schätze mal, wenn ein Objekt durchschnittlich in 4 bis 9 Listen vertreten ist, dürftest du ganz gut dabei sein. Experimentier da mal ein bisschen rum.

Dieses Verfahren ist inspiriert durch die Celllists in der Molekulardynamik:
http://en.wikipedia.org/wiki/Cell_lists

hustbaer

Wenn die Grenzen deiner "Welt" endlich sind, dann kannst du ein Grid verwenden.
Jede Kachel im Grid hat eine Liste aus Zeigern auf Objekte welche die Kachel teilweise "bedecken".

Wie performant/sinnvoll diese Variante ist, hängt von einigen Dingen ab, die ich nicht wissen kann, wie z.B. wie stark die Grösse der Bounding-Boxen variiert etc.

Wenn die zu indizierende Fläche gross wird, kann man so ein Grid auch hierarchisch machen, analog zum Mip-Mapping bei Texturen oder einem hierarchischen Z-Buffer.

EDIT: oha, zu langsam

EDIT2: da gibts noch Info über andere Verfahren, die aber vermutlich auch nicht sehr gut für Bewegungsdaten geeignet sind:
http://en.wikipedia.org/wiki/Spatial_index

Fellhuhn

Wobei die Listen natürlich geupdatet werden müssen wenn die Objekte sich bewegen. Octtree heißt das verfahren oder irgendwie so im 3D-Bereich. Geht natürlich auch als Quadtree im 2D-Bereich. Die Zellgröße ist dabei variabel, je nach Dichte.

crt32

Danke, das mit dem Grid ist eine ganz gute Idee und wird umgesetzt

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

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.

drakon

Ich benutze dafür auch einen Quadtree, um 1000 Objekte Gegeneinander auf Kollision zu prüfen. Selbst mit dem aufbauen des Trees, was in unoptimiertem Zustand in jedem Frame geschieht (eben wegen den Positionen) ist das ganze bei einer solchen grossen Zahl immer noch sehr performant (im Vergleich).

Wenn nur einzelne Objekte verändert werden müssen, dann geht das eigentlich schon recht fix, wenn man ihn einfach entfernt und nochmal einfügt. Man kann das ganze natürlich noch verbessern, indem man anstatt den ganzen Baum zu neu zu füllen einfach mal alle Objekte durch geht und schaut, ob sie noch in dem Quad vom letzten Frame liegen, was die meisten wahrscheinlich tun. Dann kann man dijenigen, die es nicht tun zuerst mit den Schwesternelementen vergleichen und ggf. gleich dort neu einfügen, anstatt nochmal von oben anzufangen. Ich denke, dass das ebenfalls einen enormen Performance Schub geben kann.

Fellhuhn

Die Berechnung sollte aber doch eigentlich unabhängig von den Frames sein.

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.