Cálculo da distância entre um ponto e uma linha virtual de dois lat / lngs

14

Por favor, consulte o exemplo e a imagem correspondente.

Gostaria de conseguir o seguinte: proporcionar dois locais (latitude / longitude), que são mostradas abaixo como uma e B . A partir disso, uma linha virtual seria desenhada e então a distância entre essa linha e C seria calculada (em qualquer medida).

desenhando

Consegui isso atualmente na API do Google Maps v3, mas também desejo realizar isso nos bastidores no meu idioma preferido. Todas as dicas / idéias serão muito apreciadas!

Prisioneiro
fonte
AB é uma linha do Grande Círculo ?
22411 Kirk Kuykendall
@Kirk, Não, AB é apenas uma linha reta
Prisoner
@ Michael, esse é um ponto interessante. Vou ter que dar uma olhada nisso!
Prisoner
@ Prisioneiro @ Kirk Literalmente, uma "linha reta" passará abaixo da superfície da Terra. Em geral, sua projeção radial de volta à superfície será de fato um segmento de um grande círculo (usando um modelo de terra esférico).
whuber
1
@ Prisioneiro Essa é uma informação extra extremamente útil! Sim você está correto. Você ainda precisa compensar o fato de que o uso (lat, lon) distorce diferencialmente as distâncias leste-oeste em comparação ao norte-sul. Como @Jose aconselha, projete as coordenadas. Isso pode ser tão simples quanto pré-multiplicar as longitudes pelo cosseno da latitude média e depois fingir que você está em um plano euclidiano.
whuber

Respostas:

6
def get_perp( X1, Y1, X2, Y2, X3, Y3):
    """************************************************************************************************ 
    Purpose - X1,Y1,X2,Y2 = Two points representing the ends of the line segment
              X3,Y3 = The offset point 
    'Returns - X4,Y4 = Returns the Point on the line perpendicular to the offset or None if no such
                        point exists
    '************************************************************************************************ """
    XX = X2 - X1 
    YY = Y2 - Y1 
    ShortestLength = ((XX * (X3 - X1)) + (YY * (Y3 - Y1))) / ((XX * XX) + (YY * YY)) 
    X4 = X1 + XX * ShortestLength 
    Y4 = Y1 + YY * ShortestLength
    if X4 < X2 and X4 > X1 and Y4 < Y2 and Y4 > Y1:
        return X4,Y4
    return None

O menor comprimento é a distância que você precisa, a menos que eu esteja enganado?

Peludo
fonte
Sim, estou procurando a menor distância entre C e o segmento de linha. É isso que essa matemática calcula?
Prisoner
1
Realmente funcionou bem, passei os três pontos (A, B, C) a seguir: i.imgur.com/bK9oB.jpg e voltei com o lat / lng de X. Ótimo trabalho!
Prisoner
1
@Hairy, Uma última coisa, como eu modificaria isso para ir para o ponto mais próximo (não apenas a linha); se eu tivesse passado do ponto de unir uma linha, como eu poderia fazer isso para verificar a distância até o ponto? ponto?
Prisoner
1
@Hairy Bom começo, mas parece que muitas vezes esse código retorna Nonequando existe uma solução legítima. O problema é que o último condicional assume X1 <X2 e Y1 <Y2, o que nem sempre pode ser garantido. É necessário um melhor teste de intermediação.
whuber
1
@Hairy Parece que essa troca entre você e o @prisoner foi produtiva. Gostaria de enfatizar que não tive nada a ver com (ou mesmo qualquer controle sobre) quaisquer alterações nos votos ou pontos que possam ter ocorrido e que meu comentário foi destinado apenas para ajudá-lo a melhorar sua resposta.
whuber
11

Talvez eu esteja complicando demais, mas o que você quer é a distância de um ponto a uma linha. Essa é a distância de um ponto ao longo de AB que liga AB com C com uma linha ortogonal a AB. Esse vetor perpendicular a AB é dado por

v=[x2-x1, -(y2-y1)] # Point A is [x1,y1] Point B is [x2,y2]

(Eu usei os colchetes para definir um vetor ou uma matriz de dois elementos). A distância entre C [xp, yp] e o ponto A é

u=[x1-xp, y1-xp]

A distância entre a linha e C é apenas a projeção de u para v. Se assumirmos que mod (v) = 1 (apenas normalizá-la), então

distance = u*v = abs( (x2-x1)*(y1-yp) - (x1-xp)*(y2-y1) )

A única complicação é que você provavelmente deseja garantir que suas coordenadas não sejam pares WGS84 lat / log, mas projetadas (ou use coordenadas geodésicas). Você pode usar OGR ou Proj4 para isso.

Jose
fonte
3
+ vários milhões de pseudo-pontos por não usar funções trigonométricas, a propósito. Todas as muitas pessoas retirar ArcTan quando deveriam estar a olhar para isto: en.wikipedia.org/wiki/Dot_product
Herb
@ Jose, obrigado pela resposta! Estou usando a lat / long da API do google maps. A parte da matemática é bastante nova para mim, então vou tentar e ver o que posso fazer. Alguma dica com a matemática? Por exemplo, [x2-x1, - (y2-y1)], o que isso significa?
Prisoner
Eu adicionei uma edição curta para isso. Basicamente, é uma notação de matriz, mas se você armazenar suas coordenadas nas variáveis ​​x1, x2, y1, y2 e xp, yp, você só precisará escrever o lado direito da última equação que forneci. Isso é muito bonito válida C, Java, JS, Python código etc :)
Jose
1
@ Joseph Você está calculando a distância de C à linha AB. Com base na figura, acredito que o OP deseja a distância de C ao segmento de linha AB. Isso requer trabalho extra para verificar se a projeção de C na linha AB está entre A e B ou não. Neste último caso, use o menor dos dois comprimentos CA e CB.
whuber
1
@Prisoner A principal diferença é que uma linha se estende para sempre (é definida apenas por um vetor de direção e um ponto, ou por dois pontos), enquanto um segmento entre A e B é o bit da linha infinita que passa entre A e B (que tem um comprimento finito)
Jose
4

Sendo um pouco avesso a toda essa matemática, eu chegaria a ela de um ângulo diferente. Eu a tornaria uma linha 'real', em vez de virtual, e depois usaria as ferramentas existentes.

Se A e B compartilharem um atributo, você poderá conectá-los desenhando uma linha (o Kosmo GIS possui uma ferramenta que criará linhas a partir de pontos, e acredito que também haja um plug-in QGIS para isso). Depois de ter as linhas, uma função 'near' na camada de pontos 'C' fornecerá a distância para a linha. Deixe o software lidar com a matemática para você!

Darren Cope
fonte
Obrigado pelo comentário, mas Cabeludo veio trunfos sobre este!
Prisoner
1
(+1) Você faz um excelente ponto. Os algoritmos de geometria computacional são notoriamente difíceis de acertar na prática (como podemos ver em todo o código oferecido até agora, o que é útil e ilustrativo, mas ainda não funciona totalmente). O uso de um procedimento GIS de alto nível geralmente é uma boa maneira de garantir que você esteja recebendo a resposta que espera e que esteja certa (desde que confie no seu GIS ;-).
whuber
1

Se você estava usando java no android, é apenas uma linha com a função de biblioteca

import static com.google.maps.android.PolyUtil.distanceToLine;

distanceToLine:

public static double distanceToLine(LatLng p, LatLng start,LatLng end)

Calcula a distância na esfera entre o ponto p e o segmento de linha do início ao fim.

Parâmetros: p - o ponto a ser medido

start - o início do segmento de linha

end - o fim do segmento de linha

Retornos: a distância em metros (assumindo terra esférica)

Basta adicionar biblioteca ao seu

dependencies {
    compile 'com.google.maps.android:android-maps-utils:0.5+'
}
indy
fonte