2
$\begingroup$

Hi, my apologies if this is not the right place to ask this- I am not a mathematician (I'm a software engineer) and Im working on some 3D applications.

My situation is this- given an origin of 0,0,0 and any two points I need to be able to return the xyz coordinate of any point that is on the line between these two points- with the assumption being that the two points must fall on a symmetrical closed surface surrounding the origin, sphere or ellipsoid. So the line would follow the surface shortest distance between the two points.

So for example, I would need the xyz point that is 0.1 of the line length... but I have no idea how to get it...

Is this possible from 2 points and an origin only? I am implementing this in C# if that helps.

Thanks!

$\endgroup$
5
  • $\begingroup$ Your question isn't at the right level for this site. To give you some pointers, what you want is to calculate the "geodesics" on the sphere or ellipsoid. For spheres, these are simply the great circles. You should probably consult a book on differential geometry of curves and surfaces e.g. Do Carmo's, which will give you the background to calculate these curves. $\endgroup$
    – j.c.
    May 21, 2010 at 21:55
  • 1
    $\begingroup$ And how exactly do you propose to find the shortest curve between two points on the ellipsoid numerically? Note also that unlike the sphere case, the situation when you have several geodesics joining two points on the ellipsoid is not exceptional. I think the level of the question is OK and that consulting a textbook on differential geometry won't be really helpful here. $\endgroup$
    – fedja
    May 21, 2010 at 22:17
  • $\begingroup$ The tag "elliptic curves" may have been slightly appropriate. After all, elliptic integrals may pertain... $\endgroup$ May 21, 2010 at 22:36
  • $\begingroup$ @fedja Good points, I admit I didn't think very hard about the question before my response and hereby retract my statement that it may be at the wrong level. I only mentioned the textbook as it seemed the asker wasn't using the standard terminology, and so I assumed perhaps didn't have differential geometry background. @Steve, I think it's a stretch considering the other questions that are tagged elliptic-curves. Feel free to add back the tag if you feel strongly about it. $\endgroup$
    – j.c.
    May 21, 2010 at 22:45
  • $\begingroup$ You can get a geodesic on the ellipsoid by exploiting the fact that the problem is underspecified. We have two points. Work in the plane containing them and the origin. Fit an ellipse. We can fatten this up to an ellipsoid with a principal axis perpendicular to the plane. Symmetry ensures the shortest path on the ellipse is a geodesic on the ellipsoid, at least of the ellipsoid is fat enough along the perpendicular. From the description it's hard to know if this is what the asker wants. $\endgroup$
    – Dan Piponi
    May 22, 2010 at 0:48

2 Answers 2

8
$\begingroup$

I guess you are in the GPS business, aren't you ? I think that Vincenty 1975 paper is what you are looking for. At least it should be a starting point for a bibliographic search.

Let me add a few remarks. Fortunately, free motion on the ellipsoid is an integrable system. Which means (loosely) that you can explicitly solve the equations of the trajectory using just a few integrals. This was done by Jacobi (1838).

So if you are not happy with Vincenty approach, there are two paths you can follow. Either look in a book (or click here) for the differential equations satisfied by the geodesics, and do a numerical integration. Or you can start from the solutions of these equations, which are given by elliptic functions. There are standard libraries in C for computing numerical values for these functions.

As a reference, I recommend the book "Elliptic functions and applications" by Derek F. Lawden. As far as I recall, the problem is solved in the book (I hope my memory is not betraying me). And I should add, this is a great book for everybody interested in making the connection between elliptic functions and classical mechanics.

By the way, if you are interested in the following question: on which manifold is the geodesic flow integrable ? then you can have a look at a short survey by Andre Miller. And if you are interested in a clever proof of the integrability of the geodesic flow that works in any dimension, there is an online paper by S. Tabachnikov.

$\endgroup$
1
$\begingroup$

If you are willing to accept an approximation, there is quite a bit of work on finding shortest paths on convex polyhedra, much of it implemented. For example, here are two images of shortest paths from one point to all vertices of a polyhedron inscribed in an ellipsoid:


EllFront EllBack
Images from Biliana Kaneva and J. O'Rourke, "An Implementation of Chen & Han's Shortest Paths Algorithm" Proc. of the 12th Canadian Conference on Computational Geometry, New Brunswick, 2000, pp. 139-146. Webpage link.
There is a nice Stanford presentation on the topic:

"Approximating Shortest Paths on a Convex Polytope in Three Dimensions." (PDF download.)

Exact shortest paths can even be computed in optimal $O(n \log n)$ time now, but the algorithm is quite complicated:

Yevgeny Schreiber, Micha Sharir. "An Optimal-Time Algorithm for Shortest Paths on a Convex Polytope in Three Dimensions." Discrete & Computational Geometry, March 2008, Volume 39, Issue 1–3, pp 500–579. (Springer link.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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