Otimização de uma função de cálculo de distância

Question

No meu código eu tenho que fazer um monte de cálculo da distância entre pares de valores de latitude / longitude.

os olhares código como este:

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

(lat2rad por exemplo latitude é convertido em radianos).

Eu identifiquei esta função como o gargalo da minha candidatura desempenho. Existe alguma maneira de melhorar isso?

(I não pode usar tabelas de consulta desde as coordenadas estão variando). Eu também olhou para esta questão , onde é sugerido um esquema de pesquisa como uma grade, o que poderia ser uma possibilidade.

Obrigado pelo seu tempo! ; -)

Answer 1

Se o seu objetivo é rank (comparar) distâncias , então aproximações (sin e pesquisas de tabela cos) poderia reduzir drasticamente a sua quantidade de cálculos necessários (implementar rápida rejeitar . )

Seu objetivo é avançar apenas com o cálculo trigonométricas real se a diferença entre as distâncias aproximadas (para ser classificado ou comparação) cai abaixo de um certo limite.

por exemplo. usando tabelas de pesquisa com 1000 amostras (isto é sin e cos amostrados cada 2*pi/1000), a incerteza de pesquisa é, no máximo, 0,006284. Usando incerteza cálculo para o parâmetro para ACos, a incerteza acumulada, também ser a incerteza limite, será, no máximo, 0,018731.

Então, se avaliar Math.Sin(lat2rad) * Math.Sin(lat1rad) + Math.Cos(lat2rad) * Math.Cos(lat1rad) * Math.Cos(lon2rad - lon1rad) usando tabelas sin e pesquisa cos por dois pares de coordenadas-set (distâncias) produz uma determinada classificação (uma distância parece maior do que a outra baseada na aproximação) e módulo de diferença é maior que o limite acima, em seguida, a aproximação é válida. Caso contrário, prossiga com o cálculo trigonométricas real.

Answer 2

O relator CORDIC algoritmo de trabalho para você (no que diz respeito à velocidade / precisão)

Answer 3

Usando a inspiração de @Brann Eu acho que você pode reduzir o cálculo um pouco (de aviso é um longo tempo desde que eu fiz nada disso e ele terá de ser verificado). Algum tipo de pesquisa de valores pré-calculados provavelmente o mais rápido embora

Você tem:

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

mas 2: COS (A-B) = SIN Um SIN B + COS Um COS B

que é reescrito como 3: SIN Um SIN B = COS (A-B) - co-seno A COS B

substituir cometer um pecado B em 1. você tem:

4: ACOS (COS (A-B) - co-seno A B + COS COS Um COS COS B (A-B))

pré-calcular X = COS (A-B) e Y = COS Um COS B e de colocar os valores para 4

para dar:

ACOS (XY + XY)

4 cálculos trigonométricas em vez de 6!

Answer 4

mudar a maneira de armazenar long / lat:

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

Ao criar uma longa / lat, também calcular a (x, y, z) ponto 3D que representa a posição equivalente a uma unidade de esfera centrado na origem.

Agora, para determinar se o ponto B está mais perto de ponto A do que o ponto C, faça o seguinte:

// 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);
}

e para obter a distância entre dois pontos:

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);
}

Você pode remover o termo 'raio', efetivamente normalizar as distâncias.

Answer 5

Mudar para pesquisar tabelas para sen / cos / acos. Será mais rápido, há um monte de c bibliotecas / c ++ ponto fixo que também incluem aqueles.

Aqui está o código de outra pessoa em Memoização . Que pode funcionar se os valores reais utilizados são mais agrupado.

Aqui está uma pergunta SO on ponto fixo .

Answer 6

O que é o gargalo? É o das chamadas de função de seno / co-seno ou a chamada arcsine?

Se seu seno / co-seno chamadas são lentos, você poderia usar o seguinte teorema para evitar tantas chamadas:

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

Mas eu gosto da idéia de mapeamento para que você não tem que recalcular valores que você já computados. Embora tenha cuidado, pois o mapa poderia ficar muito grandes muito rapidamente.

Answer 7

Como exatamente você precisa os valores a ser?

Se você arredondar os valores um pouco, então você pode armazenar o resultado de todas as pesquisas e verificar se eles têm sido usados ??antes de cada cálculo?

Answer 8

Bem, já que lat e longo são garantidos para ser em um determinado intervalo, você pode tentar usar alguma forma de uma tabela de referência para você Math. * Chamadas de método. Digamos, um Dictionary<double,double>

Answer 9

Eu diria que você pode querer re-examinar como você descobriram que a função a ser o gargalo. (IE você traçar o perfil do aplicativo?)

A equação para mim parece muito leve e não deve causar nenhum problema. Concedido, eu não sei o seu pedido e você diz que fazer um monte de estes cálculos.

No entanto, é algo a considerar.

Answer 10

Como alguém referiu, tem certeza que este é o seu gargalo?

Eu fiz alguns testes de um aplicativo semelhante Estou construindo onde eu chamar um método simples para retornar a distância entre dois pontos usando trig padrão de desempenho. 20.000 chamadas para ele empurra-lo no topo da saída profiling, ainda não há nenhuma maneira eu posso fazer isso mais rápido ... É apenas o corte # de chamadas.

Neste caso, eu preciso reduzir o # chamadas para ele ... Não que este é o gargalo.

Answer 11

Eu uso um algoritmo diferente para o cálculo da distância entre 2 lati / Longi posições, poderia ser mais leve do que o seu, uma vez que só faz 1 Cos chamada e 1 chamada 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 12

alguém já mencionou memoisation e isso é um pouco similar. se você comparar o mesmo ponto de muitos outros pontos, então é melhor para as partes precalculate dessa equação.

em vez de

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

tem-se:

double result = Math.Acos(lat2rad.sin * lat1rad.sin 
+ lat2rad.cos * lat1rad.cos * (lon2rad.cos * lon1rad.cos + lon1rad.sin * lon2rad.sin));

e eu acho que é a mesma fórmula que alguém postou porque parte da equação irá desaparecer quando você expandir os suportes:)