2

I have a point A and trying to find the nearest point to A in a list of points (B, C, D).

I could use knn with haversine metrics and get the nearest point like this:

knn = NearestNeighbors(n_neighbors=1, metric='haversine')

knn.fit(df['lat', 'lon']) 

dist, idx = knn.kneighbors([(35.9157825, -79.0826045)])

However, I'm not sure if this point df.loc[idx] will always be the same point i'd get if I calculate distance using geodesic?

knn is very fast compared to having to calculate geodesic distance for all the points in my list. So I would love to use knn if the nearest point would always be the same.

  • It should only be different if the geodesic function is pulling from a specified datum... though I am not an expert in this. – mikeLdub Jan 31 at 21:14
  • 2
    "Always" seems like an impossibly high bar; surely you can design a test case where this fails. Whether this test case is significant with your data is a different question. – Vince Jan 31 at 21:23
3

For sure, "closest" will return different points, in general, for great-circle (what you call haversine) and geodesic distances. For a specific example, consider the set of points {A, B} where the positions (lat, lon) are: A = (10.03°, 0°); B = (0°, 10°). The point P = (0°, 0°) is closest to B according to the great-circle distance, but is closest to A according to the geodesic distance (for the WGS84 ellipsoid).

GeographicLib (written by me) offers a NearestNeighbor class which implements a vantage-point tree, which is an efficient method of finding the nearest neighbor in any metric space. (Geodesic distance defines a metric space.) There's a python implementation of vantage-point trees available here.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.