Ближайший квадрат сетки к точке в сферических координатах

Question

Я программирую алгоритм, в котором разбиваю поверхность сферы на точки сетки (для простоты линии сетки параллельны и перпендикулярны меридианам).Учитывая точку A, я хотел бы иметь возможность эффективно взять любой «квадрат» сетки и определить точку B в квадрате с наименьшим сферическим координатным расстоянием AB.В вырожденном случае «квадраты» на самом деле являются «треугольниками».

На самом деле я использую его только для определения того, какие квадраты я ищу, поэтому я также могу принять нижняя граница если оно хоть чуть-чуть отклоняется.По этой причине мне нужно, чтобы алгоритм был максимально быстрым, иначе было бы лучше просто принять потерю точности и поискать еще несколько квадратов.

• Я решил перепостить этот вопрос в Math Overflow: https://mathoverflow.net/questions/854/closest-grid-square-to-a-point-in-Sphereical-coordinates.Здесь достигнут больший прогресс

Answer 1

См. Математическое переполнение: https://mathoverflow.net/questions/854/closest-grid-square-to-a-point-in-Sphereical-coordinates для точного решения

Answer 2

Что касается точек на сфере, точки, расположенные ближе всего в трехмерном пространстве, также будут ближайшими при измерении вдоль поверхности сферы.Фактические расстояния будут другими, но если вы находитесь сразу за ближайшей точкой, вероятно, проще минимизировать трехмерное расстояние, чем беспокоиться о больших дугах окружностей и т. д.

Чтобы найти фактическое расстояние по большому кругу между двумя точками (широта и долгота) на сфере, вы можете использовать первую формулу в эта ссылка.

Answer 3

Несколько моментов для ясности.

Если вы специально не хотите, чтобы эти квадраты были квадратными (и, следовательно, чтобы они не вписывались точно в эту параллельную и перпендикулярную компоновку относительно меридианов), это не совсем квадраты.Особенно это заметно, если размеры квадрата большие.

В вопросе говорится о [совершенной] сфере.Дело обстояло бы несколько иначе, если бы мы рассматривали Землю (или другие планеты) с ее уплощенными полюсами.

Ниже приводится «алгоритм», который соответствует всем требованиям. Я сомневаюсь, что он оптимален, но может предложить хорошую основу. РЕДАКТИРОВАТЬ:см. предложение Tom10 работать с простым трехмерным расстоянием между точками, а не с соответствующим расстоянием по большому кругу (т.е.шнура, а не дуги), так как это значительно уменьшит сложность формул.

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. 

Надеюсь, это поможет...

Answer 4

Метод ленивой нижней границы состоит в том, чтобы найти расстояние до центра квадрата, затем вычесть половину расстояния по диагонали и оценить его с помощью неравенства треугольника.Поскольку это не настоящие квадраты, на самом деле диагональных расстояний будет два — мы будем использовать большее.Я полагаю, что это также будет достаточно точно.