Que tipos de segmentos / arestas de linha requerem alta precisão em uma verdadeira representação da superfície do elipsóide?

8

Estive pensando (e fazendo codificação de protótipo) em uma base de código geográfica 'sem projeção' com suas primitivas básicas de ponto, linha e polígono.

Em vez de lidar com todos os sacrifícios que acompanham a projeção no avião, no entanto, estou escrevendo algoritmos que funcionam diretamente na superfície do elipsóide.

Uma das possíveis complicações é que existem diferentes tipos de "linhas" por aí:

  • (arcos de) grandes círculos: menor distância ao longo da superfície (elevação constante de zero) entre dois pontos; deve corresponder exatamente aos caminhos da linha de visão.
  • linhas de rumo: conecte os dois pontos com um caminho de direção constante - por exemplo, algumas bordas de estados seguem linhas de latitude (que não são grandes círculos).
  • curvas: arcos circulares (trajetos de distância constante de um dado ponto central); Bezier (não tenho certeza da reinterpretação correta no contexto de uma superfície curva), etc.

Dos diferentes tipos de caminhos (incluindo os que eu perdi), que são importantes o suficiente para que eles tenham uma representação 'exata', vs representando dentro de um limite de erro por segmentos curtos de um caminho mais simples (por exemplo, segmentos curtos de arco geodésico)?

Edições de esclarecimento: por 'exato' acima, quero dizer paramétrico. Em outras palavras: computável com a precisão desejada, sem uma etapa de densificação na importação.

Uma edição , muito mais tarde, para adicionar uma citação que me deparei, aproxima muito meus pensamentos sobre o uso de vetores de unidades 3D como uma primitiva geográfica: Uma Representação de Posição Horizontal Não-singular ( link alt ). Melhor parte? Eu não tive que escrever tudo sozinho!

Dan S.
fonte
Representações realmente exatas de qualquer um desses objetos em qualquer elipsóide (que não é uma esfera) são quase impossíveis. A geodésica não é mais parte de grandes círculos em geral; as linhas de rumba serão desagradáveis, não importa o quê; arcos circulares geodésicos serão particularmente confusos. Existe realmente algum ponto em fazer isso que valha algumas ordens de magnitude de computação adicional para cada operação?
whuber
Nada é exato com essa interpretação da palavra - que tal "paramétrico" como uma melhor escolha de palavra? (Além disso, como uma observação lateral: se eu me restringir a esferóides em vez de elipsóides gerais, as representações paramétricas são um pouco menos confusas.) No entanto, é verdade que muitas dessas coisas permanecem extremamente confusas / difíceis - daí a minha pergunta! Não estou interessado em um sistema que destrua a qualidade dos dados existentes, mas não sinto necessidade de representar curvas que ninguém está usando.
Dan S.
Trabalhei com grandes segmentos de linhas circulares em um esferóide representado como um polo de rotação (ponto em lat / long) com um ângulo inicial e final. Achei difícil visualizar a matemática usada para manipulá-los (quaternions). sciencedirect.com/...
Kirk Kuykendall
@Kirk: Uma representação mais fácil de trabalhar (opinião aqui!) É usar coordenadas ortográficas em 3D e representar os pontos de início / fim como vetores - você ainda está usando quaternions (para representar rotações em 3D), mas eles ' re muito mais fácil de pensar.
Dan S.
@ Dan - mas com as cordas 3d, você precisaria densificar para manter a elevação constante, não precisaria?
Kirk Kuykendall

Respostas:

6

A questão diz respeito a que tipos de curvas merecem uma representação implicitamente exata, em vez de uma aproximação discretizada. O cerne da questão é esta: para ter sucesso, a classe de curvas que você suporta dessa maneira deve ser fechada na classe de operações de criação de curvas e polígonos suportadas no GIS.

Essas operações incluem:

  • Carregando. Nesse processo, você precisa construir curvas paralelas aos recursos. ("Paralelo" significa no sentido de manter uma distância fixa.) Isso inclui círculos e partes dos mesmos (para pontos de amortecimento), paralelos oblíquos (que são curvas equidistantes à geodésica no esferóide e podem reduzir para pontos isolados em casos especiais) e círculos concêntricos. Na esfera (mas não geralmente no elipsóide), os paralelos oblíquos são eles mesmos círculos.

  • Polígonos de influência (polígonos de Thiessen; polígonos de Voronoi; células de Dirichlet). Para construir os polígonos de Thiessen para uma coleção de recursos de pontos, precisamos encontrar linhas de bissecção, que são geodésicas (são retas); mas para uma coleção de outros tipos de recursos, como pontos e segmentos, os limites dos polígonos de Thiessen incluem partes de parábolas (no plano). Talvez você não queira apoiar isso ...

  • Sobreposições teóricas de conjuntos (interseção, união, diferença, complemento). Essas operações não criam novos tipos de curvas.

  • Tradução e rotação paralelas . Geralmente não é possível executar exatamente em um elipsóide (porque não é um espaço homogêneo ), mas é simples na esfera. Na esfera, essas operações não criam novos tipos de curvas.

A classe realmente problemática de curvas que você propõe consiste nas linhas gerais de rumbos (loxodromos). Linhas de latitude são linhas de rumo, mas (pelo menos na esfera) também são círculos, portanto não apresentam problemas adicionais. Mas as linhas gerais de rumbos são bestas complicadas: se não são meridianos ou paralelos, elas espiralam em um pólo ou no outro. Buffers e traduções paralelas de linhas de rumbos serão genuinamente novos tipos de curvas. Você teria que representar esses resultados como segmentos quebrados de linhas e círculos, o que anularia seu objetivo (e seria bastante difícil de calcular). Portanto, sugiro não tentar suportar exatamente as linhas de rumba.

Em suma, parece que você pode ter sucesso em seu programa se (a) você trabalhar em um modelo esférico da Terra em vez do modelo elipsoidal ("esferoidal") mais geral e (b) você limitar certas construções, como polígonos de Thiessen (e eixos mediais, que estão intimamente relacionados) a coleções de pontos.

whuber
fonte
Eu realmente gosto dessa maneira de pensar sobre isso. Alguns pensamentos aleatórios em observações seguintes ...
Dan S.
Nit: O buffer é de distância fixa, não paralelo (exceto para linhas infinitas).
Dan S.
No avião, áreas de influência para feições retas têm curvas retas e cônicas em suas bordas - mas duvido que esteja fechada. Na verdade, não tenho idéia de quais curvas formam o limite de influência para os recursos curvos (seção cônica); talvez alguma reflexão / pesquisa profunda revele que também são seções cônicas, mas sou cético. Ser fechado em geral sob essas operações parece muito improvável.
Dan S.
Operações teóricas de conjuntos: os sistemas GIS planares normalmente não são fechados sob complemento de conjuntos, pois cria um polígono de tamanho infinito; sphere / sphereoid / elipsóide pode fazer melhor. Observe que, às vezes, os pontos de interseção não podem (ou são difíceis) representar para muitas tipologias de curva, mesmo no plano.
Dan S.
Tradução / rotação: Transformações afins são possíveis no plano, embora existam outras transformações não afins possíveis que possam realmente fazer mais sentido, tornando-as especificamente não afins. Por exemplo: "mover todos os pontos em direção ao norte em 150 metros" é geralmente o que se entende por uma tradução simples em muitas projeções, mas é claro que as distorções da projeção significam que a intenção está um pouco minada ...
Dan S.
4

Dan,

Você pode estar interessado em alguns dos trabalhos que tenho feito em geodésica. Isso é descrito nesta pré - impressão . Em particular, observe:

  • Os problemas geodésicos diretos e inversos podem ser resolvidos com precisão de máquina. Isso significa cerca de 15 nm para precisão dupla. Posso mudar para duplas longas, adicionar um termo extra na série e obter precisão às 18h. Observe, em particular, que a solução para o problema inverso sempre converge (ao contrário do método de Vincenty). A velocidade é comparável ao método de Vincenty (a solução direta é um pouco mais rápida, a solução inversa é um pouco mais lenta).

  • Calculo o comprimento reduzido e as escalas geodésicas. Essas quantidades fornecem as propriedades diferenciais da geodésica e permitem que vários problemas geodésicos (interseções, linhas medianas etc.) sejam resolvidos com rapidez e precisão usando o método de Newton. A curvatura dos limites das regiões tampão pode ser expressa em termos dessas quantidades. Veja esta nota que enviei para a lista de discussão do proj.4.

  • Defino uma projeção gnomônica elipsoidal na qual a geodésica é quase reta. Isso permite que os problemas na superfície do elipsóide sejam mapeados para problemas na geometria plana. Por exemplo, a interseção de duas geodésicas pode ser encontrada exatamente estimando um ponto de interseção, realizando uma projeção gnomônica sobre esse ponto, re-estimando a interseção e iterando.

  • Eu dou expressões para a área de um polígono geodésico. Não é necessário subdividir arestas longas para obter um resultado preciso.

  • GeographicLib (no sourceforge) implementa os algoritmos.

  • Finalmente, observo que, para muitos propósitos, a geodésica é preferível a qualquer outro tipo de curva (em particular grandes elipses ou linhas de rumba), porque obedecem à desigualdade do triângulo. Isso tem várias consequências:

    • Geodésicos e círculos geodésicos se cruzam em ângulos retos.
    • A menor linha XXX entre um ponto P e uma curva arbitrária C cruza C perpendicularmente apenas se XXX = geodésico.
    • A geodésica é uma maneira natural de particionar dados usando uma quadtree, porque limites podem ser colocados no intervalo de distâncias entre um ponto arbitrário e todos os pontos em um quadnode.
cffk
fonte
Obrigado por compartilhar essas idéias; É um papel muito bom, contendo um ótimo trabalho. Bem vindo ao nosso site! Algumas observações e perguntas a seguir. (1) Em que sentido "geodésicos e círculos geodésicos se cruzam em ângulos retos"? Você deve ter alguma restrição em mente, porque isso geralmente não é verdade. (2) As distâncias euclidianas em 3D a que @Dan se refere também satisfarão a desigualdade do triângulo.
whuber
(1) Considere todas as geodésicas que emanam de um ponto A; isso define uma família de curvas. Considere a seguir todos os círculos geodésicos centralizados em A; isso define uma segunda família de curvas. Por causa da desigualdade do triângulo, essas duas famílias são ortogonais. Isso fornece uma das propriedades básicas da projeção equidistante azimutal. (2) Sim, você está certo, é claro. Se você está metido no mundo da geometria das superfícies, recua diante da ideia de quaisquer propriedades que dependem de como a superfície é incorporada no espaço 3D. (Veja Gauss "Teorema Notável".)
cffk
Na verdade (1) é mais geral: em qualquer variedade Riemanniana, uma geodésica de um ponto P fora de uma curva suave c até um ponto em c que minimiza a distância entre P e c deve ser ortogonal a c . Sua declaração sobre "círculos geodésicos" segue imediatamente (desde que P seja o centro: essa é a restrição anteriormente não declarada). Concordo com o sentimento expresso após (2), mas devemos lembrar que o objetivo aqui é realizar cálculos precisos e eficientes, em vez de investigar propriedades intrínsecas da superfície. Uma incorporação bem escolhida pode facilitar isso.
whuber
Um agradecimento tardio por esta resposta. :) Estou muito debaixo d'água para fazer mais do que nadar no momento, mas parece ser um tesouro fantástico. Uma observação rápida sobre as interseções geodésicas desde que você as chamou - principalmente para você revisar como uma verificação de minha própria intuição insuficiente: Interseções exatas da geodésica esférica podem ser facilmente encontradas pela interseção dos planos dos grandes círculos correspondentes, e esse resultado leva para elipsóides usando uma esfera auxiliar - ou estou perdendo alguma coisa lá?
Dan S.
@ Dan Compus uma resposta para sua pergunta. Mas parece que os comentários têm limites de comprimento. Então veja a próxima resposta.
Cffk
2

Esta é a resposta à pergunta de @ Dan sobre o uso da esfera auxiliar para resolver problemas de interseção.

Não, a esfera auxiliar não permite resolver interseções diretamente. O problema é que o mapeamento do elipsóide para a esfera depende da geodésica (por exemplo, seu azimute no equador). Assim, a esfera auxiliar é boa para resolver uma única geodésica, mas não para resolver qualquer problema que envolva mais de uma geodésica.

Minha maneira recomendada de fazer interseções e interceptações geodésicas (caminho mais curto entre um ponto e uma geodésica) é usar a projeção gnomônica. A geodésica em uma esfera é mapeada para linhas retas na projeção gnomônica e, portanto, desde que seu problema esteja confinado a um hemisfério, a projeção gnomônica converte esses problemas em 2d.

Não há projeção que preserve a retidão da geodésica para um elipsóide (porque sua curvatura não é constante). No entanto, GeographicLib fornece uma generalização da projeção gnomônica na qual a geodésica é quase reta. Isso leva a algoritmos de convergência rápida para interseção e interceptações geodésicas (novamente desde que os pontos estejam todos dentro do hemisfério). Veja minhas respostas (com código!) Para o gpesquero em

https://sourceforge.net/projects/geographiclib/forums/forum/1026621/topic/4085561

Por fim, gostaria de salientar que converti recentemente as rotinas geodésicas da GeographicLib para Javascript, para que você possa brincar com elas no Google Maps. Vejo

http://geographiclib.sourceforge.net/scripts/geod-google.html

http://geographiclib.sourceforge.net/scripts/geod-calc.html

(Ainda não converti a projeção gnomônica em Javascript. Isso seria razoavelmente direto. Eu também converteria a projeção equidistante azimutal ao mesmo tempo, já que é uma maneira conveniente de resolver outra classe de problemas geodésicos que envolvem "linhas medianas". .)

ADENDA (19/08/2014)

Também é possível resolver o tempo de aproximação mais próxima para duas embarcações que viajam em velocidade constante ao longo da geodésica. Como conhecemos as propriedades diferenciais da geodésica, é possível usar o método de Newton para obter uma solução precisa em algumas iterações. O código para implementar isso é publicado em

https://sourceforge.net/p/geographiclib/discussion/1026620/thread/33ce09e0

cffk
fonte
Tenho certeza de que estou fora dos trilhos, mas não sei onde; Eu adoraria se você pudesse ajudar a depurar meu raciocínio. (Próximo comentário.) Caso contrário: agradeço muito pelo código útil + comentário + link; é tremendamente útil.
Dan S.
Aqui vai, da forma mais concisa possível. Meu raciocínio é expresso em cordas cartesianas 3D, e não angulares: (a) Em uma esfera, todos os pontos em um grande círculo são coplanares. (b) A transformação para a esfera auxiliar é linear e invertível. (Pensamento equivocado?) (C) Todos os pontos em uma geodésica elíptica se transformam em pontos ao longo de um grande círculo no aux. esfera. (d) Todos os pontos em uma geodésica elíptica também são coplanares, devido a (b). Finalmente, (e): Devido à coplanaridade, dois pontos de interseção geodésica candidatos no elipsóide podem ser encontrados por interseção plana.
Dan S.
1
@ Dan, um geodésico elipsoidal não está no plano. (Se assim fosse, teria que ser uma curva plana; e, no entanto, sabemos que, em geral, em cada circuito do globo a geodésica fica aquém de uma quantidade O (f).) A falha no seu raciocínio é (b ) - a conexão entre o aux. esfera e o elipsóide não é linear. A transformação de latitude é equivalente a um trecho na direção z e, portanto, é linear. No entanto, as longitudes são relacionadas por uma integral elíptica e isso impede que exista qualquer relação linear simples.
Cffk