Mais próximo quadrícula a um ponto em coordenadas esféricas

Question

Eu estou programando um algoritmo onde eu ter quebrado a superfície de uma esfera em pontos de grade (para simplificar eu tenho as linhas de grade em paralelo e perpendicular aos meridianos). Dado um ponto A, eu gostaria de ser capaz de tomar forma eficiente qualquer grid "quadrado" e determinar o ponto B na praça com o menos esférica coordenar distância AB. No caso degenerado os "quadrados" são na verdade "triângulos".

Eu estou na verdade, apenas usá-lo para limitar quais quadrados Estou procurando, então eu também pode aceitar uma limite inferior se é apenas uma pequena pouco fora. Por esta razão, eu preciso o algoritmo para ser extremamente rápida caso contrário, seria melhor tomar apenas a perda de precisão e procurar mais algumas praças.

• I decidiu repassar o presente pergunta para Math Overflow: https : //mathoverflow.net/questions/854/closest-grid-square-to-a-point-in-spherical-coordinates . Mais progresso tem sido feito aqui

Answer 1

Veja Math Overflow: https://mathoverflow.net / perguntas / 854 / mais próximo-grid-square-se um ponto-in-esféricas coordenadas para uma solução exata

Answer 2

Para os pontos sobre uma esfera, os pontos mais próximos no espaço 3D completo também estará mais próximo quando medido ao longo da superfície da esfera. As distâncias reais serão diferentes, mas se você está apenas após o ponto mais próximo é provavelmente mais fácil para minimizar a distância 3D ao invés de se preocupar com grandes arcos de círculos, etc.

Para encontrar o ortodromia real entre dois pontos (latitidude, longitude) sobre a esfera, você pode usar a primeira fórmula em este link .

Answer 3

Alguns pontos, para maior clareza.

A menos que você especificamente gostaria que essas quadrados para ser quadrado (e, portanto, não se encaixam exatamente neste paralela e layout perpendicular em relação aos meridianos), estes não são exatamente quadrados. Isto é particularmente visível se as dimensões do quadrado são grandes.

A pergunta fala de um [perfeita] esfera. Assuntos seria um pouco diferente se nós estávamos considerando a Terra (ou outros planetas) com seus pólos achatados.

A seguir é um "algoritmo", que seria o bill, eu duvido que ele é o ideal, mas poderia oferecer uma base boa. Editar : veja a sugestão de Tom10 ao trabalho com a distância 3D planície entre os pontos em vez do que o correspondente grande distância cirle (ou seja, do cabo ao invés do arco), pois isso irá reduzir significativamente a complexidade do fórmulas.

Problem layout:  (A, B and Sq as defined in the OP's question)
 A  : a given point the the surface of the sphere
 Sq : a given "square" from the grid 
 B  : solution to problem : point located within Sq which has the shortest 
      distance to A.
 C  : point at the center of Sq

Tentative algorithm:
Using the formulas associated with [Great Circle][1], we can:
 - find the equation of the  circle that includes A and C
 - find the distance between A and C. See the [formula here][2] (kindly lifted
    from Tom10's reply).
 - find the intersect of the Great Circle arc between these points, with the
   arcs  of parallel or meridian defining the Sq.
   There should be only one such point, unless this finds a "corner" of Sq, 
   or -a rarer case- if the two points are on the same diameter (see 
   'antipodes' below).
Then comes the more algorithmic part of this procedure (so far formulas...):
 - find, by dichotomy, the point on Sq's arc/seqment which is the closest from
   point A.  We're at B! QED.

Optimization:  
 It is probably possible make a good "guess" as to the location
 of B, based on the relative position of A and C, hence cutting the number of
 iterations for the binary search.
 Also, if the distance A and C is past a certain threshold the intersection
 of the cicles' arcs is probably a good enough estimate of B.  Only when A
 and C are relatively close will B be found a bit further on the median or
 parallel arc in these cases, projection errors between A and C (or B) are
 smaller and it may be ok to work with orthogonal coordinates and their 
 simpler formulas.

Another approach is to calculate the distance between A and each of the 4 
corners of the square and to work the dichotomic search from two of these
points (not quite sure which; could be on the meridian or parallel...)

( * ) *Antipodes case*:  When points A and C happen to be diametrically 
opposite to one another, all great circle lines between A and C have the same
 length, that of 1/2 the circonference of the sphere, which is the maximum any
 two points on the surface of a sphere may be.  In this case, the point B will
 be the "square"'s corner that is the furthest from C. 

Espero que isso ajude ...

Answer 4

O método limite inferior preguiçoso é encontrar a distância para o centro da praça, em seguida, subtrair a distância diagonal meio e ligados utilizando a desigualdade triangular. Dado estes não são quadrados reais, não vai ser realmente duas distâncias diagonais - vamos usar o maior. Suponho que será razoavelmente precisa também.