1. Best way to...
- Posted by irv Oct 17, 2010
- 1937 views
I have a list of world airports, about 25,000. The list looks like this:
KLAX|-118.408074361323|33.9425346884195 KLBB|-101.822795013889|33.6636445206324 KLBE|-79.4047956708861|40.2759411160023 KLBF|-100.683662721014|41.1262132608696 KLBL|-100.959853220239|37.0442112733297 KLBO|-92.6537609065369|37.6472052018638 ...etc.
I know my current location from my gps. So, what is an efficient way to find the 3 closest airports to my current location? Extra points for using Euphoria 4.0 routines :)
2. Re: Best way to...
- Posted by petelomax Oct 17, 2010
- 1826 views
I'd create two copies of the list, one sorted on x and the other on y. Then use a binary chop to locate the three closest in the x-axis and the three closest in the y-axis.
Regards, Pete
3. Re: Best way to...
- Posted by irv Oct 17, 2010
- 1793 views
Might be a bit more to it than that: for example, Montreal and Venice, IT are at almost the same latitude, but nowhere near close to each other in longitude.
So it could well turn out that the 3 closest (or the n closest) in one coordinate might not have any overlap with the 3 (or n) closest in the other coordinate.
How big is n?
The formula for computing distance between 2 points:
d=2*asin(sqrt((sin((lat1-lat2)/2))^2 + cos(lat1)*cos(lat2)*(sin((lon1-lon2)/2))^2))
I could compute all 25k distances, but perhaps there's an easier way? Hashing lat/lon perhaps?
4. Re: Best way to...
- Posted by mattlewis (admin) Oct 17, 2010
- 1869 views
I have a list of world airports, about 25,000. The list looks like this:
KLAX|-118.408074361323|33.9425346884195 KLBB|-101.822795013889|33.6636445206324 KLBE|-79.4047956708861|40.2759411160023 KLBF|-100.683662721014|41.1262132608696 KLBL|-100.959853220239|37.0442112733297 KLBO|-92.6537609065369|37.6472052018638 ...etc.
I know my current location from my gps. So, what is an efficient way to find the 3 closest airports to my current location? Extra points for using Euphoria 4.0 routines :)
There was a question on StackOverflow asking about this (not for euphoria, of course).
Geohashing looks like a way to attack it.
Matt
5. Re: Best way to...
- Posted by petelomax Oct 17, 2010
- 1788 views
So it could well turn out that the 3 closest in one coordinate might not have any overlap with the 3 closest in the other coordinate.
Stupid me, scratch that idea. I was thinking the best three of each would do it, just like Roger on Matt's stackoverflow link, which was shot down rather smartly (in a nice way).
6. Re: Best way to...
- Posted by ArthurCrump Oct 17, 2010
- 1791 views
Firstly:
At some point the strings should be split up into a name, Easting, Northing. For example:
{"KLAX",-118.408074361323,33.9425346884195}
The best time to do this is before any comparison so that it is only done once on each string.
Secondly:
Convert each location into a cartesian coordinate system.
Using N for the Northing, in degrees, and E for the Easting, also in degrees:
sequence XYZ[location_number] = R * { cos(N)*cos(E), cos(N)*sin(E), sin(N) }
R should be the radius of the Earth. However, it is irrelevant when distances are only being compared, so leave it out.
Thirdly:
There is no need to calculate the surface distance between locations. The straight line between them is sufficent for finding the nearest. To find this chord:
Find the difference between the cartesian coordinates:
XYZdif = XYZ[1] - XYZ[2]
Don't worry about the sign, because the three elements XYZdif are now going to be squared and added together. The chord length is:
chord = sqrt( XYZdif[1]*XYZdif[1]+XYZdif[2]*XYZdif[2]+XYZdif[3]*XYZdif[3] )
Just find the shortest chord length.
The sqrt is not important, you might just as well compare the square of the chord length.
7. Re: Best way to...
- Posted by CoJaBo Oct 17, 2010
- 1743 views
Best way to write an ellipses? I'd say like this: …
8. Re: Best way to...
- Posted by irv Oct 17, 2010
- 1740 views
Well, if you know how to phrase the question so it will fit on the subject line, please don't keep us in suspense.
Thanks for the suggestions. The following code, copied from a javascript version, works and gives a reasonably accurate distance, as well. This takes slightly more than 1 second on my computer, which is acceptable.
include std/math.e include std/sequence.e include std/get.e include std/io.e include std/sort.e constant R = 6371 -- km Radius of earth enum ID,LON,LAT,KM atom lat1, lat2, lon1, lon2, dLat, dLon, a, c, km, nm, sm -- current location (KLAX) lat1 = 33.9425346884195 lon1 = -118.408074361323 sequence airports = read_lines("index.txt") for i = 1 to length(airports) do airports[i] &= "|0" -- place to store distance in km airports[i] = split(airports[i],'|') lat2 = defaulted_value(airports[i][LAT],0) lon2 = defaulted_value(airports[i][LON],0) dLat = deg2rad(lat2-lat1) dLon = deg2rad(lon2-lon1) a = sin(dLat/2) * sin(dLat/2) + cos(deg2rad(lat1)) * cos(deg2rad(lat2)) * sin(dLon/2) * sin(dLon/2) c = 2 * atan2(sqrt(a), sqrt(1-a)) km = R * c --nm = km * 0.5399568034557235 --sm = km * 0.621371192237334 airports[i][KM] = km end for airports = sort_columns(airports,{KM}) for i = 1 to 3 do printf(1,"%s %.2f km\n",{airports[i][ID],airports[i][KM]}) end for
9. Re: Best way to...
- Posted by Spock Oct 17, 2010
- 1776 views
Thanks for the suggestions. The following code, copied from a javascript version, works and gives a reasonably accurate distance, as well. This takes slightly more than 1 second on my computer, which is acceptable.
SNIP
Hi Irv,
Your code has several math identities to exploit for faster execution, as we all know. Another speed-up could be to sort the 3 shortest distances inside the main loop, eg:
atom km, a, b, c -- a, b, c get initialized with some ridiculous default value before entering the main loop -- at the end of the loop perform this optimized sort if km < c then if km < b then if km < a then c=b b=a a=km else c=b b=km end if else c=km end if end if
More code infrastructure is required but this shows the idea.
Spock
10. Re: Best way to...
- Posted by ArthurCrump Oct 19, 2010
- 1690 views
I should get out of the habit of doing things in too much of a hurry.
In my previous reply, I forgot that sin and cos want radians, not degrees.
Here is a function that takes the list of airports and a current location as degrees East and North. It seemed to get the distance from San Francisco to Los Angeles airport about right. It uses Euphoria version 4.
include std/sequence.e include std/math.e include std/convert.e constant EarthRadius = 3963 -- Approximate miles, or 6378 Kilometres -- Parameters of 'nearest': -- site_list: The list of airports, in the original form, {"KLAX|-118.4etc|33.94etc",...} -- E: The Easting of the current location, ie degrees longitude East. -- N: The Northing of the current location, ie degrees latitude North. public function nearest(sequence site_list, atom E, atom N ) sequence bestsite, this, XYZhere, XYZsite atom bestcp2, ChordSquared integer bestindex N = deg2rad(N) E = deg2rad(E) XYZhere = { cos(N)*cos(E), cos(N)*sin(E), sin(N) } bestcp2 = 9.9 -- The actual range is 0.0 to 2.0 for n = 1 to length(site_list) do -- First convert "name|degrees|degrees" to {"name",radians, radians} this = split(site_list[n],'|') this[2] = deg2rad(to_number(this[2])) this[3] = deg2rad(to_number(this[3])) -- It would be more efficient if site_list entries were already in this form. XYZsite = { cos(this[3])*cos(this[2]), cos(this[3])*sin(this[2]), sin(this[3]) } ChordSquared = sum(power(XYZsite-XYZhere,2)) if ChordSquared < bestcp2 then bestcp2 = ChordSquared bestsite = this end if end for return bestsite & 2*arcsin(sqrt(bestcp2)/2)*EarthRadius & sqrt(bestcp2) end function -- The function returns a sequence of 4 elements for the nearest airport: -- {Name, Easting, Northing, Surface_distance} -- Currently in miles. -- To take account of polar flattening, the Z coordinate should be multiplied by -- 0.99665. The chord lengths and the nearest airport would be correct, but the -- surface distance would be more difficult to work out from the chord length.
Arthur
11. Re: Best way to...
- Posted by jeremy (admin) Oct 23, 2010
- 1610 views
Just out of curiosity, what project are you working on that this is a part of? Airports, GPS coordinates, Euphoria... sounds like fun!
Jeremy
12. Re: Best way to...
- Posted by irv Oct 23, 2010
- 1594 views
Just out of curiosity, what project are you working on that this is a part of? Airports, GPS coordinates, Euphoria... sounds like fun!
Jeremy
Add-on utilities for FlightGear - the open source flight simulator. There are only a few, and those are mostly for Windows. FlightGear runs better on Linux, so I want to create some for that platform.
13. Re: Best way to...
- Posted by jeremy (admin) Oct 23, 2010
- 1660 views
Just out of curiosity, what project are you working on that this is a part of? Airports, GPS coordinates, Euphoria... sounds like fun!
Jeremy
Add-on utilities for FlightGear - the open source flight simulator. There are only a few, and those are mostly for Windows. FlightGear runs better on Linux, so I want to create some for that platform.
Irv, are you a pilot or just enjoy FlightGear?
Jeremy
14. Re: Best way to...
- Posted by irv Oct 23, 2010
- 1578 views
Used to fly some, out west, but my eyesight isn't *quite* good enough to keep from running into other aircraft. That sort of puts a damper on doing the real thing, you know. (besides, FlightGear is a lot cheaper)