
Author 
Message 
dgrafx Corporal
Joined: 01 Jan 2004 Posts: 13

Posted: Wed Jan 07, 2004 5:44 pm Post subject: Determine Latitude Longitude Direction 



Does anyone know of a formula to determine direction(N E S W) from one lat/lon point to another?
Thanks,
DM 

Back to top 


chris Dark Lord of the Sith
Joined: 10 May 2003 Posts: 6267 Location: Outer Space

Posted: Wed Jan 07, 2004 8:35 pm Post subject: 



The direction is the direction of the tangent vector to the shortest curve on earth's surface (a sphere) connecting the two points.
Such a curve is called a geodesic.
Read this: Euler showed that the geodesics on a sphere are arcs of great circles.
Therefore, what you are looking for, is the great circle connecting the two points on the sphere.
Then, compute its tangent vector  it will show in the direction you want to compute. _________________ Regards
Chris Karakas
www.karakasonline.de 

Back to top 


chris Dark Lord of the Sith
Joined: 10 May 2003 Posts: 6267 Location: Outer Space

Posted: Wed Jan 07, 2004 8:53 pm Post subject: 



The following are the mathematical formulas for calculating great circle distance and bearing:
Distance:
Where: D = Distance (in Nautical Miles) L1 = Original Latitude, L2 = Destination Latitude, lamda1 = Origin Longitude, lamda2 = Destination Longitude Latitude.
Direction:
Where: C = Initial Bearing (in degrees) D = Distance L1 = Original Latitude, L2 = Destination Latitude.
Example:
The distance and initial bearing from New York JFK, N 40° 38' 24" W 74° 46' 42" and London LHR, N 51° 28' 39" W 00° 27' 41" are:
See Distance and Direction (scroll down to the bottom of that page to see it). _________________ Regards
Chris Karakas
www.karakasonline.de 

Back to top 


dgrafx Corporal
Joined: 01 Jan 2004 Posts: 13

Posted: Wed Jan 07, 2004 11:02 pm Post subject: 



Thanks Chris,
Is this correct?
c=cos((sin(lat1)*sin(lat2)+cos(distance/60)/sin(distance/60)*cos(lat1)))
what is the 1 behind the cos? if significant, how do I calculate?
and the result I get, how would I translate to a general N S E W thing?
I've never studied any advanced math. I'm just an idiot web developer.
thanks,
DM 

Back to top 


chris Dark Lord of the Sith
Joined: 10 May 2003 Posts: 6267 Location: Outer Space

Posted: Thu Jan 08, 2004 12:45 am Post subject: 



That 1 means "inverse", in our case: Inverse Cosine. Also known as acos, or arccos or Arcus Cosinus. In simple words: the arc (angle) that has that cosine as its cosine.
acos(x) is the "arc that has cosine x". Or, in mathematical words, cos(acos(x))=x.
Thus, you should read the above formula as
C = ACOS[....]
and NOT as
C = COS[....]
as you did. Just compute the example and, if you get the same result, then you know you are on the right way.
You get an angle in degrees as the result. I guess this will be the angle with a parallel cirle (the hoizontal lines in a map), from which you can derive the direction by a discretization in 45 degree intervalls: from 0 to 45 degrees, it is West to NorthWest, from 45 to 90, it is NW to North etc.
Are you programming an online navigation system? _________________ Regards
Chris Karakas
www.karakasonline.de 

Back to top 


dgrafx Corporal
Joined: 01 Jan 2004 Posts: 13

Posted: Thu Jan 08, 2004 3:16 am Post subject: 



Hi,
Nothing so exotic as an online navigation system. I was subcontracted to provide a dealer locator addin that would be incorporated into a site that the contractor was updating for their client. I said 'no problem' thinking to myself that I just needed to package a couple blocks of code taken from one of my other applications, but I fell into a big pit  called microsoft access... it doesn't understand ACOS. The app needed to pick the 3 closest dealers to a users zip code. I could have looped through all the dealers and had the application calculate ACOS without involving access but then I'd have to order them myself. I probably could've devised a decent method of ordering by distance, but as soon as I started thinking about it it upset me enough to try to dig up a way to calculate acos within the query. I don't know enough about advanced math nor do I really have the time to learn. I've requested the contractor convince the client to upgrade to MySql for not just this reason but its just a better database + its free. If they don't upgrade I'll just loop through each dealer and devise a method of picking & ordering the closest 3. (personaly I prefer ms SqlServer). Anyway... Some of the inquires here have been just for personal curiosity. The calculations on the globe are kinda interesting. And my interest in specifying direction is that I want to incorporate it into a distance calculator for another app I've written.
I'm having difficulties with the direction calc. Sometimes I get an error: Parameter 1 of function ACos which is now "1.05606309323" must be a real number between 1 and 1. So I'm wondering if it has to do with unit of measurement. I'm using miles for distance. Heres the Sql:
Select
3959 * ACOS(sin(zipcodes.latitude/57.3) * sin(dealers.latitude/57.3) +
cos(zipcodes.latitude/57.3) * cos(dealers.latitude/57.3) *
cos(dealers.longitude/57.3  zipcodes.longitude/57.3)) AS Distance
Are these figures compatible with your formula? Did I miss something?
Thanks  DM 

Back to top 


chris Dark Lord of the Sith
Joined: 10 May 2003 Posts: 6267 Location: Outer Space

Posted: Thu Jan 08, 2004 10:32 am Post subject: 



O.K., there are two questions there, let me pick one:
Quote:  The app needed to pick the 3 closest dealers to a users zip code.

That's the famous Nearest Neighbour Problem!
Why didn't you tell me before? You don't solve this problem with calculations or arccos!
Whole books can be written on this problem alone. Look at the books mentioned in the link above. The second one is even completely online! Here it is:
Skiena, S. S. "Nearest Neighbor Search." §8.6.5 in The Algorithm Design Manual. New York: SpringerVerlag, pp. 361363, 1997.
Get this book and read it  covertocover! Or stop developing such applications!
Why?
Because to compute the nearest neighbour (or the 3 nearest neighbours) to a point, you construct the Voronoi diagram (or the 3rd order Voronoi diagram) of all points, then look for the "cell" your point is in. By doing point location on this structure, the k nearest neighbors (out of n points) to a query point can be found in O(k + log(n)).
Uups...Voronoi diagram...what is this?
Exactly  that's why I say "read that book". For example the section on Voronoi diagrams.
Your mobile phone does the same, by the way: to find the antenna that is closest to the mobile phone, the Voronoi diagram of all antennas is computed. Then, the whole region is divided in "cells" by this diagram. Whenever you cross the cells, your mobile is internally changing the field for its "nearest neighbour" antenna.
Don't tell me you don't have the time to learn that stuff. You must. Otherwise, you will still be trying to reinvent the wheel for the 39th time. _________________ Regards
Chris Karakas
www.karakasonline.de 

Back to top 


chris Dark Lord of the Sith
Joined: 10 May 2003 Posts: 6267 Location: Outer Space


Back to top 


dgrafx Corporal
Joined: 01 Jan 2004 Posts: 13

Posted: Thu Jan 08, 2004 3:45 pm Post subject: 



You're such a math geek Chris. I've never known one before. That's cool, I'm a code geek.
I'm just starting in on the info you recomended. But just FYI, the client has about 50 dealers spread throughout the US and Canada. Even though I can understand what you're saying, from an advanced trig point of view  this is not accurate, still wouldn't such a formula be 'good enough' to pull up the 3 closet dealers by comparing distance on each one? The demo data so far seems accurate (enough anyway). Also I used similar methodology in a job search app giving the user the ability to seach only with a certain distance of their zipcode. That was also good enough.
I'll do some reading.
Thanks, 

Back to top 


chris Dark Lord of the Sith
Joined: 10 May 2003 Posts: 6267 Location: Outer Space

Posted: Thu Jan 08, 2004 9:42 pm Post subject: 



As you will read in Nearest Neighbour Search, for only a few points (say 50), it may be fastest to do an exhaustive comparison of distances. However, since dealer offices don't change that fast (or do they?), you could just as well compute their Voronoi diagram once, then use it each time a nearest neighbour er... dealer query comes up. Of course, you will have to recompute it each time a dealer's position changes, or one is deleted or inserted. It all depends  for 50 dealers, Voronoi might be overkill, but for 5000 it will not.
You might check that Ranger software the book talks about in the link above. Didn't try it. But I would be interested in a report from a code geek on how it can be used in a situation like this (perhaps you can even use some of its code??). _________________ Regards
Chris Karakas
www.karakasonline.de 

Back to top 




