Jak mogę szybko oszacować odległość między dwoma (szerokość, długość) punktami?

Question

Chcę być w stanie uzyskać szacunkową odległość między dwoma punktami (szerokość, długość geograficzna). Chcę się cofnąć, ponieważ będzie to dotyczyć przeszukiwania wykresów A * i chcę, aby był to szybki. Punkty będą co najwyżej 800 km od siebie.

Answer 1

Odpowiedzi na Haversine Formula in Python (Bearing and Distance between two GPS points) dostarczają implementacje Python, które odpowiedzą na twoje pytanie.

Korzystanie z wdrożenia poniżej I wykonał 100 000 iteracji w mniej niż 1 sekundę na starszym laptopie. Myślę, że dla waszych celów powinno to wystarczyć. Jednak powinieneś profilować wszystko, zanim zoptymalizujesz pod kątem wydajności.

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

Aby nie docenić haversine(lat1, long1, lat2, long2) * 0.90 lub innego czynnika, jaki chcesz. Nie rozumiem, w jaki sposób przydatne może być wprowadzenie błędu w niedoszacowaniu.

Answer 2

Jednym z pomysłów na szybkość jest przekształcenie współrzędnych długości/szerokości na współrzędne 3D (x, y, z). Po wstępnym przetworzeniu punktów użyj odległości euklidesowej między punktami, jako szybko obliczonej wartości niecałkowitej rzeczywistej odległości.

Answer 3

Aby uzyskać maksymalną prędkość, można utworzyć coś w rodzaju współrzędnych odległościowych od rainbow table. Wygląda na to, że znasz już obszar, nad którym pracujesz, więc wydaje się, że wykonanie ich może być możliwe. Następnie możesz załadować najbliższą kombinację i po prostu z niej skorzystać.

Na przykład w kontynentalnej części Stanów Zjednoczonych długość geograficzna wynosi 55 stopni, a szerokość geograficzna 20, czyli 1100 punktów. Odległość pomiędzy wszystkimi możliwymi kombinacjami wynosi handshake problem, na którą odpowiada kombinacja (n-1) (n)/2 lub około 600k. To wydaje się całkiem możliwe do zapisania i odzyskania. Jeśli podasz więcej informacji o swoich wymaganiach, mogę być bardziej konkretny.

Answer 4

Ponieważ odległość jest stosunkowo niewielka, można użyć przybliżenia odległości w kształcie prostokąta. To przybliżenie jest szybsze niż użycie formuły Haversine'a. Aby uzyskać odległość od punktu odniesienia (lat1/lon1) do punktu, który testujesz (lat2/lon2), użyj poniższej formuły. Ważna uwaga: trzeba konwertować wszystkie lat/lon punktów na radiany:

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) 

Ponieważ „R” jest w km, odległość „d” będzie w km.

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

Answer 5

Proszę kliknąć na poniższy kod.

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