Tell me more ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.
up vote 3 down vote favorite

I only actually need to intersect a great circle arc i.e. the shortest path between two points, with a given small circle.

I found this tutorial for intersecting two great circle arcs, but unfortunately it doesn't cover small circles.

share|improve this question
languages, toolkits, libraries, implementations, a bit of light? – falcacibar Sep 22 '11 at 18:41

2 Answers

up vote 4 down vote

While an algebraic solution is possible if one assumes the earth is a sphere, we can still handle an ellipsoidal earth using Newton's method and a Esri's projection engine. The projection engine is a c style dll (pe.dll) and is bundled with the freely downloadable ArcGIS Explorer.

I think the question could be rephrased as ...

A plane is flying from NewYork to Tokyo along a great circle path - at what location(s) along it's journey is it exactly 3000 miles from San Francisco?

Think of the problem in terms of a plot of X vs Y where X is the airplane is from New York, and Y is the distance the airplane is from San Francisco. The curve can be generated using the projection engine.

The problem then becomes finding the place(s) where the curve crosses the y=3000 line.

We can make some assumptions about the curve, it is either:

  • Flat (San Franciso would be pole of great circle)
  • a single hill
  • a single valley

Here's just a guess what the curve would look like. enter image description here

By determining the slope of the curve at a guessed x, Newton's method can make an appropriate next guess, allowing it to quickly find the points where the lines intersect, or determine that they don't intersect - without knowing the internals of the projection engine.

share|improve this answer
Good approach. Note that your pseudocode does not implement Newton's method; its runtime is uncertain (and potentially infinite), because it avoids the important question of how to pick the new point, and that at best it finds a single solution whereas usually there are two or none. – whuber♦ Sep 22 '11 at 20:25
@whuber I've taken it out and hopefully simplified things. – Kirk Kuykendall Sep 22 '11 at 21:22
+1 Much better. Newton's method requires more than a guess of the slope: it needs to calculate it. One could use the secant method to great effect here: it is close to your description of repeatedly guess-the-slope & correct. The details can get messy due to the possibility of 0, 1, or 2 solutions along any arc. The salient point of your approach is that it can get correct answers for an ellipsoid by exploiting no more than the GIS's ability to do distance calculations and to move around along a geodesic arc between two points. – whuber♦ Sep 22 '11 at 22:22
Changed. I guess it could get in an infinite loop in the case where there are two solutions that are closer together than the step size (epsilon?). – Kirk Kuykendall Sep 22 '11 at 23:08
In that case it should find a unique solution. There are standard techniques to avoid infinite loops: first, bracket a solution; second, terminate whenever either the last step was sufficiently small or the value of the function is sufficiently close to zero; third, terminate with an error if the new step is longer than the old step. – whuber♦ Sep 22 '11 at 23:24
up vote 1 down vote accepted

Here is a full algebraic solution for two arbitrary small circles, using Cartesian coordinates to simplify the maths.

It's assumed the earth is a spherical, but that's fine for my purposes.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.