Più vicino a griglia quadrata di un punto in coordinate sferiche

Question

Io sono la programmazione di un algoritmo in cui ho suddiviso la superficie di una sfera in una griglia di punti (per semplicità ho la griglia di linee parallele e perpendicolari ai meridiani).Dato un punto, vorrei essere in grado di gestire efficientemente qualsiasi griglia "piazza" e determinare il punto B in piazza con il minimo di coordinate sferiche distanza AB.In caso degenerato le "piazze" sono in realtà i "triangoli".

In realtà sto solo usando per vincolato che le piazze sono di nuovo alla ricerca, così posso anche accettare un limite inferiore se è solo un po ' di sconto.Per questo motivo, ho bisogno di un algoritmo per essere estremamente rapido in caso contrario, sarebbe meglio prendere la perdita di precisione e di ricerca di un paio di altre piazze.

• Ho deciso di pubblicare questa domanda di Matematica Overflow: https://mathoverflow.net/questions/854/closest-grid-square-to-a-point-in-spherical-coordinates.Ulteriori progressi sono stati fatti qui

Answer 1

Vedere Overflow: https://mathoverflow.net/questions/854/closest-grid-square-to-a-point-in-spherical-coordinates per una soluzione esatta

Answer 2

Per i punti su una sfera, i punti più vicini nello spazio pieno 3D sarà anche più vicino quando misurata lungo la superficie della sfera. Le distanze reali saranno diverse, ma se siete appena dopo il punto più vicino è probabilmente più facile per ridurre al minimo la distanza 3D, piuttosto che preoccuparsi di grandi archi di cerchio, ecc.

Per trovare la distanza grande cerchio reale tra due punti (latitidude, longitudine) sulla sfera, è possibile utilizzare la prima formula in questo link .

Answer 3

Alcuni punti, per chiarezza.

A meno che non espressamente desidera queste piazze per essere quadrato (e quindi di non rientra esattamente in questo layout paralleli e perpendicolari per quanto riguarda i meridiani), queste non sono esattamente quadrati. Questo è particolarmente visibile se le dimensioni del quadrato sono grandi.

La questione parla di un [perfetto] sfera. Questioni sarebbe un po 'diverso se stavamo considerando la Terra (o su altri pianeti), con i suoi poli appiattite.

A seguito è un "algoritmo" che si adatterebbe il disegno di legge, ne dubito è ottimale, ma potrebbe offrire una buona base. modifica : vedi suggerimento di Tom10 a lavorare con la distanza 3D piana tra i punti piuttosto che la grande distanza cirle corrispondente (cioè quello del cavo anziché l'arco), in quanto riduce notevolmente la complessità della formule.

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. 

Spero che questo aiuta ...

Answer 4

Il metodo limite inferiore artificiale è di trovare la distanza dal centro del quadrato, quindi sottrarre la distanza diagonale metà e legato usando la disuguaglianza triangolare. Alla luce di queste non sono vere e proprie piazze, ci saranno effettivamente due distanze diagonali - useremo il più grande. Suppongo che sarà ragionevolmente accurata pure.