Как я могу быстро оценить расстояние между двумя (широта, долгота) точек?

Я хочу, чтобы получить оценку расстояния между двумя (широта, долгота) точек. Я хочу отказаться от работы, так как это будет для поиска по графику A *, и я хочу, чтобы он был быстрым. Точки будут находиться на расстоянии не более 800 км.

Ответ 1

Ответы на Формула Хаверсина в Python (Подшипник и Расстояние между двумя точками GPS) предоставляют реализации Python, которые отвечают на ваш вопрос.

Используя нижеприведенную реализацию, я выполнил 100 000 итераций менее чем за 1 секунду на более старом ноутбуке. Я думаю, для ваших целей этого должно быть достаточно. Однако перед тем, как оптимизировать производительность, вы должны прокомментировать все.

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

Недооценить haversine(lat1, long1, lat2, long2) * 0.90 или любой необходимый вам фактор. Я не вижу, насколько полезно вводить ошибку в вашу недооценку.

Ответ 2

Так как расстояние относительно невелико, вы можете использовать приближение равноугольного расстояния. Это приближение быстрее, чем использование формулы Хаверсина. Итак, чтобы получить расстояние от вашей контрольной точки (lat1/lon1) до точки, которую вы тестируете (lat2/lon2), используйте приведенную ниже формулу. Важное примечание: вам нужно преобразовать все точки lat/lon в радианы:

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 )

Так как "R" находится в км, расстояние "d" будет в км.

Ссылка: http://www.movable-type.co.uk/scripts/latlong.html

Ответ 3

Одной из идей скорости является преобразование длинного/лат-координата в координаты 3D (x, y, z). После предварительной обработки точек используйте евклидово расстояние между точками как быстро вычисленное недожатие фактического расстояния.

Ответ 4

Для максимальной скорости вы можете создать что-то вроде таблицы радуги для координатных расстояний. Похоже, вы уже знаете область, с которой работаете, поэтому кажется, что предварительное вычисление их возможно. Затем вы можете загрузить ближайшую комбинацию и просто использовать ее.

Например, в континентальной части Соединенных Штатов долгота составляет 55 градусов, а широта - 20, что составляет 1100 целых чисел. Расстояние между всеми возможными комбинациями - это проблема рукопожатия, на которую отвечают (n-1) (n)/2 или около 600k комбинаций. Это кажется вполне возможным для хранения и извлечения. Если вы предоставите более подробную информацию о своих требованиях, я могу быть более конкретным.

Ответ 5

Если расстояние между точками относительно невелико (расстояние от нескольких метров до нескольких километров) тогда один из быстрых подходов может быть

from math import cos, sqrt
def qick_distance(Lat1, Long1, Lat2, Long2):
    x = Lat2 - Lat1
    y = (Long2 - Long1) * cos((Lat2 + Lat1)*0.00872664626)  
    return 111.319 * sqrt(x*x + y*y)

Lat, Long в радианах, расстояние в км.

Отклонение от расстояния Хаверсайна составляет порядка 1%, а прирост скорости - более чем в 10 раз.

0,00872664626 = 0,5 * пи /180,

111.319 - это расстояние, которое соответствует 1 градусу на экваторе, вы можете заменить его медианным значением, как здесь https://www.cartographyunchained.com/cgsta1/ или замените его простой таблицей поиска.

Ответ 6

Пожалуйста, используйте следующий код.

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

Ответ 7

Для вычисления расстояния между двумя точками вы можете просто использовать библиотеку mpu.haversine_distance(), например:

>>> import mpu
>>> munich = (48.1372, 11.5756)
>>> berlin = (52.5186, 13.4083)
>>> round(mpu.haversine_distance(munich, berlin), 1)
>>> 504.2