Speichern von 2D-Punkte für schnellen Abruf von denen im inneren eines Rechtecks

Question

Ich habe eine große Anzahl von 2D-Punkte, und ich möchte, um schnell diejenigen, die sich in einem bestimmten Rechteck.Sagen wir mal ein '.' ist jeder Punkt und 'X' ist ein Punkt möchte ich im inneren finden Sie ein Rechteck, die hat 'T' als TopLeft und 'B' als BottomRight Punkte:

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

Ich habe einen std::set, die eine Art functor, welche Arten der TopLeft-Punkt am Anfang und am BottomRight am Ende des Satzes.Bei der Sortierung nach X-Wert zuerst, so hätte dies die folgenden Punkte, gefunden zu werden.

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

Das bedeutet ich müsste das Kontrollkästchen jeder gefundenen Stelle, ob es wirklich innerhalb des Rechtecks.Nicht wirklich gut.

Was wäre ein besserer Weg, dies zu tun?

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

Update

Mit Lesen die Antworten so weit, ich merkte, dass ich noch nicht entfallen sämtliche Parameter der mein problem:Es gibt nicht die eine Feste Rechteck.Rechtecke können eingestellt werden zur Laufzeit durch den Benutzer.Dies bedeutet, dass die Sortierung der Punkte, die verspricht, effizienter zu sein als eine lineare Suche durch alle Punkte, wie vorgeschlagen, durch Artelius, bevor Sie dieses update.Ich werde es ausprobieren, aber!Ich erwarte nicht, dass der Benutzer ein Rechteck sehr Häufig.Also in Bezug auf die Umsetzung bemühen, es könnte zeigen, bis zu werden eine gute Lösung für mich.

Answer 1

Könnten Sie speichern die Punkte in einem räumlichen index mit quad-oder r-Bäume.Dann das Rechteck, das Sie finden konnte, dass alle Knoten des Baumes, die sich überlappen, würden Sie dann zu vergleichen, jeder Punkt dieser Teilmenge zu sehen, wenn es fällt in das Rechteck.

In Essenz, die räumliche Struktur hilft, Sie beschneiden die Suche nach Raum.

Sie können möglicherweise verwenden Sie eine einfachere Lösung, wie die Partitionierung der Punkte reicht.Sagen, wo x ist von 0,10 als einen Bereich, 11,20, wie der andere.Jede Lösung, dass können Sie beschneiden die Suche nach space helfen.

Answer 2

Finden diese Frage. The Stony Brook Algorithm Repository einige Implementierungen von KDTrees in C++, obwohl Sie nicht Teil der STL-noch Steigern.

Answer 3

Sortieren eines Arrays in O(nanmeldenn- ) Zeit.Einfach die Kontrolle jeder Punkt einzeln (ohne Sortierung) O(n- ) Zeit.

Ergo, einfach nur durch und überprüfen Sie jeden Punkt ist schneller als das Sortieren.Und es ist schneller als der Bau einer quadtree zu.

EDIT:Wenn Sie haben viele Rechtecke, um zu überprüfen, es ist eine andere Geschichte.Aber wenn Sie nur überprüfen müssen, um eine kleine, Feste Anzahl von Rechtecken nur dann nicht der "offensichtlichen" Weise!

Answer 4

verwenden Sie einen quadtree, und Sie haben 3 Arten von qtree Knoten:

1. Knoten, die außerhalb der Ziel-Rechteck:ignorieren
2. Knoten in der Ziel-Rechteck:zählen Sie alle Punkte im inneren Knoten
3. Knoten teilweise außerhalb des Rechtecks:tun bounds check on Punkte im inneren Knoten

Answer 5

Folgende Yuval F link, den ich gefunden Bereichssuche, die zu sein scheint, die genaue Art der Sache, die Sie suchen.Ich folgte einige links von dort, und fand CGAL, ein open-source-C++ - Bibliothek, die implementiert eine Reihe Suche, mit Beispielen hier.

Answer 6

Ihre Art Funktion überprüfen konnten Punkte werden Hinzugefügt, für den innen-und-die-Rechteck-ness, und Sortieren Sie alle Punkte innerhalb des Rechtecks, bevor alle Punkte außerhalb des Rechtecks.Sie würde haben zu verfolgen, wie viele vorhanden sind, oder verwenden Sie eine binäre Suche auf den gesamten Satz zu finden, den cutoff-Punkt-lookup-Zeit.