[Resolved] mysql closest value

marque

Here's what I'm trying to do...

I have two tables, one is a survey of sites (not websites) with longitude and latitude cordinates [Survey Table]. The other is a database I retrieved from NGA; GNS with place names, longitudes and latitudes [Locations Table].

I'm trying to get the suburb name from the locations table by joining the cordinates, yet I have know idea where to begin on this.

Because it's a join I don't think I can retrieve the closest suburb to the longitude and latitude with a simple order statement.

Does anyone have a solution?

bubblocity

Hi marque,

Are your values always integers for longitude and latitude? Do you have a specified range for which you want to return results, i.e within 5 degree radius?

If both are true, this might(?) be a way to do this:

Create another table called range with 2 columns with values like this: populate it with every radius range combination: below shows 5 degree radius range:

longituderange latituderange
1 1
1 2
1 3
1 4
1 5
2 1
2 2
2 3
2 4
2 5
3 1
3 2
3 3
3 4
3 5
4 1
4 2
4 3
4 4
4 5
5 1
5 2
5 3
5 4
5 5

Here's my idea:

I'm thinking you can do a cartesian join with no where clause between your survey table and the range table (to get every combination of qualifying location)

Then do a join between the cartesian product against the location table to get a match.

Then you can do a ORDER BY on your results.

Here is the final query that I used, it is sligtly rearrange from how it is described above, but it seem to give the right results.

SELECT locations.longitude, locations.latitude, locations.place,
survey.longitude AS survey_longitude, survey.latitude AS survey_latitude
FROM survey, range, locations
WHERE
longituderange=abs(survey.longitude-locations.longitude) And latituderange=abs(survey.latitude-locations.latitude)

ORDER BY survey.longitude, survey.latitude,
abs(survey.longitude-locations.longitude), abs(survey.latitude-locations.latitude)

If you want to send me an email to bubblocity@yahoo.com, I'll send you the ACCESS database where I tested this.

If you have a different solution, do you mind posting it, I'm very curious about this...

Thanks.

Roger_Ramjet

Latitude and Longditude are angles measured in degrees:minutes:seconds. It may well be that yours are only defined to a precision in Minutes. There are 60 minutes in a degree, and 60 seconds in a minute.

Longditude is also either East or West of Greenwich meridian 0-180 E or W
Latitude is North or South of the Equator 0-90 N or S.
If yours are all in North America then they will be all be West and North.

The shortest distance between two point on the Earth's surface is the arc of the Great Circle that passes through the two points. It is straightforward trigonometry to calculate this distance and the vector or direction from one to the other. MySQL has the spatial extensions that you will need to use for this (which I did not know before). Essentially you will be creating a GIS. My first plan would be to search for an existing one on SourceForge.

Good luck.

Roger_Ramjet

And as soon as I posted the above I saw this thread about GIS and Maps. Apparently there is a GIS mapping extension in PEAR. Whether you could adapt it to your needs I don't know.

AstroTeg

Some ideas here: http://www.rsbauer.com/webdev.php (scroll to the bottom of the page)

You can use lat/long values and calculate the distance between your target location and the list of suburbs you have. Do a sort on the list and pick the one with the shortest distance. The link above has some SQL code you could use or if you're gutsy and need/want speed, go for the C code.

AstroTeg

Originally posted by Roger Ramjet
And as soon as I posted the above I saw this thread about GIS and Maps. Apparently there is a GIS mapping extension in PEAR. Whether you could adapt it to your needs I don't know.

Sorry, that GIS package is for drawing maps from GIS data found in .E00 files (ArcView). I think Marque is looking to solve a simple distance problem...

marque

Thanks for all your help,

The page http://www.rsbauer.com/webdev.php looks like the best solution.

The only problem is there are 66,259 rows in the locations database. Matching up the closest location to 200+ sites could take a while.

Roger_Ramjet

Yep, that's some query he's written there. Sure it will take a while to run, but it's a one-off if you store the results isn't it. Are you going to try the C++ function?

marque

Ok, I'll put that down as the most complicated statement I've ever done. Too bad I can't take complete credit for it 😉

The solution:

First Statement:

SELECT survey.Latitude
       survey.Longitude
FROM survey

Second Statement within loop

SELECT locations.Name
       ((ACOS((SIN( ".$row['Latitude']." /57.2958) *
SIN( locations.Latitude /57.2958)) +
(COS( ".$row['Latitude']." /57.2958) *
COS( locations.Latitude /57.2958) * 
COS( locations.Longitude /57.2958 - 
".$row['Longitude']." /57.2958)))) * 
6378.7) AS Distance
FROM locations
ORDER BY Distance
LIMIT 1

Easy!

I found a discription of the calculation if anyone is interested http://www.meridianworlddata.com/Distance-Calculation.asp

Thanks everyone for your help. If you can think of a way to do this in a single statement please share.

My thought was to use 4.1+'s group concat and setting group_concat_max_len to 1 for the statement, yet that would still be two statements (I guess better than 200+)

Edited to remove the horozontal scroll bar

Roger_Ramjet

Well, no. Not if you want an accurate distance calculation, that is the formula that applies. However, last night I did think of a fudge that would work. If you converted all lats and longs to minutes, you would have integers to work with; eg
site
lat 40.25 = (4060)+25 = 2425
long 35.47 = (3560)+47 = 2147

zip
lat 39.52 = (3960)+52 = 2392
long = 37.02 = (3760)+2 = 2222

I am assuming that nearest zip will be close ie within a couple of degrees lat and long

fudge distance =
lat 2425-2392 = 33
long 2222-2147 = 75

fudge score = 33+75 = 108

the closest zip is the one with the lowest fudge score. This approximation does hold true for points that are close on the ground.

Of course you could use pythagorus' theorem to calculate a more accurate length for the fudge distance.

fudge score = square root of (3333)+(7575) = 81.94

Net result is still lowest fidge score wins

marque

Ok I don't get it, is the formula I used accurate? Does it return the correct distance between two points?

I checked on one site where the location is about 780 meters from the center point of the suburb, the result I got was 0.77740268913564. I would consider that to be pretty damn close 🙂

Although I think I see where your heading with your formula, my origional description was to find the closest suburb, not the distance. But since I have the distance thats a bonus.

By the way, I was getting extreamly strange results when i first tested. It turns out my data file of the locations is completely inaccurate.

I have the Australian file from http://earth-info.nga.mil/gns/html/cntry_files.html which out of wack by several hundred degrees.

Does anyone know where I can get a more reliable datafile? ga.gov.au has a very nice but expensive set.

Roger_Ramjet

Yes, my approach will give you the closest. It is an aproximation based upon the minutes of arc between the different latitudes and longditudes of two point, and the assumption that the arc of the great circle is directly proportional to them: which it is. It is just an abbreviation of the full furmula used in navigation to calculate the distance along the great arc between the two points.

The problem inherent in calculating real distance is because lines of longditude divide the earth up into segments like an orange. So the distance between 2 points 10 degrees apart in longditude varies with the distance from the equator.

For your initial problem: finding which is closest: I am just working from the angle between them. It is, as I said, an approximation that is only good for relativaly small distances. Once you take it beyond a few degrees of latitude and longditude then the distortions due to the way that latitude and longditude are differently defined will invalidate it.

Nope, don't know of any Aussie resorces to help. I'm surprised their figues are so inaccurate though.

marque

My application is only to short distances, within one city. So the origional calculation works fine. I will try use your formular though for the purpose of ordering.

Thanks for your help.

Roger_Ramjet

No point. My fudge was just that, a fudge to get a quick answer. If you are going to use the full formula to get an accurate distance then you can use that for ordering as well.

If 2 points are nearly the same distance from a site then my fudge will not discriminate very well and could easily get them in the wrong order. If you were to plot a line with of the equal values my fudge can produce it would not be a circle it would be egg shaped and the further away from the equator you got the more eggy it would get. Even at the equator it would produce an elipse, and the greater the distance involved the more flattened the elipse would be.

I hope you do try it though just to see how well it performs, and how fast its accuracy deteriorates with distance from the site. I'm sure that you could use it for a fast first pass to reduce the candidates for the full formula.

jeanne

hi there,

You might want to try get the information at http://www.geodatasource.com . It provides Latitude/Longitude, as well as distance calculation.

Reene