Schneller Algorithmus zum Auffinden aller Punkte innerhalb eines Rechtecks ​​

Question

Gegeben eine Menge von Punkten im 2D-Raum und ein Rechteck (Koordinaten aller vier Punkte, Seiten parallel zur xy-Achse) Wie finde ich schnell heraus, welche Punkte innerhalb des Rechtecks ​​liegen?

Ich bin nicht an der grundlegenden Lösung interessiert, alle Punkte durchzugehen und zu sehen, welche innerhalb des Rechtecks ​​ist. Nach was ich suche, ist ein Algorithmus, der mir schnelle Abfragezeiten pro Rechteck gibt.

Es ist mir egal, wie viel Zeit ich im Vorverarbeitungsschritt verbringen. Mir ist wichtig, dass ich nach der Verarbeitung meiner Daten eine nützliche Struktur erhalte, die mir schnelle Abfragezeiten pro Rechteck gibt.

Ich weiß zum Beispiel kann ich zählen, wie viele Punkte ich in einem Rechteck in O (logN) habe. Das funktioniert, weil ich am Anfang sehr viel Verarbeitung mache und dann die verarbeiteten Daten jedes Mal mit einem neuen Rechteck abfrage und eine neue Anzahl in LogN-Zeit erhalte. Ich suche nach einem ähnlichen Algorithmus, um die tatsächlichen Punkte zu finden, nicht nur ihre Anzahl.

Answer 1

Eine klassische Antwort ist der kD-Baum (in diesem Fall 2D-Baum).

Für eine einfache Alternative, wenn Ihre Punkte gleichmäßig genug verteilt sind, können Sie versuchen, durch Rasterung.

Wählen Sie eine Zellengröße für ein quadratisches Gitter aus (wenn das Problem anisotrop ist, verwenden Sie ein rechteckiges Gitter).Weisen Sie jeden Punkt der Rasterzelle zu, die ihn enthält, und speichern Sie ihn in einer verknüpften Liste. Suchen Sie beim Ausführen einer Abfrage alle Zellen, die vom Rechteck überlappt werden, und scannen Sie sie, um ihre Listen zu durchlaufen. Für die teilweise abgedeckten Zellen müssen Sie den Punkt-in-Rechteck-Test durchführen.

Die Wahl der Größe ist wichtig: zu groß kann dazu führen, dass zu viele Punkte ohnehin getestet werden müssen; zu klein kann zu vielen leeren Zellen führen.

Answer 2

Wenn Sie die Punkte nach der X-Achse sortieren, sollten Sie in der Lage sein, eine binäre Suche durchzuführen, um den am weitesten links liegenden (kleinsten X-Wert) Punkt im Rechteck zu finden.

Führen Sie eine weitere binäre Suche durch, um den am weitesten rechts liegenden (größten X-Wert) Punkt im Rechteck zu finden.

Alle Punkte in der sortierten Liste zwischen diesen beiden Punkten befinden sich innerhalb der linken und rechten Grenzen des Rechtecks, obwohl Sie die meisten davon nie überprüft haben!

Wiederholen Sie den Vorgang auf der vertikalen/Y-Achse.

---

Die beiden binären Suchen entlang der X-Achse sollten beide O (logN) sein.
Gleiches mit den zwei binären Suchen entlang der Y-Achse.
O (4 log N) == O (log N)

Es wird immer noch am Ende eine Art von Merge-Schritt sein, dass ich nicht sofort sicher bin.

Answer 3

Ich denke, Sie sollten Ihre Punkte in einem quadtree speichern. Ich habe die Details nicht ausgearbeitet, aber es sollte grundsätzlich etwas Ähnliches wie eine binäre Suche ermöglichen, die direkt die Punkte ergibt, die sich innerhalb eines Rechtecks ​​befinden.

Wenn Ihre Punkte gruppiert sind, d. H. Es gibt Cluster, die viele Punkte in einem kleinen Bereich enthalten, und andere Bereiche, die keine oder sehr wenige Punkte enthalten, könnte sogar noch besser sein.

Laufzeit Komplexität sollte O (logN) Ich denke.

Answer 4

Sie könnten Punkt in Sektoren gruppieren. Wenn ein Sektor vollständig innerhalb oder außerhalb des gegebenen Rechtecks ​​liegt, sind alle Punkte innerhalb oder außerhalb des Sektors ebenfalls vorhanden. Wenn ein Sektor teilweise in ist, müssen Sie O (n) nach Punkten in diesem Sektor suchen, um zu überprüfen, ob sie sich in dem Rechteck befinden. Suchen Sie nach k-d tree Suche.

Answer 5

Sie suchen nach kd-tree range search oder Bereich Abfrage.

Quadtrees (oder octtrees oder 16-trees ...) sind besser, wenn sich Punkte ändern, aber Sie erwarten eine gleichmäßige Verteilung. Es sind keine weiteren Ausgleichsschritte erforderlich, da die Struktur des Baumes festgelegt ist.

kd-Bäume schneiden auf einer festen Punktmenge besser ab, selbst bei ungleichmäßiger Verteilung. Wenn sich der Punktsatz ändert, ist es schwer (aber nicht unmöglich), selbstabgleichende Schritte durchzuführen.

AABB-Bäume (oder dicke AABB-Bäume) bieten eine schnelle Möglichkeit, überlappende Formen zu testen, nicht nur Punkte. AABB-Bäume müssen gelegentlich ausgeglichen werden. Wenn sich ständig bewegende Objekte enthalten sind, ist es üblich, "fette AABB-s" zu verwenden, so dass Sie den Baum nicht in jedem Frame aktualisieren müssen.

Sortierung von nur einer Achse und binäre Suche (etwas wie abelenky vorgeschlagen, aber ich denke, es hat keinen Sinn, eine zweite binäre Suche zu tun) ist eine einfache und elegante Lösung, aber wird langsam, wenn Sie zum Beispiel sortieren X-Achse, und alle Punkte sind auf einer Linie parallel zu Y. Sie müssen eine lineare Filterung auf die Punkte, die durch die binären Suchvorgänge von X übereinstimmen. Zeitkomplexität ist schlimmsten Fall O(n), aber dieser schlimmste Fall passiert ziemlich oft.

Alle diese Algorithmen führen Abfragen im Durchschnitt O(log n + k) durch, wobei k die Anzahl der übereinstimmenden Punkte ist.

Gridding, wie Yves vorgeschlagen, kann Bereichssuche in O(k) Zeit ausführen, aber nur, wenn die Größe des Abfrage-Rechtecks ​​begrenzt ist. Dies tun sie oft in particle simulations. Das Gridding kann auch verwendet werden, wenn der Eingabebereich nicht begrenzt ist - Sie müssen nur eine feste Anzahl von Buckets basierend auf dem Hash der Gitterkoordinaten erstellen. Wenn das Abfrage-Rechteck jedoch eine beliebige Größe haben kann, ist das Gridding ein No-Go.

Answer 6

Zusammen mit anderen Antworten können Sie auch in Morton-Codes (Sortierreihenfolge der Sortierreihenfolge) nachsehen.

In Ihrem Fall sind das statische Daten, Sie können sogar die gesamten Punktdaten als Array darstellen.

https://en.wikipedia.org/wiki/Z-order_curve

Dieses Papier hat auch eine ziemlich komplizierte Chronologie der verschiedenen „multi-dimensionale Zugriffsmethoden“ - http://www.cc.gatech.edu/computing/Database/readinggroup/articles/p170-gaede.pdf