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.
1
-
languages, toolkits, libraries, implementations, a bit of light?– falcacibarCommented Sep 22, 2011 at 18:41
Add a comment
|
3 Answers
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.
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.
answered Sep 22, 2011 at 18:05
-
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.– whuberCommented Sep 22, 2011 at 20:25
-
@whuber I've taken it out and hopefully simplified things. Commented Sep 22, 2011 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.– whuberCommented Sep 22, 2011 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?). Commented Sep 22, 2011 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.– whuberCommented Sep 22, 2011 at 23:24
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.
-
1Could you please post thesolution here, because the link does no longer work– KurtCommented Dec 28, 2014 at 18:48
-
Yes, somebody please post the full algebraic solution since the link is broken. Commented Jul 7, 2017 at 19:54
Since people are asking for a full algebraic solution, here's one that I worked through for the problem on a sphere. I am providing a link rather than a full solution since LaTeX formatting (for the math) is not provided on this site.
