Speichern von 2D-Punkten zum schnellen Auffinden der Punkte innerhalb eines Rechtecks

Question

Ich habe eine große Anzahl von 2D-Punkten und möchte schnell diejenigen finden, die in einem bestimmten Rechteck liegen. Nehmen wir an, ein '.' ist ein beliebiger Punkt und 'X' ist ein Punkt, den ich innerhalb eines Rechtecks finden möchte, das 'T' als TopLeft- und 'B' als BottomRight-Punkt hat:

. . . . . .
. T-----+ .
. | X X | .
. +-----B .
. . . . . .

Ich habe ein std::set mit einem Sortierfaktor ausprobiert, der den TopLeft-Punkt am Anfang und den BottomRight-Punkt am Ende des Sets sortiert. Wenn ich zuerst nach dem X-Wert sortiere, würde dies dazu führen, dass die folgenden Punkte gefunden werden.

. . . . . .
. T-----+ .
X | X X | X
. +-----B .
. . . . . .

Das bedeutet, dass ich für jeden gefundenen Punkt prüfen müsste, ob er wirklich innerhalb des Rechtecks liegt. Das ist nicht wirklich gut.

Wie könnte man das besser machen?

Meine Sprache ist C++ (Windows) und ich habe sowohl die STL als auch Boost zur Verfügung.

Update

Nachdem ich die bisherigen Antworten gelesen habe, ist mir aufgefallen, dass ich nicht alle Parameter meines Problems berücksichtigt habe: Es gibt nicht ein festes Rechteck. Die Rechtecke können vom Benutzer zur Laufzeit festgelegt werden. Das bedeutet, dass das Sortieren der Punktmenge effizienter zu sein verspricht als eine lineare Suche durch alle Punkte, wie sie Artelius vor dieser Aktualisierung vorgeschlagen hat. Ich werde es aber trotzdem versuchen! Ich erwarte nicht, dass der Benutzer ein Rechteck setzt sehr häufig. Im Hinblick auf den Implementierungsaufwand könnte sich das für mich also als gute Lösung erweisen.

Answer 1

Sie können die Punkte in einem räumlichen Index mit Quad- oder R-Trees speichern. Bei einem gegebenen Rechteck könnten Sie dann alle Knoten des Baums finden, die sich mit dem Rechteck überschneiden. Sie müssten dann jeden Punkt in dieser Teilmenge vergleichen, um festzustellen, ob er in das Rechteck fällt.

Im Wesentlichen hilft Ihnen der räumliche Baum, den Suchraum zu beschneiden.

Möglicherweise können Sie eine einfachere Lösung verwenden, z. B. die Aufteilung der Punkte in Bereiche. Sagen wir, x liegt zwischen 0 und 10 als ein Bereich, 11 und 20 als ein anderer. Jede Lösung, mit der Sie den Suchraum einschränken können, ist hilfreich.

Answer 2

Siehe bitte diese Frage . Das Algorithmen-Repository von Stony Brook hat einige Implementierungen von KDTrees in C++, obwohl sie weder Teil der STL noch von Boost sind.

Answer 3

Das Sortieren eines Arrays dauert O( n Protokoll n ) Zeit. Die einfache Prüfung jedes einzelnen Punktes (ohne Sortierung) benötigt O( n ) Zeit.

Ergo, einfach durchzugehen und jeden Punkt zu überprüfen ist schneller als das Sortieren. Und es ist auch schneller, als einen Quad-Tree zu erstellen.

EDIT: Wenn Sie viele Rechtecke zu prüfen haben, ist das eine andere Sache. Aber wenn Sie nur eine kleine, feste Anzahl von Rechtecken überprüfen müssen, dann tun Sie es einfach auf die "offensichtliche" Weise!

Answer 4

Einen Quadtree verwenden, und Sie haben 3 Arten von Qtree-Knoten:

1. Knoten liegt außerhalb des Zielrechtecks: ignorieren
2. Knoten liegt innerhalb des Zielrechtecks: alle Punkte innerhalb des Knotens einbeziehen
3. Knoten liegt teilweise außerhalb des Rechtecks: Prüfung der Grenzen an Punkten innerhalb des Knotens

Answer 5

Über den Link von Yuval F. fand ich Bereichssuche die genau das zu sein scheint, wonach Sie suchen. Ich bin dort einigen Links gefolgt und habe Folgendes gefunden CGAL , eine quelloffene C++-Bibliothek, die eine Bereichssuche implementiert, mit Beispielen aquí .