Sign in to follow this  
FFMG

Calculate shortest distance to a great circle line

Recommended Posts

Hi, I am trying to find the right segment for my vehicle to join a path. My path is made of many Lat/Lon points. As per the discussion in the thread, I need to join the section that is closest to my vehicle. If I have ptA(Lat/Lon) and ptB(Lat/Lon) and my vehicle is at ptC(Lat/Lon). How do I calculate the shortest distance to this great circle line? As an aside, my points are actually fairly close to each others, (a couple of miles at the most), so would it be quicker to calculate the shortest distance using the slop perpendicular? Thanks in advance FFMG

Share this post


Link to post
Share on other sites
You can even do what you want for a "great circle arc". This has the flavor of computing the point on a line segment closest to a specified point. If A and B are the endpoints of the great circle arc, and if P is the specified point, compute the point Q on the great circle through A and B. If Q is between A and B, then Q is the closest arc point to P. If Q is on the "complement arc" (the arc from B to A whose union with the arc from A to B is the full circle), then choose A or B, whichever forms smallest dot product with P.

To compute Q, notice that the plane of the great circle has normal N = Cross(A,B)/Length(Cross(A,B)). Remove the N component of P by projection to obtain a point on the great circle.

Share this post


Link to post
Share on other sites
Quote:
Original post by Dave Eberly
To compute Q, notice that the plane of the great circle has normal N = Cross(A,B)/Length(Cross(A,B)). Remove the N component of P by projection to obtain a point on the great circle.


Sorry I am not sure I fully understand.
How do I calculate Cross(A,B)?


I have some formulas from http://williams.best.vwh.net/avform.htm but I cannot see how to calculate the point to a line.

Would you have any link/formula I could look at?

Many thanks

FFMG

Share this post


Link to post
Share on other sites
Quote:
How do I calculate Cross(A,B)?
Are you asking what the function Cross() represents in this context? Or are you asking how to compute the cross product of two vectors?

Share this post


Link to post
Share on other sites
On a sphere of radius R you have two points A and B that determine a great circle G, and a point C. You wish to compute the distance from C to G.

Look at the points as vectors of length R in 3 dimensions (Google for spherical coordinates to learn how to convert latitude/longitude to (x,y,z)). Now, the cross product of A and B is a vector that is perpendicular to the plane that contains G. Normalize that vector and call it N. Now there are several ways to compute your distance, but I would probably do it like this:

distance(C,G) = R * (pi/2 - acos(dot(N,C)/R))

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Quote:
How do I calculate Cross(A,B)?
Are you asking what the function Cross() represents in this context? Or are you asking how to compute the cross product of two vectors?


To tell you the truth I am not sure.
Dave suggested that I use, N = Cross(A,B)/Length(Cross(A,B)).

But I am not even sure how I would use it to solve my problem.

I was just hoping that there was a formula that would give me the shortest distance from a point(Lat/Lon) to a great circle line.

I have been using many formulas, (to get enroute points, true course, distance and so on), so I was hoping that there would be the same kind of formula to calculate the distance from a point to a line.

FFMG

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
On a sphere of radius R you have two points A and B that determine a great circle G, and a point C. You wish to compute the distance from C to G.


Well, I wish to compute the shortest possible distance to G if that's what you mean.

Quote:

Look at the points as vectors of length R in 3 dimensions (Google for spherical coordinates to learn how to convert latitude/longitude to (x,y,z)). Now, the cross product of A and B is a vector that is perpendicular to the plane that contains G. Normalize that vector and call it N. Now there are several ways to compute your distance, but I would probably do it like this:

distance(C,G) = R * (pi/2 - acos(dot(N,C)/R))


I think I understand. But I would still need to calculate R. is that right?
I know the radius of the earth, (give or take).

Would that equation be accurate enough anywhere in the world?
Or, as I mentioned in my first post, would it not be faster to compute the distance in a 2D world, (using A(Lat/Lon),B(Lat/Lon) and the point P(Lat,Lon))?

Many thanks

FFMG

Share this post


Link to post
Share on other sites
Quote:
Original post by FFMG
Quote:
Original post by alvaro
On a sphere of radius R you have two points A and B that determine a great circle G, and a point C. You wish to compute the distance from C to G.


Well, I wish to compute the shortest possible distance to G if that's what you mean.

Yes, that's what "distance" means.

Quote:

I think I understand. But I would still need to calculate R. is that right?
I know the radius of the earth, (give or take).

Well, then you don't need to calculate R: You know it.

Quote:
Would that equation be accurate enough anywhere in the world?

In a spherical world, yes. Note that all the operations I did are intrinsic (i.e., they don't depend on the exact coordinate system you use). That way you know that nothing funny happens around the poles or anywhere else, since all the points in the sphere are equivalent.

If you want to take into account the eccentricity or the Earth, things get a lot more complicated (be prepared to deal with elliptical integrals).

Quote:
Or, as I mentioned in my first post, would it not be faster to compute the distance in a 2D world, (using A(Lat/Lon),B(Lat/Lon) and the point P(Lat,Lon))?

No, that will have all sort of problems near the poles, where spherical coordinates become singular.

Also, why do you care about "faster"? Believe me, you want "simpler" or "more correct", but not "faster".


Share this post


Link to post
Share on other sites
Let the sphere be centered at the origin and have radius r. Let the arc have endpoints A and B, both vectors of length r. Let P be the point for which you want to know the closest point K on the great circle through A and B. Note that P and K also have length r.

The great circle is the intersection of the sphere and the plane Dot(N,X) = 0. The unit-length normal is N = Cross(A,B)/Length(Cross(A,B)). By Cross(A,B), I mean the cross product of the two vectors A and B. I divided by the length to make N a unit-length vector.

The closest point is K = r*(P - Dot(P,N)*N)/Length(P - Dot(P,N)*N). The point P - Dot(P,N)*N is the projection of P onto the plane Dot(N,X) = 0. The division by length makes a unit-length vector. Then I scaled by the radius r.

Share this post


Link to post
Share on other sites
What if P is already a unit vector? Could the equation be simplified to

K = r*(P - Dot(P,N)*N)

? Basically the same formula but without the denominator?



I'm going with NO on this one, but I use [color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif][size=3][background=rgb(250, 251, 252)]r*(p - Dot(p,N)*N)/Length(p - Dot(p,N)*N) with p being the unit-length vector of P, as the r in P should cancel each other in the nominator and denominator) but It should be nice if anybody can confirm this approach.[/background][/size][/font][/color] Edited by oschrenk

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this