Por que a lei dos cossenos é mais preferível que a haversine ao calcular a distância entre dois pontos de latitude-longitude?

41

De fato, quando Sinnott publicou a fórmula haversine, a precisão computacional era limitada. Atualmente, o JavaScript (e a maioria dos computadores e linguagens modernos) usa números de ponto flutuante IEEE 754 de 64 bits, que fornecem 15 números significativos de precisão. Com esta precisão, a fórmula simples da lei esférica de cossenos ( cos c = cos a cos b + sin a sin b cos C) fornece resultados bem condicionados até distâncias tão pequenas quanto cerca de 1 metro. Em vista disso, provavelmente vale a pena, na maioria das situações, usar a lei mais simples dos cossenos ou a fórmula elipsóide mais precisa da Vincenty, em vez da navalha! (tendo em mente as notas abaixo sobre as limitações de precisão do modelo esférico).
Fonte: http://www.movable-type.co.uk/scripts/latlong.html

Qual é a razão pela qual a lei dos cossenos é mais preferível?

Nota: O texto citado foi atualizado por seu autor, conforme mencionado abaixo .

Afriza N. Arief
fonte
10
Como é preferível a lei dos cossenos? Podemos responder a isso de duas maneiras: para o computador e o programador. Para o computador, a fórmula haversine usa menos funções trigonométricas, mas requer duas raízes quadradas. Para eficiência computacional, então, é um lance. Para o programador, a fórmula haversine é um pouco mais longa. No entanto, a fórmula da lei dos cossenos exige uma implementação de ACos, que é vista com menos frequência do que uma implementação de ATan. Além disso, para escrever um código à prova de balas, é necessário verificar se o ACos não falhará. Por esse motivo , devemos preferir a barba por fazer.
whuber
2
Acabei de implementar haversine e cosseno em Python. Nesta haversine computador leva 3.3μs e cosseno leva 2.2μs que é bastante significativo se você precisa fazer um monte deles
gnibbler
11
Obrigado a todos por algumas boas observações e informações. Atualizei o texto citado na pergunta para, espero, ser mais objetivo e útil.
ChrisV
@ ChrisV, obrigado pela atualização! Mudei isso para um comentário, pois não é diretamente uma resposta à pergunta, obrigado pelo ótimo site.
scw

Respostas:

48

O problema é indicado pela palavra "bem condicionado". É uma questão de aritmética computacional, não matemática.

Aqui estão os fatos básicos a serem considerados:

  1. Um radiano na Terra mede quase 10 ^ 7 metros.

  2. A função cosseno para argumentos x próximos a 0 é aproximadamente igual a 1 - x ^ 2/2.

  3. O ponto flutuante de precisão dupla possui cerca de 15 dígitos decimais de precisão.

Os pontos (2) e (3) implicam que, quando x está em torno de um metro ou 10 ^ -7 radianos (ponto 1), quase toda a precisão é perdida: 1 - (10 ^ -7) ^ 2 = 1 - 10 ^ - 14 é um cálculo no qual os 14 primeiros dos 15 dígitos significativos são cancelados, deixando apenas um dígito para representar o resultado. Girar isso (que é o que o cosseno inverso, "acos", faz) significa que calcular acos para ângulos que correspondem a distâncias de comprimento de metro não pode ser feito com precisão significativa. (Em certos casos ruins, a perda de precisão fornece um valor em que nem o acos é definido, portanto o código será quebrado e não dará resposta, uma resposta sem sentido ou travará a máquina.) Considerações semelhantes sugerem que você deve evitar o uso do cosseno inverso se estiverem envolvidas distâncias inferiores a algumas centenas de metros, dependendo da precisão que você deseja perder.

O papel desempenhado pelos acos na fórmula ingênua da lei dos cossenos é converter um ângulo em uma distância. Esse papel é desempenhado por atan2 na fórmula do haversine. A tangente de um pequeno ângulo x é aproximadamente igual a x . Consequentemente, a tangente inversa de um número, sendo aproximadamente esse número, é calculada essencialmente sem perda de precisão. É por isso que a fórmula haversine, embora matematicamente equivalente à lei da lei dos cossenos, é muito superior para pequenas distâncias (da ordem de 1 metro ou menos).

Aqui está uma comparação das duas fórmulas usando 100 pares de pontos aleatórios no globo (usando os cálculos de precisão dupla do Mathematica).

texto alternativo

Você pode ver que, para distâncias inferiores a 0,5 metros, as duas fórmulas divergem. Acima de 0,5 metros, eles tendem a concordar. Para mostrar o quanto eles concordam, o próximo gráfico mostra as proporções da lei dos cossenos: resultados de barreiras para outros 100 pares de pontos aleatórios, com latitudes e longitudes diferentes aleatoriamente em até 5 metros.

texto alternativo

Isso mostra que a fórmula da lei dos cossenos é boa com 3 a 4 casas decimais quando a distância excede 5 a 10 metros. O número de casas decimais de precisão aumenta quadraticamente; assim, a 50-100 metros (uma ordem de magnitude), você obtém uma precisão de 5-6 dp (duas ordens de magnitude); a 500-1000 metros, você obtém 7-8 dp, etc.

whuber
fonte
Existe algum teste barato - por exemplo, delta latitude > .1 || delta longitude > .1para escolher dinamicamente o cosseno (para grandes) ou o haversine (para pequenas distâncias)? Para obter o melhor desempenho e boa precisão.
Anony-Mousse
@ Anony-Mousse Ambas as fórmulas podem ser desativadas em alguns décimos de um por cento para distâncias de um quarto ao redor do mundo, então, a essa altura, não estaremos preocupados com a precisão! Portanto, qualquer teste que possa distinguir pontos próximos (algumas centenas de metros) de pontos quase diametralmente opostos (cerca de 20 milhões de metros) de tudo o que estiver no meio deve ser suficiente.
whuber
Será que atan2oferecem benefícios numéricos mais asin? Vi benchmarks, que atan2eram 2-3 vezes mais lentos do que asine precisamos de um segundo sqrttambém.
21817 Erich Schubert
@Erich Não estudei a diferença, mas observe que asiné essencialmente a mesma coisa acose, portanto, sofre a mesma perda de precisão para determinados valores - nesse caso, para argumentos próximos a 1 e -1. Em princípio, atan2não tem esse problema.
whuber
Isso seria a grandes distâncias? Combinar isso com a sugestão de @ Anony-Mousse acima parece ser interessante então.
21717 Erich Schubert
6

Uma nota de rodapé histórica:

O haversine era uma maneira de evitar grandes erros de arredondamento em cálculos como

1 - cos(x)

quando x é pequeno. Em termos de barulhento, temos

1 - cos(x) = 2*sin(x/2)^2
           = 2*haversin(x)

e 2 * sin (x / 2) ^ 2 podem ser calculados com precisão mesmo quando x é pequeno.

Antigamente, a fórmula haversine tinha uma vantagem adicional de evitar uma adição (o que implicava uma pesquisa antilog, a adição e uma pesquisa de log). Dizia-se que uma fórmula trigonomética que envolvia apenas multiplicações estava em "forma logarítmica".

Atualmente, o uso das fórmulas haversine é levemente anacrônico. Pode ser que o ângulo x seja expresso em termos sin(x)e cos(x)(e x pode não ser explicitamente conhecido). Nesse caso, a computação 1 - cos(x)pela fórmula haversine implica um arco tangente (para obter o ângulo x), metade (para obter x/2), um seno (para obter sin(x/2)), um quadrado (para obter sin(x/2)^2) e uma duplicação final. Você está muito melhor usando a avaliação

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

que não implica avaliações de funções trigonométricas. (Obviamente, use o lado direito apenas se cos(x) > 0; caso contrário, não há problema em usá-lo 1 - cos(x)diretamente.)

cffk
fonte
1

A fórmula do cosseno pode ser implementada em uma linha:

  Distance = acos(SIN(lat1)*SIN(lat2)+COS(lat1)*COS(lat2)*COS(lon2-lon1))*6371

A fórmula haversine usa várias linhas:

  dLat = (lat2-lat1)
  dLon = (lon2-lon1)
  a = sin(dLat/2) * sin(dLat/2) + cos(lat1) * cos(lat2) * sin(dLon/2) * sin(dLon/2)
  distance = 6371 * 2 * atan2(sqrt(a), sqrt(1-a))

Matematicamente, existem idênticas, portanto, a única diferença é a praticidade.

Tom W
fonte
Embora o Haversine original não use a atan2fórmula relacionada ao computador , não há nada que impeça a reescrita das 4 linhas acima em uma única fórmula.
Arjan
@ Arjan, True, mas seria ineficiente porque você precisa calcular a duas vezes. É essencial que a fórmula envolva Sqrt (a) e Sqrt (1-a), porque, embora uma delas seja numericamente instável por distâncias muito pequenas ou muito grandes, a outra não será: é isso que faz essa abordagem funcionar.
whuber
É verdade, @whuber, mas ainda assim eu duvido que o número de linhas me faça escolher uma sobre a outra. (E como você já está explicado na sua resposta, não são muito mais importantes razões para favorecer um.)
Arjan
3
@Arjan eu concordo. A primeira prioridade de alguém deve ser a adequação do código para a tarefa de programação. Depois disso, eu colocaria clareza: isto é, legibilidade, manutenção e documentação alfabetizada. Na ausência desse contexto, contar o número de linhas de código não faz sentido.
whuber
11
atan2(sqrt(a), sqrt(1-a))é o mesmo queasin(sqrt(a))
user102008