Nächste N nächste Geo-Punkte

Question

Ich habe in meiner Android-Anwendung eine Datenbanktabelle mit Geo Pointes (lat und lon sind Dezimalgrad-Werte), etwa 1000 Punkte. Und ich muss 20 nächstgelegenen Punkt zu einem gegebenen Geo-Punkt auswählen.

Ich habe bei Stackoverflow die Antwort gefunden, wie man Abstand zwischen zwei geo Punkten berechnet und war sehr glücklich, bis ich versuchte, meine Frage zu schreiben. Ich habe herausgefunden, dass es nicht möglich ist trignometrische Funktionen in der integrierten SQLite von Android zu verwenden.

Aber dann habe ich eine Idee. Ich muss nicht wirklich eine Entfernung berechnen. In der Nähe eines Punktes liegt der kleinere Unterschied in ihren Geo-Koordinaten.

Wie könnte ich diese Tatsache verwenden? Wäre es ausreichend, die gespeicherten Punkte nach (lat_0 - lat_n)^2 + (lon0-lon_n)^2 zu ordnen, wobei lat_0 und lon_0 Geokoordinaten eines gegebenen Punktes sind?

Danke,

Mur

UPD

der beste Weg, eine Antwort auf meine Frage zu bekommen war also Ansatz zu testen, die ich oben beschrieben.

Es funktioniert ziemlich gut, aber nicht wirklich genau mit der genauen Entfernung verglichen.

Also, wenn Sie nur eine Strecke berechnen müssen, ist diese Lösung in Ordnung, aber in meinem Fall musste ich auch Stationen nach Entfernung bestellen und konnte diese Lösung nicht verwenden.

Mein Dank geht John bei CashCommons und Philip. Danke Jungs

Answer 1

Wenn Ihre Punkte innerhalb einer Stadt (mehr oder weniger) getrennt sind, wird diese Annäherung gut funktionieren. Die Annäherung fällt jedoch auseinander, wenn Sie weltweit gehen.

EDIT: Basierend auf Philip Kommentar unten, sollten Sie eine der Komponenten skalieren. Deutschland ist etwa 50 Grad nördlicher Breite, also multipliziert die Länge mit (cos 50 Grad) wird besser.

Answer 2

Ja. :-) Die tatsächliche Entfernung ist sqrt ((lat_0 - lat_n)^2 + (lon0-lon_n)^2), aber die Anordnung nach (lat_0 - lat_n)^2 + (lon0-lon_n)^2 ist ausreichend.

Answer 3

Hmm ... Ich bin mir nicht sicher, wie diese Bestellung funktionieren würde? Brauchst du nicht für jeden Punkt eine andere Reihenfolge, um seine Nachbarn anzuzeigen?

Die einfachste Lösung besteht darin, einfach alle Punkte zu durchlaufen und die geometrical distance zwischen den Punkten zu berechnen. Für 1000 Punkte sollte das ziemlich schnell passieren.

Die am besten optimierte Lösung (in Bezug auf die Abrufgeschwindigkeit) besteht darin, die Nachbarn jedes Punkts zu berechnen, wenn Sie sie in die Datenbank einfügen. Zum Beispiel können Sie die Liste der IDs als separate Komma-Zeichenfolge beibehalten und in die Datenbank einfügen. Dann, wenn du Nachbarn brauchst, machst du direkt mit ihnen. Dies wird jedoch zu einem Problem werden, wenn Sie neue Punkte einfügen müssen. Im Grunde müssen Sie die Nachbarn neu berechnen.