Оптимизация функции расчета расстояния

Question

В моем коде мне нужно много вычислить расстояние между парами значений lat / long.

код выглядит так:

double result = Math.Acos(Math.Sin(lat2rad) * Math.Sin(lat1rad) 
+ Math.Cos(lat2rad) * Math.Cos(lat1rad) * Math.Cos(lon2rad - lon1rad));

(например, lat2rad - это широта, переводимая в радианы).

Я определил эту функцию как узкое место в производительности моего приложения. Есть ли способ улучшить это?

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

Спасибо за ваше время! ; -)

Answer 1

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

Ваша цель состоит в том, чтобы приступить к фактическим тригонометрическим вычислениям только в том случае, если разница между приблизительными расстояниями (для ранжирования или сравнения) падает ниже определенного порога.

например. используя таблицы поиска с 1000 выборками (то есть sin и cos выборка каждые 2*pi/1000), неопределенность поиска составляет не более 0,006284. При использовании расчета неопределенности для параметра ACos накопленная неопределенность, также являющаяся пороговой неопределенностью, будет не более 0,018731.

Таким образом, при оценке Math.Sin(lat2rad) * Math.Sin(lat1rad) + Math.Cos(lat2rad) * Math.Cos(lat1rad) * Math.Cos(lon2rad - lon1rad) с использованием таблиц поиска sin и cos для двух пар (координат) с заданными координатами можно получить определенное ранжирование (одно расстояние больше другого на основе аппроксимации), а разность модуль больше, чем порог выше, то приближение является действительным. В противном случае продолжите фактический тригонометрический расчет.

Answer 2

Будет ли работать алгоритм CORDIC для вас (в отношении скорости / точности)?

Answer 3

Используя вдохновение от @Brann, я думаю, вы можете немного сократить вычисления (предупреждаю, что это долгое время, так как я делал все это, и его нужно будет проверить) Какой-то поиск предварительно рассчитанных значений, вероятно, самый быстрый, хотя

У вас есть:

1: ACOS (SIN A SIN B + COS A COS B COS (A-B))

но 2: COS (A-B) = SIN A SIN B + COS A COS B

, который переписывается как 3: SIN A SIN B = COS (A-B) - COS A COS B

заменить SIN A SIN B на 1. у вас есть:

4: ACOS (COS (A-B) - COS A COS B + COS A COS B COS (A-B))

Вы предварительно рассчитываете X = COS (A-B) и Y = COS A COS B, и вы помещаете значения в 4

дать:

ACOS (X - Y + XY)

4 триггерных вычисления вместо 6!

Answer 4

Изменить способ хранения длинных / лат:

struct LongLat
{
  float
    long,
    lat,
    x,y,z;
}

При создании long / lat также рассчитайте трехмерную точку (x, y, z), которая представляет эквивалентную позицию на единичной сфере с центром в начале координат.

Теперь, чтобы определить, находится ли точка B ближе к точке A, чем точка C, сделайте следующее:

// is B nearer to A than C?
bool IsNearer (LongLat A, LongLat B, LongLat C)
{
  return (A.x * B.x + A.y * B.y + A.z * B.z) < (A.x * C.x + A.y * C.y + A.z * C.z);
}

и для получения расстояния между двумя точками:

float Distance (LongLat A, LongLat B)
{
  // radius is the size of sphere your mapping long/lats onto
  return radius * acos (A.x * B.x + A.y * B.y + A.z * B.z);
}

Вы можете удалить термин 'радиус', эффективно нормализуя расстояния.

Answer 5

Что такое горлышко бутылки? Вызов функции синус / косинус или арксинус?

Если ваши синусоидальные / косинусоидальные вызовы медленные, вы можете использовать следующую теорему, чтобы предотвратить так много вызовов:

1 = sin(x)^2 + cos(x)^2
cos(x) = sqrt(1 - sin(x)^2)

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

Answer 6

Переключение на таблицы поиска для sin / cos / acos. Будет быстрее, есть много библиотек c / c ++ с фиксированной запятой, которые также включают их.

Вот код от кого-то еще на Памятка . Что может сработать, если используемые фактические значения будут более кластерными.

Вот ТАК вопрос о Фиксированная точка .

Answer 7

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

вместо </p> <pre> double result = Math.Acos(Math.Sin(lat2rad) * Math.Sin(lat1rad) + Math.Cos(lat2rad) * Math.Cos(lat1rad) * Math.Cos(lon2rad - lon1rad)); </pre> <p>

есть:

</p> <pre> double result = Math.Acos(lat2rad.sin * lat1rad.sin + lat2rad.cos * lat1rad.cos * (lon2rad.cos * lon1rad.cos + lon1rad.sin * lon2rad.sin)); </pre> <p>

и я думаю, что это та же формула, которую опубликовал кто-то другой, потому что часть уравнения исчезнет, ​​когда вы расширите скобки:)

Answer 8

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

public static double GetDistanceBetweenTwoPos(double lat1, double long1, double lat2, double long2)
{
  double distance = 0;
  double x = 0;
  double y = 0;

  x = 69.1 * (lat1 - lat2);
  y = 69.1 * (long1 - long2) * System.Math.Cos(lat2 / 57.3);

  //calculation base : Miles
  distance = System.Math.Sqrt(x * x + y * y);

  //Distance calculated in Kilometres
  return distance * 1.609;
}

Answer 9

Как кто-то еще указал, вы уверены, что это ваше узкое место?

Я провел некоторое тестирование производительности аналогичного приложения, которое я строю, где я вызываю простой метод для возврата расстояния между двумя точками с использованием стандартного триггера. 20 000 обращений к нему подталкивают его прямо к началу вывода профилирования, но я никак не могу сделать это быстрее ... Это просто число вызовов.

В этом случае мне нужно уменьшить количество # обращений к нему ... Не то чтобы это узкое место.

Answer 10

Я бы сказал, что вы, возможно, захотите пересмотреть, как вы обнаружили, что эта функция является узким местом. (IE вы профилировали приложение?)

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

Тем не менее, это то, что нужно учитывать.