Более быстрый способ расчета географического расстояния между двумя точками

Я позаимствовал следующий метод где-то в Интернете (не помню где). Но он делает прямой процесс, находя расстояние между двумя точками GPS. Он работает просто отлично, за исключением того, что он может быть немного медленным, так как я пробегаю его по миллионам точек. Мне было интересно, если кто-нибудь знает подход, который будет в вычислительном отношении дешевле.

Точность должна быть в общей области "правильно", но не должна быть точной на 100%.

private double distFrom(double lat1, double lng1, double lat2, double lng2) {
    double earthRadius = 3958.75;
    double dLat = Math.toRadians(lat2-lat1);
    double dLng = Math.toRadians(lng2-lng1);
    double a = Math.sin(dLat/2) * Math.sin(dLat/2) +
           Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2)) *
           Math.sin(dLng/2) * Math.sin(dLng/2);
    double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
    return   earthRadius * c;
  }
}

PS Я действительно нашел ряд других актуальных вопросов, но они на самом деле не фокусируются на моей скорости.

Источник

4 ответа

Решение

Если вы не возражаете, игнорируя небольшое сжатие Земли (и ваш опубликованный код Хаверсайна так или иначе делает именно это), рассмотрите возможность предварительного преобразования всех ваших сферических (широтных / длинных) координат в трехмерные декартовые координаты единичной длины, согласно:

http://en.wikipedia.org/wiki/Spherical_coordinate_system

Тогда ваше сферическое расстояние между декартовыми координатами p1 а также p2 это просто:

r * acos(p1 . p2)

поскольку p1 а также p2 будет иметь единицу длины, это уменьшает до четырех умножений, двух сложений и одной обратной операции триггера на пару.

Также обратите внимание, что вычисление точечных произведений является идеальным кандидатом для оптимизации, например, с помощью графического процессора, расширений MMX, векторных библиотек и т. Д.

Кроме того, если вы хотите упорядочить пары по расстоянию, потенциально игнорируя более удаленные пары, вы можете отложить дорогостоящее r*acos() часть уравнения путем сортировки списка только по значению точечного произведения, поскольку для всех допустимых входных данных (т. е. диапазона [-1, 1]) гарантируется, что:

acos(x) < acos(y) if x > y

Вы тогда просто возьмите acos() ценностей, которые вы на самом деле заинтересованы.

Re: потенциальные неточности с использованием acos()это действительно важно, если вы используете одинарную точность float переменные. Используя double с 16 значащими цифрами вы получите точное расстояние с точностью до одного метра или менее.

Источник

Вы можете попробовать закон косинусов для сферической тригонометрии:

a = sin(lat1) * sin(lat2)
b = cos(lat1) * cos(lat2) * cos(lon2 - lon1)
c = arccos(a + b)
d = R * c

Но это будет неточно для коротких расстояний (и, вероятно, просто немного быстрее).

Здесь есть полное обсуждение. Тем не менее, формула haversine является наиболее правильным способом, так что помимо того, что другие предложили, вы не можете многое сделать. @ Ответ Альнитака может сработать, но преобразование сферических в декартовых не обязательно быстрое.

Источник

Это алгоритм haversine, предоставит вам достойный уровень точности.

Если это действительно "миллионы" точек, возможно, реализуйте кэш вычислений, которые вы сделали... если вы встретите пару координат, которые достаточно близки к паре, расстояние которой вы уже рассчитали, тогда использовать кэшированное значение?

Или попробуйте кэшировать некоторые промежуточные этапы, например, преобразование градусов в радианы.

Источник

Если вы жертвуете точностью, вы можете внести некоторые улучшения. Насколько я помню, sin(x) примерно равно x для маленьких x, Также похоже, что вы вычисляете одни и те же вещи несколько раз, например: Math.sin(dLat/2) (который может быть приближен к dLat/2 как указано выше).

Однако, если вы делаете миллионы этих операций, я бы где-нибудь еще.

  • Ваш алгоритм оптимален? Может быть, вы делаете слишком много простых вычислений?

  • Если точки поступают из базы данных, можете ли вы выполнить вычисления как хранимые процедуры на стороне сервера базы данных?

  • Если вы ищете ближайшие точки, можете ли вы как-то их проиндексировать?

  • Могут ли вам помочь геопространственные индексы?

Источник
Другие вопросы по тегам