Douglas-Puker - The shortest arc from a point to a circle, on the surface of a sphere

Question

I saw many examples in different programming languages ​​that use the Douglas-Picker polyline simplification algorithm to create a GPolyline that will be used on Google Maps. The algorithm expressed for polylines on the plan involves calculating the distance between a point and a line (passing through two other points).

Now all the examples I've seen so far apply the algorithm in a very naive way, simply replacing x and y with latitude and longitude. This can give acceptable results if the polyline is very localized, not too close to the pole, and does not cross the 180 ° meridian, but I would like to implement a more general version of the algorithm.

So, if I'm not mistaken, I will need to calculate the length of the shortest arc on the surface of the sphere, from a point to a circle passing through two other points on the surface of the sphere, the center of which coincides with the center of the sphere (Earth).

Does anyone know a formula that calculates this length?

Thanks in advance

Answer 1

I will try to express everything in terms of the unit vectors p , q and r , which can be considered as points on the unit sphere & Sigma; centered at the beginning of 0 . You can convert this to terrestrial values ​​by increasing the radius of the earth. There is background material here .

We want to find a large distance d from p to a large circle C passing through q and r strong>. C is the intersection of the plane P and the sphere & Sigma; , where P is the plane passing through q , r and the beginning 0 . d is just the angle & theta; (expressed in radians) between p and P. The normal vector for P is the normalized transverse product q x r / sin? phi; where? phis; is the angle between q and r .

As a result, we get

& theta; = arcsin ( p & sdot; ( q * r ) / sin & phi;)

As I said, everything here expands with the radius R of the earth. Thus, there are three points: * R *** p **, * R *** q **, * R *** r **, and the distance is R the.

However, if all you want is to find combos with points / lines with the shortest distance, you can omit the multiplication by R. In fact, you can omit arcsin () and just look at the relative sizes of p & SDOT; ( d & t ; t ) / sin & phi ;.