Algorithmus zum Finden des nächsten Punktes

Ich habe eine Liste von ein paar hundert Städten mit ihren Breiten- und Längengraden. Bei einem anderen Ort (auch in Lat / Long) muss ich die nächste Stadt finden.

Da ich kein GIS verwende, besteht der naheliegende Algorithmus darin, eine Schleife für alle Städte zu erstellen und den Abstand zwischen den Punkten zu berechnen.

Die Schleife zu bilden ist für mich praktikabel, aber gibt es einen einfach zu implementierenden Algorithmus, um dies effizienter zu erreichen? Oder eine leichte Java-Bibliothek, die helfen kann, das zu lösen?

Anmerkungen : Ich benötige / möchte keine vollständige GIS-Lösung oder eine umfangreiche / komplizierte Bibliothek. Ich bevorzuge eine weniger gute, aber einfachste und leichtere Lösung, da dies die einzige Sache ist, die ich lösen muss.

Genau diese Frage habe ich vor 20 Jahren beim Entwurf eines Desktop-GIS untersucht. Wir mussten interaktiv Punkt-zu-Punkt-Entfernungen finden. Unser Ziel war es, die Berechnungen für Tausende von Punkten in weniger als einer halben Sekunde durchzuführen. Tests (auf einem 25 MHz 486 PC!) Ergaben, dass wir alle Entfernungen genau wie von Ihnen beschrieben (mit dem einfachen offensichtlichen Algorithmus) so schnell berechnen konnten, dass es keinen Sinn machte, eine komplexere Lösung wie eine Quadtree-Struktur zu erstellen .

Zur Berechnung der Entfernungen zu einem einzelnen "Sonden" -Punkt haben Sie folgende Möglichkeiten: (a) Projizieren Sie alle Punkte mit einer äquidistanten Projektion, die auf den Sondenpunkt zentriert ist, oder (b) Übernehmen Sie ein sphärisches Erdmodell und verwenden Sie die Haversine-Formel . Die erste Option ist geeignet, wenn Sie die Genauigkeit eines Ellipsoidmodells benötigen. In beiden Fällen sind die Berechnungen relativ schnell und dauern wahrscheinlich weniger als 1000 Ticks. Mit einem einzelnen Prozessor können Sie pro Sekunde rund eine Million Punkte abfragen.

Schnell genug für dich? Andernfalls lässt sich die Brute-Force-Methode leicht parallelisieren und direkt mit der Anzahl der Prozessoren skalieren: Teilen Sie einfach die Punkte unter den Prozessoren auf und führen Sie dann einen abschließenden Vergleich der Punkte durch, die jedem Prozessor am nächsten kommen.

Wenn Sie schneller fahren müssen, können Sie verschiedene Näherungswerte zum Anzeigen von Punkten verwenden. Wenn Sie sich beispielsweise zwischen -88 und +88 Grad Breitengrad befinden und der bisher gefundene nächste Punkt 200 km entfernt ist, kann ein Punkt, dessen Breitengrad sich vom Breitengrad des Prüfpunkts um mehr als 2 Grad unterscheidet, möglicherweise nicht näher sein (weil irgendwo auf Erde, ein Breitengrad übersteigt etwa 110 km). In vielen Fällen können Sie mit dieser Art der Vorprüfung Hunderte Millionen Punkte pro Sekunde verarbeiten.

Ich stimme anderen zu, dass eine einfache Schleife für "einige hundert Städte" effektiv sein sollte.

In Anbetracht Ihrer Anwendung ist der Umgang mit ellipsoiden Abständen wahrscheinlich ein großer Overkill - Sie haben es wahrscheinlich mit Wettervorhersagen zu tun, deren Lokalität nur wenige Meter beträgt. Die sphärische Geometrie ist so einfach, dass Sie dies problemlos in Ihrer Schleife tun können.

Es könnte noch einfacher sein (z. B. Delta lat als y und Delta lon * cos (lat) als x verwenden und das Minimum x ^ 2 + y ^ 2 finden). Sie verwenden den Kosinus der Zielbreite, den Sie nur einmal berechnen. Dies wird für entfernte Städte immer ungenauer, aber sie werden trotzdem abgelehnt, also spielt es keine Rolle. Unter der Annahme, dass die nächstgelegene Stadt in der Regel nur ein paar hundert Kilometer entfernt ist, ist die Wahrscheinlichkeit eines anderen Ergebnisses (nächstgelegene Stadt), das diese verwendet, im Vergleich zu einer genaueren Formel, recht gering und würde nur dann eintreten, wenn die Unterschiede so gering sind, dass "welche Prognose größer ist genau "würde wahrscheinlich sowieso von anderen Faktoren abhängen (dh: im Lärm verloren).

Wenn Sie kein eingebettetes System oder einen langsamen Interpreter verwenden, können Sie es sich wahrscheinlich leisten, nur die sphärischen Formale zu verwenden, die andere vorschlagen.

Dies ist zusätzlich zu dem, was bereits gesagt wurde, aber ich dachte, ich würde die Wichtigkeit der Auswahl einer geeigneten Datenstruktur bemerken. Ich habe meinen eigenen Code für eine K-Funktion in .NET geschrieben und festgestellt, dass die Verwendung effizienter Sammlungen die Dinge erheblich beschleunigt hat. Tut mir leid, ich kenne die O-Notation für exakte Geschwindigkeiten nicht. Ich habe zwei Wörterbücher für x- und y-Koordinaten mit der Punkt-ID als Schlüssel verwendet. Ich kenne Java nicht und kann daher nichts vorschlagen.

Prost, David