Copyright © 2004 jsd

1  Great-Circle Navigation using Vectors

We are given two points on the sphere, point A and point B. The task is to find the heading that we should use when departing A via the great-circle route to B.

We are going to do this with a minimum of trigonometry, using instead vector techniques.

(You don’t need to know anything about Clifford Algebra to follow the derivation or carry out the calculations ... although there is some passing mention of Clifford-Algebra ideas, such as for giving a name to the AB plane. The optional section 3 is the only part that makes nontrivial use of Clifford Algebra.)

Without loss of generality, let’s scale things so that our sphere is the unit sphere. Consequently A and B are unit vectors.

Assumption #1: We assume A is not a multiple of B, because otherwise the problem is trivial: any direction will equally well get you from A to B. To say the same thing more formally, we assume AB is nonzero.

Assumption #2: We assume A is not the north or south pole. Otherwise expressing the answer as a heading is not useful. (Some useful alternatives will be given below.)

By way of preparation, it will be convenient to construct a unit vector W that lies in the AB plane and is perpendicular to A. To remove an ambiguity as to the sign of W, we require that W lie on the "same side" as B, so that B · W is positive.

We construct W by subtracting from B the component parallel to A in the usual way:

w := 
B − 
(A · BA 
(A · A)
    = B − (A · BA

and then normalizing:

W := w / |w|              (2)

So much for preparation. Let’s actually attack the main problem now.

Let X(θ) be a point that roves along the great circle from A to B, starting with X=A when θ=0. Then the tangent vector will be dX/dθ.

My physical intuition tells me that the tangent vector, tangent to the great circle at point A, will be just W (or perhaps a multiple thereof, depending on how you scale θ). (If that’s not obvious to you, see the appendix, below.)

So here’s the recipe: If the two vectors A and B are already expressed in rectangular coordinates, that’s great. Otherwise, e.g. if they are in polar coordinates (latitude and longitude), convert them to rectangular coordinates ... which will be the last (or almost the last) use of trig functions in the whole problem!

The vector W is found using equation 1 and equation 2.

Next we need to know what W looks like to the guy on the ground, i.e. in the tangent plane, tangent to the sphere at point A. To get our bearings, let’s determine the vector (call it V) that points from A to the north pole. We can find this immediately using the same technique, just using the north pole instead of B in equation 1.

Now we project out the component of W parallel to V (call it W1). The remainder of W (call it W2) will be perpendicular to V. All of these vectors (W, V, W1, and W2) lie in the tangent plane. This is just another projection exercise:

W1 = 
 (V · WV 
V · V


W2 = W − W1              (4)

At this point we know enough to draw the vector that points from A to B. Lay a piece of graph paper on the floor (aligned NS/EW of course), and draw a vector from the origin to the point (W2, W1).

Note that starting from the rectangular components of A and B, we have gotten to this point without using any trig functions or any other transcendental functions. We have just performed algebraic computations on the components. It’s just add, subtract, multiply, and divide. We can even leave out the square roots, since we only care about the direction of w, not its magnitude. This is arguably important if you need to do this calculation a zillion times per second, and you don’t want to spend all your CPU time evaluating transcendental functions. Specifically: As you move along the great circle, keep track of your position using rectangular coordinates. To find your new position, just take a step along the W vector. You can iterate this process as you go along, following the whole great circle without ever needing any trigonometric functions.

Finally: If you insist on expressing the answer as a heading angle, calculate atan2(W1, W2).

2  Special Cases

For slight extra credit, we now consider the special case where A is at the north pole. The desired departure heading is south (duh!) but that probably isn’t what you wanted to know. To determine which meridian you should follow, you can skip the entire calculation; the answer is just the longitude of B, by inspection.

However, you can appreciate the power and beauty of the vector formulation by observing that you can calculate the vector W just fine, even when A is at the north pole. We cannot calculate the projections W1 and W2, because V doesn’t exist, because we have no useful notion of ’north’ ... but W exists as a perfectly well-behaved vector in real space.

This is import if you’re building something like an autopilot or video game. The flight director can display the vector w as a pointer that points that-a-way ... and it will work just fine at the poles and everywhere else.

To say the same thing in fancier terms:

3  Calculating the Tangent Vector

You can easily prove that the tangent to the great circle at point A is just W, a vector in the AB plane perpendicular to A.

This should be obvious from the geometry of the situation, but it is also possible to prove it by directly calculating the tangent vector. It’s an amusing exercise in Clifford Algebra.

As before, we let X(θ) be a point that roves along the great circle from A to B, starting with X=A when θ=0. We express X(θ) by starting with point A and then applying the operator R(θ), i.e. the rotation operator that rotates things by an angle θ in the AB plane. Once we have X(θ), the tangent vector is just the derivative dX/dθ.

Specifically, for an infinitesimal angle θ, we can use the standard formula (reference 1) for producing a rotation, which gives us

 R(θ) A = (1 + 
 W ∧ AA  (1 + 
 A ∧ W)              (5)

and if you just turn the crank, expanding the RHS and simplifying using the axiomatic properties of vectors A and W, you get

... = A + θ W + (irrelevant terms involving θ2).              (6)

This can be immediately differentiated w.r.t θ, whereupon we find that the tangent vector is W, QED.

4  Remarks: Style etc.

Note that we have taken an essentially non-trigonometric approach. You can keep track of your position, updating your position as you move along the great circle without using trigonometric functions or any other transcendental functions.

Or to say the same thing in more positive terms, this style focuses attention on the vectors. Vectors are physical things, geometric things, having a reality independent of any coordinate system. Operations such as the dot product are independent of the coordinate system. Most of what makes the great-circle nav problem seem hard is just the cruftiness of the polar coordinate system.

5  References

John Denker, "Multi-Dimensional Rotations, Including Boosts" ./rotations.htm

Copyright © 2004 jsd