Datenstruktur gesucht (Überlappung in 2D)

Hallo!

Ich suche eine Datenstruktur, um 2D-Rechtecke zu verwalten.

Die Datenstruktur soll folgendes möglichst performant leisten

• Initialisieren mit Rechtecken
• Hinzufügen von Rechtecken
• Entfernen von Rechtecken
• Abfrage: Welche Recktecke überlappen mit einem gegebenen Rechteck.

Die Abfrage ist das wichtigste.

Es werden bis etwa 1000 Rechtecke gespeichert, eine Abfrage sollte maximal wenige Millisekunden dauern.

Beim Googlen bin ich auf R tree, R+ tree, R* tree, Quad Tree, A tree usw. gestoßen.

Kennt jemand von euch eine C# implementierung einer datenstruktur, die obige Anforderungen erfüllt? Möglichst nicht kostenpflichtig?

Vielen Dank,
Uwe

Hallo,

zB C# QuadTree
Das Rectangle auch nicht (ganz) vergessen 😉

mfG Gü

Hallo!

Danke für den Link. Das Problem ist, dass ich vermutlich mich in den Datenstrukturen nicht genau auskenne, aber ich weiß nicht, ob mir ein QuadTree wirklich hilft (er macht zwar was ähnliches, aber ich weiß nicht, wie ich ihn anwenden soll).

Mir ist klar, wie ich punkte in QuadTrees sortieren kann. Aber wie funktioniert die Überlappungs-Abfrage?

Schau dir doch erstmal die Links an, die dir rausgesucht werden! Dann hättest du auch die Rectangle.Intersect-Methode gefunden.

Schau dir doch erstmal die Links an, die dir rausgesucht werden! Dann hättest du auch die Rectangle.Intersect-Methode gefunden.

Ähm, ja. Den link habe ich gesehen, aber der nützt ja nix. Damit kann ich überprüfen, ob sich zwei Rechtecke überlappen. Aber wie man nun effizient eine Menge von Rechtecken verwalten kann, steht da nicht. Ich will die ja nicht paarweise prüfen (dann hätte eine Abfrage lineare Laufzeit!).

Hallo Uwe81,

naja – MrSparkles Post ist durchaus eine sinnvolle Antwort auf deine Frage:

Aber wie funktioniert die Überlappungs-Abfrage?

Aber zurück zu deiner Frage:

Aber wie man nun effizient eine Menge von Rechtecken verwalten kann, steht da nicht

Du musst natürlich nicht jedes einzelne Rechteck des QuadTrees durchlaufen und auf eine eventuelle Überschneidung mit einem gegebenen Rechteck prüfen, sondern kannst dir die skalierbare Auflösungsfähigkeit des QuadTrees zunutze machen. So kannst du prüfen, ob sich ein Quadrant mit dem gegebenen Rechteck überschneidet. Tut er das nicht, tut es auch keins seiner Kind-Rechtecke. Tut er es doch, durchläufst du diesen Vorgang rekursiv und testest die Kind-Rechtecke, bis alle durchlaufen worden sind.

m0rius