Wessi Wessi - 2 months ago 10
SQL Question

SQL: Finding closest neighbor based on lat/lon

I have a table containing the lat/lon of cafés. I would like to make an SQL query that gives me the closest café to each café. Can someone help with advice on how to do this?

The table basically looks like this:

Cafe ID

+-------------------------+----------------------+----------------------+
| cafe_id | gps_latitude | gps_longitude |
+-------------------------+----------------------+----------------------+
| 011-1003 | 55.86649500000000000 | 8.16856200000000000 |
| 192-143 | 57.04419159749860000 | 10.36447024359820000 |
| 037-0233 | 55.08773849210000000 | 8.56101036070000000 |
| 121-934 | 56.89120900000000000 | 9.16818100000000000 |
+-------------------------+----------------------+----------------------+


Any help is much appreciated!

Answer

You could use the Spherical Law of Cosines to get the distance expressed in earth-radii.

Some prefer the Haversine formula because it gives better precision, but given that MySql's floating point precision is high enough, the difference between the two is negligible. The first one is simpler to implement:

select     c1.cafe_id,
           substring_index (
             group_concat( C2.cafe_id order by 
               acos(  sin(radians(c1.gps_latitude)) * sin(radians(c2.gps_latitude)) 
                    + cos(radians(c1.gps_latitude)) * cos(radians(c2.gps_latitude)) 
                      * cos(radians(c2.gps_longitude-c1.gps_longitude)) ) ),
             ',', 1) nearest
from       cafe c1
inner join cafe c2 on c1.cafe_id <> c2.cafe_id
group by   c1.cafe_id

Output for the sample data is:

|  cafe_id |  nearest |
|----------|----------|
| 011-1003 | 037-0233 |
| 037-0233 | 011-1003 |
| 121-934  | 192-143  |
| 192-143  | 121-934  |

Here is a MySql fiddle.

Explanation

The distance calculation is used in the order by clause of the group_concat aggregation function, which results in a comma-separated list of cafe_id values in order of their distance to the cafe you group by. The substring_index function extracts the first item from that list.

The join condition is important as without it you'd get the cafe itself as the closest neighbor (its distance is obviously 0 then).

Comments