Localização do projeto em um caminho (grande círculo)

9

Estou pesquisando neste site SE há algumas horas e ainda estou lutando para encontrar uma solução para minha pergunta. Meu objetivo é que, de certa forma, no OSM e na minha localização (coordenadas lat / lon), eu queira encontrar o local mais próximo (coordenadas lat / lon) nesse caminho. O ponto pode estar em qualquer lugar do caminho, não limitado aos pontos usados ​​para definir o caminho.

Então, eu estou pensando no seguinte algoritmo:

  1. Caminho separado em arestas separadas, cada aresta conectando apenas dois pontos.
  2. Selecione a aresta mais próxima.
  3. Projete minha localização nessa extremidade.

Agora, existem muitas perguntas sobre o cálculo da distância entre um local e um caminho:

Também uma pergunta muito semelhante, da qual não consigo acertar ou verificar os cálculos:

Há também algumas informações do Dr. Math sobre esse assunto. No entanto, parece que não consigo encontrar um algoritmo para calcular a localização na etapa 3. Como não toquei na álgebra (vetor) há um bom tempo, não entendo bem a lógica nessas respostas.

Alguém pode mostrar um algoritmo para fazer isso? Uma solução em qualquer linguagem de programação razoável está bem comigo.

Bouke
fonte
11
Como isso parece crítico para a sua "rejeição" das outras perguntas, por favor, elabore "projete minha localização nesse limite". A projeção pode não estar na borda. Acredito que esse problema seja tratado nas outras questões. (Bem feito, para a pesquisa, BTW).
Martin F
O @MartinF que pergunta calcula a distância de um ponto a uma linha, mas não o ponto mais próximo da própria linha.
Bouke
Não é uma solução a gis.stackexchange.com/a/23500/3195 embora é talvez difícil de compreender.
Martin F
Ah sim obrigado, eu atualizei ref no. 3. A 'solução' nessa pergunta específica está vinculada a uma explicação geral do campo do problema. Embora isso possa ser suficiente para matemáticos bem fundamentados, não entendo bem a matemática nesse artigo.
Bouke

Respostas:

7

O uso de um modelo esférico da Terra pode fornecer precisão adequada e levar a cálculos rápidos e simples.

Converta todas as coordenadas em coordenadas cartesianas centradas na terra (3D). Por exemplo, a fórmula

(cos(lon)*cos(lat), sin(lon)*cos(lat), sin(lat))

vai fazer. (Ele usa uma medida de distância na qual o raio da Terra é uma unidade, o que é conveniente.)

Escrevendo X0 = (x0, y0, z0) para o ponto inicial e X1 = (x1, y1, z1) para o ponto de destino, que define o grande círculo (desde que X0 seja distinto de X1 e os dois não sejam diametralmente opostos), seja U o produto cruzado normalizado de X0 e X1. Isso é calculado em duas etapas:

V = (xv, yv, zv) = (y0*z1 - z0*y1, z0*x1 - x0*z1, x0*y1 - y0*x1)

O comprimento de V é

|V| = sqrt(xv^2 + yv^2 + zv^2)

A normalização estende V ao comprimento da unidade:

U = (xu, yu, zu) = V / |V| = (xv/|V|, yv/|V|, zv/|V|).

A distância 3D orientada entre qualquer ponto X = (x, y, z) e o plano desse grande círculo é apenas o produto escalar de X com Z, dado por

d = X * U = x*xu + y*yu + z*zu

O ponto mais próximo em termos da distância na superfície da Terra é o que está mais próximo do plano: assim, ele tem o menor valor absoluto de d .

Figura

Esta figura mostra um grande círculo (em preto) determinado pelos dois pontos brancos e 2000 pontos aleatórios na esfera colorida e sombreada de acordo com sua distância 3D absoluta ao plano desse grande círculo; isto é, | d |.

Tendo encontrado um ponto mais próximo, projete-o no grande círculo, primeiro projetando-o no plano do grande círculo (em 3D) e depois estendendo-o radialmente para a superfície da Terra. A projeção apenas subtrai d * U:

X' = (x', y', z') = X - d*U = (x - d*xu, y - d*yu, z - d*zu).

A projeção radial simplesmente renormaliza X 'da mesma maneira que V foi renormalizado para U:

X'' = X' / |X'|.

(Isso será problemático se | X '| = 0, que acontece quando o ponto mais próximo é um dos pólos do grande círculo. Inclua um teste no código para essa condição, se possível, e lide com ele separadamente, usando o sinal de d para identificar qual pólo.)

Se desejar, converta as coordenadas de X '' de volta para (lat, lon) usando as fórmulas usuais .

whuber
fonte
Uma questão. Considere o caso não muito incomum em que podemos escolher qualquer X1 e X0 (no grande círculo), do ponto de vista da precisão, é melhor escolher X1 e X0 próximos ou distantes (novamente, desde que X0 seja diferente de X1 e os dois não são diametralmente opostos)?
user189035
11
@ user189035 Escolha um ângulo de 90 graus. Quando estão muito próximos, seu produto cruzado é numericamente incerto: há muito cancelamento nas subtrações, levando à perda de números significativos.
whuber