Come posso stimare rapidamente la distanza tra due punti (latitudine, longitudine)?

Question

Voglio essere in grado di ottenere una stima della distanza tra due punti (latitudine, longitudine). Voglio eseguire l'undershoot, poiché questo sarà per la ricerca del grafico A * e voglio che sia veloce. I punti saranno al massimo a 800 km di distanza.

Answer 1

Le risposte a Haversine Formula in Python (Bearing and Distance between two GPS points) forniscono implementazioni Python che rispondono alla tua domanda.

L'implementazione di seguito I ha eseguito 100.000 iterazioni in meno di 1 secondo su un laptop precedente. Penso che per i tuoi scopi questo dovrebbe essere sufficiente. Tuttavia, dovresti profilare qualsiasi cosa prima di ottimizzare per le prestazioni.

from math import radians, cos, sin, asin, sqrt 
def haversine(lon1, lat1, lon2, lat2): 
    """ 
    Calculate the great circle distance between two points 
    on the earth (specified in decimal degrees) 
    """ 
    # convert decimal degrees to radians 
    lon1, lat1, lon2, lat2 = map(radians, [lon1, lat1, lon2, lat2]) 
    # haversine formula 
    dlon = lon2 - lon1 
    dlat = lat2 - lat1 
    a = sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2 
    c = 2 * asin(sqrt(a)) 
    # Radius of earth in kilometers is 6371 
    km = 6371* c 
    return km

Da sottovalutare haversine(lat1, long1, lat2, long2) * 0.90 o qualsiasi altro fattore si desideri. Non vedo come sia utile introdurre errori nella tua sottostima.

Answer 2

Un'idea per la velocità è trasformare le coordinate long/lat coordinate in 3D (x, y, z). Dopo aver preelaborato i punti, usa la distanza euclidea tra i punti come undershoot calcolato rapidamente della distanza effettiva.

Answer 3

Per la massima velocità, è possibile creare qualcosa come un rainbow table per le distanze delle coordinate. Sembra che tu conosca già l'area con cui stai lavorando, quindi sembra che il pre-computing possa essere fattibile. Quindi, potresti caricare la combinazione più vicina e usarla.

Ad esempio, negli Stati Uniti continentali, la longitudine è di 55 gradi e la latitudine è 20, che corrisponde a 1100 punti interi. La distanza tra tutte le combinazioni possibili è una handshake problem a cui risponde (n-1) (n)/2 o circa 600k combinazioni. Sembra abbastanza fattibile per archiviare e recuperare. Se fornisci ulteriori informazioni sui tuoi requisiti, potrei essere più specifico.

Answer 4

Poiché la distanza è relativamente piccola, è possibile utilizzare l'approssimazione della distanza equirettangolare. Questa approssimazione è più veloce rispetto all'utilizzo della formula di Haversine. Quindi, per ottenere la distanza dal punto di riferimento (lat1/lon1) al punto che stai testando (lat2/lon2), usa la formula seguente. Nota importante: è necessario convertire tutti i punti di lat/lon in radianti:

R = 6371 // radius of the earth in km 
x = (lon2 - lon1) * cos(0.5*(lat2+lat1)) 
y = lat2 - lat1 
d = R * sqrt(x*x + y*y) 

Poiche 'R' è in km, la distanza 'd' sarà in km.

Riferimento: http://www.movable-type.co.uk/scripts/latlong.html

Answer 5

Si prega di utilizzare il seguente codice.

def distance(lat1, lng1, lat2, lng2): 
    #return distance as meter if you want km distance, remove "* 1000" 
    radius = 6371 * 1000 

    dLat = (lat2-lat1) * math.pi/180 
    dLng = (lng2-lng1) * math.pi/180 

    lat1 = lat1 * math.pi/180 
    lat2 = lat2 * math.pi/180 

    val = sin(dLat/2) * sin(dLat/2) + sin(dLng/2) * sin(dLng/2) * cos(lat1) * cos(lat2)  
    ang = 2 * atan2(sqrt(val), sqrt(1-val)) 
    return radius * ang