Was ist besser als Begrenzungsboxen?

Question

Ich habe ein Szenario, in dem ich X -Millionen -Längengrad -Breitengradpunkte habe.

Wenn ein neuer Long/Lat -Punkt hinzugefügt wird, möchte ich es wissen effizient Welche anderen Punkte befinden sich innerhalb eines benutzerkonfigurierten Distanzparameters, sodass ich sie einer Liste hinzufügen kann.

Hast du etwas Besseres als Begrenzungsboxen?

Ich würde gerne Algorithmen, Referenzen und ein paar Implementierungen sehen;) Vielen Dank!

Answer 1

Es gibt einige Optionen, die besser sind, hauptsächlich basieren auf Weltraumpartitionierung.

Eine häufige und oft sehr gute Option (was nicht zu schwer zu implementieren ist) ist, a zu verwenden KD-Baum. Quadtrees sind einfacher zu implementieren, aber langsamer für die Suche. Abhängig von der Verteilung Ihrer Daten und Ihrer Anforderungen können andere Space Partitioning -Algorithmen besser abschneiden, niedrigere Speicheranforderungen oder andere damit verbundene Probleme haben.

Answer 2

Ein Kollege erzählte mir, dass er gute Erfahrungen mit der Verwendung hatte Morton-Code Als räumlicher Index für GIS -Daten ist dies vielleicht etwas, das es wert ist, untersucht zu werden.

Answer 3

Dieser schnelle und schrägliche Ansatz kann Ihnen einige Trauer ersparen: Teilen Sie die Oberfläche der Erde in 1-Grad-Kisten. Sie haben dann ein 180x360-Element-Array und müssen nur eine kleine Anzahl von Kästchen durchsuchen, einschließlich des Box mit dem neuen Punkt und allen Kästchen unmittelbar um sie, für die sich eines der Ecken innerhalb der benutzerdefinierten Entfernung befindet. Sie werden feststellen, dass es einige Tricks gibt, mit denen Sie schnell herausfinden können, welche Boxen verwendet werden sollen, ohne sie alle zu berücksichtigen. Vergessen Sie einfach nicht Breiten- und Längengrad-Wrack.

Wenn Ihre "nur" Millionen von Punkten haben und sie nicht in Hotspots zusammengefasst sind, könnte das Sie durchbringen.

Ein theoretisch überlegener Weg: Sie können jeden Punkt in dreidimensionalen Raum abbilden und sie dann in einem speichern Octree, wodurch Sie schnell in der Nähe von Punkten in einer willkürlichen Entfernung finden können. Natürlich unterscheidet sich die Entfernung des dreidimensionalen Raums geringfügig von der Großkreisentfernung auf der Welt, sodass Sie einen Konvertierungsfaktor berechnen müssen. Das sollte jedoch einfach sein. Sie erwähnen keine Implementierungssprache, aber es wird mit ziemlicher Sicherheit eine gut getestete Octree-Implementierung für jede Sprache geben, in der Sie arbeiten. Wenn es Ihnen nichts ausmacht, den Code von Drittanbietern einzufügen, ist diese Lösung der Weg zu gehen.