Rejilla más cercana plaza a un punto en coordenadas esféricas

Question

Yo soy de programación de un algoritmo que me ha roto la superficie de una esfera en los puntos de cuadrícula (por simplicidad tengo la cuadrícula de líneas paralelas y perpendiculares a los meridianos).Dado un punto a a Un punto, me gustaría ser capaz de tomar de manera eficiente cualquier cuadrícula de la "plaza" y determinar el punto B en la plaza con el menos esférica coordinar la distancia AB.En el caso de degeneración de las "plazas" son en realidad "triángulos".

De hecho, estoy solo lo utiliza para limitar los cuadrados que estoy buscando, para que yo también pueda aceptar una límite inferior si es sólo un poco apagado.Por esta razón, necesito el algoritmo de ser extremadamente rápido, de lo contrario sería mejor tomar sólo la pérdida de la precisión y la búsqueda de un par de cuadrados más.

• He decidido publicar esta pregunta a las Matemáticas de Desbordamiento: https://mathoverflow.net/questions/854/closest-grid-square-to-a-point-in-spherical-coordinates.Más avances ha realizado aquí

Answer 1

Ver La Matemática De Desbordamiento: https://mathoverflow.net/questions/854/closest-grid-square-to-a-point-in-spherical-coordinates para una solución exacta

Answer 2

Para los puntos en una esfera, los puntos más cercanos en el espacio 3D completo también habrá más cercano cuando se mide a lo largo de la superficie de la esfera. Las distancias reales serán diferentes, pero si estás justo después del punto más cercano es probable que sea más fácil para reducir al mínimo la distancia 3D en lugar de preocuparse por arcos de círculo, etc.

Para encontrar la distancia de círculo máximo real entre dos puntos (latitidude, longitud) sobre la esfera, se puede utilizar la primera fórmula en este enlace .

Answer 3

A los pocos puntos, para mayor claridad.

A menos que desee específicamente estos cuadrados a ser cuadrada (y por tanto a no encaja exactamente en este diseño paralelo y perpendicular con respecto a los meridianos), estos no son exactamente cuadrados. Esto es particularmente visible si las dimensiones de la plaza son grandes.

La pregunta habla de una esfera [perfecta]. Asuntos serían algo diferente si estábamos teniendo en cuenta la Tierra (u otros planetas), con sus polos aplanados.

A continuación se presenta un "algoritmo" que encajaría el proyecto de ley, lo dudo es óptimo, pero podría ofrecer una buena base. Editar : ver la sugerencia de Tom10 a trabajar con la distancia 3D llanura entre los puntos en lugar de la correspondiente distancia cirle gran (es decir, la de la cuerda en lugar de arco), ya que esto reducirá en gran medida la complejidad de la 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 esto ayude ...

Answer 4

El método cota inferior perezoso es para encontrar la distancia al centro de la plaza, luego restar la distancia diagonal media y unida usando la desigualdad triangular. Teniendo en cuenta estos no son cuadrados reales, en realidad habrá dos distancias diagonales - vamos a utilizar el mayor. Supongo que será razonablemente precisa también.