Minimum distance between two approximate GPS coordinates

Question

I have two pairs of latitude and longitude, but each pair also has an associated radius, because the coordinates may be more or less accurate. How to find the minimum distance between two circular areas on Earth?

• The .NET code here calculates the distance between two precise geocoordinates, but does not take into account the associated radii.

Example

What is the shortest distance between the perimeters of these two circles, one in London, England and the other in Cancun, Mexico ?

• 51°31′2″ N 0°7′50″ W radius 90m
• 21°7′45″ N 86°45′49″ W radius 550m

Also, the distance between these two overlapping areas should be 0 meters:

• 21°7′46″ N 86°45′49″ W radius 50m
• 21°7′45″ N 86°45′49″ W radius 550m

Answer 1

A cheap and cheerful approximation would be to find the distance between the centres and then subtract the radius of each circle from that. If the result is negative the circles overlap and the minimum distance is 0; otherwise the minimum distance is the result. This would give the exact answer on a plane.

Actually, except for some odd cases involving nearly antipodal points I think this will give the correct answer on a spheroid too. For (except for the odd cases) if the centres (A and B say) are d apart, then there will be a geodesic from A to B of length d. If we go a distance r (radius of the circle about A) along the geodesic toward B we will get to a point a on the circle, and similarly (from B a distance s going towards A) we get to a point b on the circle about B. The geodesic from A to B is also a geodesic from a to b, and the distance along it is d-r-s. So the distance from a to b is d-r-s. There can't be points (a',b' say) on the circles closer then that, for if there were we could get from A to B by going from A to a', along the geodesic from a' to b' and then from B to b; but the geodesic from A to B is the shortest route.

Answer 2

Assuming the two regions are "close enough" so one can neglect the spherical nature of the problem, along with ...

Assuming that those "confidence regions" are somehow important to the user of the result, along with ...

The fact that a single number as a result would erase the uncertainty of the information (or the measurement errors), I would recommend to not expect a number but an interval to be an adequate result.

Let p1, p2 be two "close enough" centers of regions R1, R2.
Let u1, u2 be the uncertainty of the position in the same distance unit as p1, p2 are measured, as the radius of those circles.

Center distance:
dc p1 p2 = |p2-p1|

BorderDistance Minimum:
bdmin p1 p2 u1 u2 = (dc p1 p2) - u1 - u2

BorderDistance Maximum:
bdmax p1 p2 u1 u2 = (dc p1 p2) + u1 + u2

Then, the distance between those regions is the interval:

[bdmin p1 p2 u1 u2, bdmax p1 p2 u1 u2]

let sq x = x*x
let distance p1 p2 : float = 
    let x1,y1 = p1
    let x2,y2 = p2
    sqrt(sq (x2-x1) + sq (y2-y1))

let rdistance p1 u1 p2 u2 = 
    ( (distance p1 p2) - u1 - u2
    , (distance p1 p2) + u1 + u2
    )

let rdistance3 p1 u1 p2 u2 =
    let mi,ma = rdistance p1 u1 p2 u2
    (mi,distance p1 p2,ma)


let P1 = (0.0,0.0)
let P2 = (10.0,10.0)
let U1 = 2.0
let U2 = 5.0

printfn "as interval: %A" (rdistance P1 U1 P2 U2)
printfn "as interval with center: %A" (rdistance3 P1 U1 P2 U2)

as interval: (7.142135624, 21.14213562)
as interval with center: (7.142135624, 14.14213562, 21.14213562)

The latter version is nice as it allows users to continue as they please, having all 3 values and also are able to get a feeling for the accuracy.

Discussion:

If the true data looks like the one on the picture, it does not pay off to take spherical geometry formulae for the computation. The reason being, that the size of the circles is magnitudes larger than the error yielded from euklidean geometry.

If, on the other hand, the true data would be at significantly large distances, it would probably not matter if the center points or the edges of the circles were taken for the computation. As then the radius of the circles would be tiny compared to the distance. Then, though, spherical geometry is needed.

Last not least, if this is only one step in a longer series of computations, it pays off to keep accuracy information.

See for example the wikipedia article on interval arithmetic.

If you see U1, U2 as statistical parameters, such as the n% confidence region (think something like standard deviation), then you can try to find a statistical model and reason about it.

Warming up, if we assumed both P1 and P2 were measured points from the same statistical distribution, which they are obviously not. Then, the variance of both points would be the same. Which is obviously not the case. Then, given a series of P1,P2 pairs, you could estimate the underlying distribution and use something like a t-test to test the hypothesis P1 = P2.

Now, what you probably have as your U1, U2 in GPS laymans terms is called "dilution of precision" (DOP, some use 2, actually HDOP,VDOP), which is a single number, aggregating the uncertainty of the GPS fix computation. It is a function of many parameters, as a GPS receiver can actually notice:

• Number of visible and used satellites used for the fix
• Estimate of time accuracy
• Accuracy information stated by the satellites
• ...

Let's say, the GPS receiver only sees 3 satellites. What it does is "measure" the distance to each satellite which is at a location known to the GPS receiver (the satellites send their positions). So from each of the satellites, the receiver can yield a sphere of its own position, with the radius of the sphere being the distance, the center being the location of the satellite.

Intersecting the Spheres computed for each used satellite, one can receive a volume in which the GPS receiver is located. In the absence of any measurement errors etc. it would actually the be exact location of the receiver...in case of selective availability being turned off. SA is an artificial error satellites can add to their information, which decreases the accuracy, civilian GPS receivers can obtain. I think it has been turned off now for a while...

Since the GPS receiver does not have an atomic clock, but the GPS satellites do have those, the estimation task of the receiver is not only to estimate its 3 coordinates, but also the state of its own cheap clock. This is why a GPS fix with only 3 satellites is also called a 2D fix (as the system of equations is still underdetermined). 4 and more satellites yield a 3D fix.

Beyond that basic theory of how it works, there are factors specific to the location of the GPS receiver. Apart from the number of satellites a receiver can use in a given location, there can be RF frequency reflections etc., which can render the "distance computed by time delay" for one or more satellites errorneous. If, say the GPS receiver sees many more than 4 satellites, it will be able to construe, that some measurements are inconsistent compared to the remaining measurements.

All those aspects shown above are then computed into a single floating point number, named "Dilution of precision".

So, clearly it is not easy to take basic statistical tests for the hypothesis P1 <> P2 and one would have to dig deeper than is possible here in this format.