Correctamente matematicamente um estimador de heurística / distância para um gráfico de latitude / longitude

5

Eu tenho um gráfico em que cada nó é um ponto geográfico na superfície da Terra, definido por suas coordenadas de latitude / longitude.

As maneiras corretas de calcular a distância entre dois desses pontos podem ser a Fórmula de Haversine para modelos de terra esférica ou o problema inverso de Vincenty para modelos de terra esferoidal.

Mas estes são muito caros em termos de recursos computacionais, e em A * basicamente você não precisa dos valores absolutos desses resultados, você só precisa deles para fins de comparação.

No meu algoritmo A *, a função heurística é a distância mais curta entre 2 pontos (definida como o comprimento do maior círculo menor entre os 2 pontos em um modelo esférico) e o caminho real entre dois nós é uma cadeia de linhas. cujo comprimento é calculado basicamente da mesma forma, apenas que você soma distâncias entre vértices consecutivos.

Portanto, se d(A, B) é a distância geográfica real entre A e B (como pontos de latitude / longitude), o problema é basicamente encontrar o estimador de distância mais eficiente computacional d*(A, B) que satisfaça as condições necessárias para que A * funcione corretamente, como:

  • se d(A, B) < d(C, D) , em seguida, d*(A, B) < d*(C, D) .
  • se d(A, B) + d(E, F) < d(C, D) , em seguida, d*(A, B) + d*(E, F) < d*(C, D)

Eu até vi em alguns lugares que as pessoas recomendam a distância euclidiana para tal caso, mesmo que latitude / longitude sejam ângulos. Pode ser o caso, mas estou interessado se é "matematicamente correto" supor que satisfaz as condições acima.

    
por Tiborg 22.01.2015 / 14:27
fonte

1 resposta

5

Se a área onde os nós podem estar for pequena (relativamente, o tamanho de metade dos EUA é pequeno o suficiente) e longe dos pólos, você pode razoavelmente abordar o problema usando apenas a longitude e a latitude como coordenadas X / Y. Perto dos pólos você pode tratá-los como coordenadas polares com a latitude de 90 ° como a distância do centro e a longitude como o ângulo do eixo x.

Se você estiver trabalhando em todo o mundo, você pode transformar a lat / lon em um ponto em uma esfera de unidade 3D e, em seguida, tomar a distância euclidiana entre eles. O comprimento do acorde entre os dois pontos. (2 sin e cos para cada coordenada (pré-calculada), mais uma raiz quadrada). Isto é, no entanto, mal condicionado quando os pontos estão próximos. Outra opção, em vez da distância euclid, é obter o produto de ponto entre eles e encontrar o aco dele. Isso resultará no ângulo entre os pontos.

    
por 22.01.2015 / 15:13
fonte