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

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

9 голосов
/ 20 июня 2011

Я позаимствовал следующий метод из Интернета (не помню где).Но он делает прямой процесс, находя расстояние между двумя точками 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 ]

17 голосов
/ 20 июня 2011

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

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

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

r * acos(p1 . p2)

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

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

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

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

Затем вы просто берете acos() значений, которые вам действительно интересны.

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

1 голос
/ 20 июня 2011

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

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

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

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

1 голос
/ 20 июня 2011

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

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

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

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

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

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

1 голос
/ 20 июня 2011

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

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

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

...