The closest grid square to a point in spherical coordinates
I am programming an algorithm where I have split the surface of a sphere into grid points (for simplicity, I have grid lines parallel and perpendicular to the meridians). Given point A, I would like to be able to effectively take any square grid and define point B in the square with the smallest spherical coordinate distance AB. In the degenerate case, "squares" are actually "triangles".
I only use it to tie the squares I am looking for, so I can also accept the bottom border if it is dropped a little. For this reason, I need the algorithm to be extremely fast, otherwise it would be better to just lose precision and find a few more squares.
- I decided to post this question to Math Overflow: https://mathoverflow.net/questions/854/closest-grid-square-to-a-point-in-spherical-coordinates . Significant progress has been made here.
source to share
See Math Overflow: https://mathoverflow.net/questions/854/closest-grid-square-to-a-point-in-spherical-coordinates for the exact solution
source to share
For points on a sphere, the points closest to full 3D space will also be the closest when measured along the surface of the sphere. The actual distances will vary, but if you are only after the closest point then it is probably easiest to minimize the 3D distance rather than worrying about big circle arcs etc.
To find the actual distance between two points (latitidude, longitude) on a sphere, you can use the first formula in this link .
source to share
A few points for clarity.
Unless you specifically want these squares to be square (and therefore do not correspond exactly to this parallel and perpendicular arrangement with respect to the meridians), they are not exactly squares. This is especially noticeable if the dimensions of the square are large.
The question speaks of an [ideal] sphere. The question would be somewhat different if we were considering the Earth (or other planets) with its flattened poles.
Below is the "algorithm" that would fit the bill, I doubt it is optimal but may suggest a good foundation. EDIT : See Tom10's suggestion to work with a simple 3D point-to-point spacing rather than an appropriately large channel spacing (like a cord rather than an arc), as this would greatly reduce the complexity of the formula.
Problem layout: (A, B and Sq as defined in the OP 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 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 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" corner that is the furthest from C.
Hope this helps ...
source to share
The lazy lower bound method is to find the distance to the center of the square, then subtract the half-diagonal distance and relate it using the triangle inequality. Given that these are not real squares, there will actually be two diagonal distances - we will use more. I believe it will be accurate enough as well.
source to share