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

Question

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

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

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

Answer 1

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

Answer 2

Несколько точек, для ясности.

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

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

Ниже приведен алгоритм, который будет соответствовать законопроекту, я сомневаюсь, что он оптимален, но может предложить хорошую основу. EDIT: см. Предложение 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 3

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

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

Answer 4

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