Finding the closest coordinates to a point

Question

I have coordinates of city: (52.2319581, 21.0067249) and Python dictionary with cities around mentioned city. How to get 3 closest cities from given coordinates:

({'Brwinów': (52.133333, 20.716667), 'Warszawa Bielany': (52.283333, 20.966667), 'Legionowo': (52.4, 20.966667), 'Warszawa-Okęcie': (52.16039, 20.961674), 'Warszawa': (52.280957, 20.961348), 'Belsk Duży': (51.833333, 20.8)}, {})

Thanks for help.

Check this out. https://stackoverflow.com/questions/29481485/creating-a-distance-matrix/45834105 — Farhood ET, Apr 19 '20 at 12:23
This uses external libraries, while it doesn't seem that's what OP wants — RMPR, Apr 19 '20 at 12:25
@FarhoodET I dont need matrix, just 3 closest cities to given coordinates. — Bartol, Apr 19 '20 at 12:27
@Bartol well create the matrix and then get the top 3 for each city in that matrix. You have to create the matrix anyway. — Farhood ET, Apr 19 '20 at 12:28
Everybody is recommending Euclidean distance for what are clearly spherical coordinates, which is very wrong when you're not close to the equator. Look at [great-circle distance](https://en.wikipedia.org/wiki/Great-circle_distance) instead! Or, more likely, these are not even spherical coordinates but WGS84, which uses a spheroid, but that distinction is unlikely to matter if an entire city can be treated as a point. — Thomas, Apr 19 '20 at 12:44
@Błotosmętek That would be me, see my comment right above yours. Sorry that I made it a bit hard to find. (Edit: copied to individual posts now.) — Thomas, Apr 19 '20 at 12:51
@Thomas you probably haven't noticed, but all towns listed by the OP are close to Warsaw (in a 100km range); at those distances euclidean distance is a good enough approximation. — Błotosmętek, Apr 19 '20 at 12:51
@Błotosmętek Not at 52 degrees latitude it isn't. At that latitude, 1 degree of longitude represents about half as much distance as 1 degree of latitude. — Thomas, Apr 19 '20 at 12:52
@yatu Imagine you're 10 meters from the north pole. With a single step, you can now cross many degrees of longitude, but you need to take very many steps due south to cross one degree of latitude. In other words, at high latitudes, the lines of equal longitude are much closer together. — Thomas, Apr 19 '20 at 12:56
@yatu I updated my answer with some hard numbers to show how much this matters even in Poland. — Thomas, Apr 19 '20 at 13:04
Thanks for the details. That makes it very clear that we need spherical coordinates for this @thomas — yatu, Apr 19 '20 at 13:07

RMPR · Accepted Answer · 2020-04-19T17:19:58.917

Without any external libraries

from math import acos, cos, sin

def gc_distance(first_point, second_point):
    return acos(sin(first_point[1]) * sin(second_point[1]) + cos(first_point[1]) * cos(second_point[1]) * cos(first_point[0] - second_point[0]))

def three_closest(city, cities):
    cities_distances = { key: gc_distance(city, value) for key, value in cities.items()}
    return [k for k, v in sorted(cities_distances.items(), key=lambda item: item[1])][:3]

Sample test:

>>> city = (52.2319581, 21.0067249)
>>> cities = {'Brwinów': (52.133333, 20.716667), 'Warszawa Bielany': (52.283333, 20.966667), 'Legionowo': (52.4, 20.966667), 'Warszawa-Okęcie': (52.16039, 20.961674), 'Warszawa': (52.280957, 20.961348), 'Belsk Duży': (51.833333, 20.8)}
>>> three_closest(city, cities)
['Warszawa Bielany', 'Warszawa', 'Warszawa-Okęcie']

If you want to return keys and values instead:

for result in three_closest(city, cities):
    print(result + " : " + str(cities[result]))

To get:

Warszawa Bielany : (52.283333, 20.966667)
Warszawa : (52.280957, 20.961348)
Warszawa-Okęcie : (52.16039, 20.961674)

@RMPR i've posted this which i felt would also help you https://meta.stackexchange.com/questions/346726/let-new-comers-know-what-they-should-know — Joshua Varghese, Apr 20 '20 at 04:32

Thomas · Answer 2 · 2020-04-19T13:03:06.150

Everybody is recommending Euclidean distance for what are clearly spherical coordinates, which is very wrong when you're not close to the equator. In the example coordinates (Poland), around 52° latitude:
1° of latitude is still about 10000 km / 90° = 111 km, but
1° of longitude is only 10000 km * cos(52°) / 90° = 68 km.
So at the very least we have to use great-circle distance instead!

from math import sin, cos, acos

def angle(c1, 2):
  l1, p1 = c1
  l2, p2 = c2
  return acos(sin(p1) * sin(p2) + cos(p1) * cos(p2) * cos(l2 - l1))

sorted_coords = sorted(coords, key=lambda city: angle(city, center))
print(sorted_coords[:3])

More likely, these are not even spherical coordinates but WGS84, which uses a spheroid, but that distinction is unlikely to matter if an entire city can be treated as a point.

score -2 · Answer 3 · answered Apr 19 '20 at 12:35

Maybe this would work (this doesn't take into account the fact that one degree of longitude mean different distance at different latitudes).

the_city = (52.2319581, 21.0067249)
cities = ({'Brwinów': (52.133333, 20.716667), 'Warszawa Bielany': (52.283333, 20.966667), 'Legionowo': (52.4, 20.966667), 'Warszawa-Okęcie': (52.16039, 20.961674), 'Warszawa': (52.280957, 20.961348), 'Belsk Duży': (51.833333, 20.8)}, {})

closest3 = sorted(cities[0], key=lambda k: (cities[0][k][0]-the_city[0])**2 + (cities[0][k][1]-the_city[1])**2)[:3]

This does not work for spherical coordinates in general. It only works as an approximation if the points are not too far apart, do not straddle the cutover from -180 to 180 degrees longitude, and are close to the equator (unlike Poland). — Thomas, Apr 19 '20 at 12:53

Finding the closest coordinates to a point

3 Answers3

Linked