Was ist der schnellste Weg, um herauszufinden, welche Koordinaten sich in einem bestimmten Umkreis befinden?

Question

Nehmen wir an, ich habe eine Datenbank mit 100.000 Koordinaten, Ich muss herausfinden, welche weniger als 1 Meile von einer bestimmten Koordinate entfernt sind. ?

Was ist der effizienteste Weg, dies zu tun (in jeder Sprache)

Answer 1

Erstens haben wir eine grundlegende Funktion zu schreiben, um den Abstand zwischen zwei Punkten zu berechnen:

function distance(lat1, lon1, lat2, lon2) {} 

Für dieses Beispiel , Ich werde die Funktion auf die Formel einer sphärischen Erde projiziert auf eine Ebene basieren (here) Zuerst müssen wir die Deltas (der Abstand in Grad zwischen den Lat und Longs) und die mittlere Breite (Durchschnitt der Breiten) berechnen:

Jetzt

dLat = dLat * 180/3.1415926535; 
dLon = dLon * 180/3.1415926535; 
mLat = mLat * 180/3.1415926535; 

, verwenden wir die Formel unsere Daten in Abstand zu verwandeln:

var dLat = lat1 - lat2; 
var dLon = lon1 - lon2; 
var mLat = (lat1 + lat2)/2; 
var earthRadius = 3959; //in miles 

Dann wandeln wir diejenigen zu Radiant mit d=180/PI rad

var distance = earthRadius * (dLat * dLat + Math.pow(Math.cos(mLat) * dLon, 2)); 

und gibt die Entfernung

return distance; 

Jetzt, nur durch alle Punkte und ch wenn die Entfernung für jeden in Ordnung ist. Nehmen sich an einem Punkt, auf diese Weise beschrieben wird:

var p = { 
    lat = ... 
    lon = ... 
} 

Und vorausgesetzt, es gibt eine Liste von Punkten (zum Beispiel genannten Punkte) und ein Bezugspunkt (zum Beispiel genannt ref).

Sie können auch nach der Breite-Grenze-Box suchen - Longitude erfordert komplexere Berechnungen und es ist nur eine Verschwendung von Zeit. Sie können eine Meile in Grad ist 1/69 deg/mile (etwa 0,1449 Grad) bestimmen. So können Sie überprüfen, welche Punkte außerhalb dieses Grenzkasten sind:

var result = [] 
var maxLat = ref.lat + 0.1449; 
var minLat = ref.lat - 0.1449; 
points.forEach(function (d) { 
    if (d.lat > maxLat || d.lat < minLat) continue; 
    if (distance(d.lat, d.lon, ref.lat, ref.lon) <= 1) { 
     result.push(d); 
    } 
}; 

Dazu sollte Finish mit einer Reihe von Punkten, die näher als 1 Meile vom Referenzpunkt sind.

Ich könnte einen Fehler in der Formel Dinge haben (Ich bin eher wie ein Programmierer als ein Mathematiker). Also überprüfe, ob sie mit dem Wikipedia-Artikel arbeiten, zu dem ich einen Link hinzugefügt habe.