OpenEuphoria

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

4. Re: Best way to...

• Posted by mattlewis (admin) Oct 17, 2010
• 1870 views

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. 

There was a question on StackOverflow asking about this (not for euphoria, of course).

Geohashing looks like a way to attack it.

Matt

6. Re: Best way to...

• Posted by ArthurCrump Oct 17, 2010
• 1792 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.

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 

10. Re: Best way to...

• Posted by ArthurCrump Oct 19, 2010
• 1691 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

12. Re: Best way to...

• Posted by irv Oct 23, 2010
• 1594 views

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.

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)