Understanding Great Circle Arcs Intersection Algorithm

The following material is the result of my attempt to understand the nice example from Jason Davies.
I was puzzled about the origin of the algorithm used to find the intersection of two great circle arcs.
Google helped and I discovered Roger Stafford’s post in Matlab newsgroup and the relevant Python’s implementation in the Spherical Geometry Toolkit.

The algorithm

You have two great circle arcs on a sphere, $a$ from point $\mathbf{a_0}$ to $\mathbf{a_1}$, and $b$ from $\mathbf{b_0}$ to $\mathbf{b_1}$, whose coordinates are expressed as longitude $\theta$ (positive going East of Greenwich) and latitude $\phi$ (positive going North).
Transform theses coordinates over to Cartesian coordinates using the equations:

$$\begin{aligned} x & = cos(\theta) cos(\phi) \\ y & = sin(\theta) cos(\phi) \\ z & = sin(\phi) \end{aligned}$$

where

$$\begin{equation} -\pi \le \theta \le \pi \\ -\frac{\pi}{2} \le \phi \le \frac{\pi}{2}. \end{equation}$$

These Cartesian coordinates correspond to a hypothetical spherical “earth” of unit radius, but that does not interfere in the following computations.

Let $\mathbf{a_0}$, $\mathbf{a_1}$, $\mathbf{b_0}$, and $\mathbf{b_1}$ be vectors of the Cartesian coordinate endpoints for the two arcs $a$ ($\mathbf{a_0} \leftrightarrow \mathbf{a_1}$) and $b$ ($\mathbf{b_0} \leftrightarrow \mathbf{b_1}$) obtained in this way. Carry out the following computations:

$\mathbf{p} = \mathbf{a_0} \times \mathbf{a_1}$ is the vector normal to the plane going through the arc $a$ and the center of the Earth.

$\mathbf{q} = \mathbf{b_0} \times \mathbf{b_1}$ is the vector normal to the plane going through the arc $b$ and the center of the Earth.

$\mathbf{t} = \mathrm{normalized}(\mathbf{p} \times \mathbf{q})$ is along the line of intersection of the planes above. (The normalization was not mentioned in Roger’s post but it is implemented in the Spherical Geometry Toolkit and by Jason’s example.)

Then, let’s define the following quantities:

$$\begin{aligned} s_1 & = (\mathbf{a_0} \times \mathbf{p}) \cdot \mathbf{t} \\ s_2 & = (\mathbf{a_1} \times \mathbf{p}) \cdot \mathbf{t} \\ s_3 & = (\mathbf{b_0} \times \mathbf{q}) \cdot \mathbf{t} \\ s_4 & = (\mathbf{b_1} \times \mathbf{q}) \cdot \mathbf{t} \end{aligned}$$

(These quantities are crucial: they represent the projection of $\mathbf{t}$ along the arcs $a$ and $b$.)
The arcs $a$ and $b$ will intersect $\iff$ $-s_1$, $s_2$, $-s_3$, and $s_4$ are all of the same sign. In that case they intersect along $+\mathbf{t}$ if they are all positive or along $-\mathbf{t}$ if all are negative.
(Jason tests against $\epsilon = 10^{-6}$, I implemented the test against the sign.)

If they do intersect, you can transform the corresponding vector, $\mathbf{t}$ or $-\mathbf{t}$, back into longitude and latitude (without worrying about its length.) Letting $x$, $y$, $z$ be $\mathbf{t}$’s Cartesian coordinates this reverse transformation can be accomplished this way:

$$\begin{aligned} \theta & = {\mathrm arctan2} (y,x) \\ \phi & = {\mathrm arctan2}(z, \sqrt{x^2+y^2}) \end{aligned}$$

References

• Roger Stafford’s post on Matlab newsgroup (but it lacks the normalization step which is instead used in Jason Davies code, and in Spherical Geometry Toolkit)
• implementation in Python as part of the Spherical Geometry Toolkit
• Jason Davies implementation in D3.js

Written and published with StackEdit.

on revising

Lately I found myself involved into writing.
And I have been often cought into the vicious cycle of revising my (or other's) text without really understanding how to do it properly and when to stop.

I want to summarize some of the advise I found on the web.
I put it here for me to find it again and share.

Let's first paraphrase the famous grook from Piet Hein:

THE ROAD TO WRITING?
Well, it's plain
and simple to express.
revise and revise and revise again,
but less and less and less.

I found an interesting post by Brian Marick.
(And [for now] I reformat it here for my own use. But I will revise it later ;-)

• If a sentence is unclear, do not fix it by adding more words. Fix it by splitting it into two sentences. Then maybe add a third.
• If a paragraph is unclear, do not fix it by adding more sentences. First look earlier in the piece. Can you find a place to add a few sentences that will make the later idea clearer? Perhaps you can rule out an interpretation that will later cause confusion. Write text to head off the problem, then return to adjust the guilty paragraph.
• If an idea or procedure is complicated, don't add more words explaining it. Add an example. If the example is too complicated, don't add more words explaining it. Precede it with a simpler example, then change the explanation of the complicated example to focus on what it adds to the simpler one.
• If you use change tracking, turn display of changes off. You won't be able to make the new text read well if it's all mixed up with the old text.
• After you change a sentence, leave it aside for a while, then come back and reread at least the whole paragraph that contains it. Then tweak the sentence to make it fit better into its environment.

 How do you find what needs revision?

• Can you turn that bullet list into one or more paragraphs? Bullet lists are, on average, easier for writers but harder for readers. They're easier for writers because you don't have to worry about transitions between one idea and the next. They're harder for readers because there are no transitions guiding them from one idea to the next. Will their eyes glaze over because you're not providing them with a sense of flow?
• Read your text aloud. You don't have to write like you speak, but reading aloud changes your perspective. Awkwardness will jump out at you. Reading aloud is one way to get some distance, to separate the piece from your memory of writing it.
  Putting it aside for a day or, better, a week does the same thing.
  I find that reading a printed copy helps me see things I don't see on a screen.
  
  Can you find other tricks?
  Richard P. Gabriel tells the story of one writer who would tape his work to a wall, go to the other side of the room, and read it through binoculars.
  
  Print the piece with a wide margin on one side. Next to each paragraph, scribble a few words about the paragraph's topic. Now read the scribbles. Do they form a progression of thought, a developing story of explanation? Or are they more like a bunch of thoughts hitched together in any old order? If so, shuffle them into a better order. (Some people cut the paragraphs out and move them around; I usually draw arrows from where the paragraph is to where it should go. I suspect the other people do better.)
  
  Sometimes you read a piece where a particular secondary idea or clever chunk of text seems to have undue importance. It's almost as if the piece were distorted to find a way to make that gem fit. That's usually because it was. The gem came first, the piece grew away from it, but the author forced it to stay. Ask what your favorite bit of the piece is, then throw it out - or at least consider how the piece would read if you dropped it. I find this useful to do when I get bogged down during writing.