find closest object via latitude and longitude and haversine distance

Question

Given a pandas data frame containing objects with ids and latitudes and longitudes:

  id   latitude  longitude
0  a  52.617960   1.717728
1  b  51.773427  -4.455351
2  c  52.206543  -4.345786

I would like to find the closest object with a different id in the same data frame resulting in the following data:

  closest_id  closest_latitude  closest_longitude    distance id   latitude  longitude
0          c         52.206543          -4.345786  413.676582  a  52.617960   1.717728
1          c         52.206543          -4.345786   48.741132  b  51.773427  -4.455351
2          b         51.773427          -4.455351   48.741132  c  52.206543  -4.345786

My working (AFIK) but clumsy/rooky/non pythonic attempt can be found below. Any improvement suggestions would be very much welcome.

import pandas as pd
from math import radians, cos, sin, asin, sqrt

def dist(lat1, long1, lat2, long2):
    """
    Calculate the great circle distance between two points 
    on the earth (specified in decimal degrees)
    """
    # convert decimal degrees to radians 
    lat1, long1, lat2, long2 = map(radians, [lat1, long1, lat2, long2])
    # haversine formula 
    dlon = long2 - long1 
    dlat = lat2 - lat1 
    a = sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2
    c = 2 * asin(sqrt(a)) 
    # Radius of earth in kilometers is 6371
    km = 6371* c
    return km

test_data = {'id':['a','b','c'], 'latitude':[52.61796, 51.773427, 52.206543], 'longitude':[1.717728, -4.455351, -4.345786]}
haves = pd.DataFrame(test_data)

def find_nearest(lat, long, id, df):

    # guess very inefficient
    filter_data = df.copy()
    filter_data.drop(filter_data.index[filter_data['id'] == id], inplace = True)

    distances = filter_data.apply(lambda row: dist(lat, long, row['latitude'], row['longitude']), axis=1)

    #print(distances)
    dic = dict()
    dic['closest_id'] = filter_data.loc[distances.idxmin(), 'id']
    dic['closest_latitude'] = filter_data.loc[distances.idxmin(), 'latitude']
    dic['closest_longitude'] = filter_data.loc[distances.idxmin(), 'longitude']
    dic['distance'] = distances[distances.idxmin()]
    #print(dic)
    
    return dic

print(haves)

wants = pd.DataFrame()

for index, row in haves.iterrows():

    dic = find_nearest(row['latitude'], row['longitude'], row['id'], haves)
    dic['id'] = row['id']
    dic['latitude'] = row['latitude']
    dic['longitude'] = row['longitude']

    wants = wants.append(dic, ignore_index=True)

print(wants)

Answer 1

So, with regards to the code style (naming, spacing, etc.), the code is really not bad.

There's one small thing I'd like to say, when you use an algorithm or a pattern that has a specific name, use it. The function name dist doesn't tell us, users/readers of your code, that you're using the Haversine Distance.

There's nothing bad with using meaningful names, as a matter of fact it's much worst to have code with unclear variable/function names.

So, don't name your function dist, name it haversine_distance. This way, if someone wants to understand what's happening in your code, they'll be able to find it very fast by searching this on the web. You might tell me that you have a comment in your function that says " # haversine formula ", but comments shouldn't be used to describe what's happening it's a last resort.

Now, for the algorithm. It's not clear in your post what amount of data you have. If you have a hundred points, the way to find the closest distance to another point really isn't the same as if you have a billion rows.

If the amount of data you have is very small, your algorithm is most likely "ok".

Now, if you have lots of data, which is a more fun assumption, I think you're not using the full advantages of the libraries offered to you in Python.

What you want is to find, for each element E in the dataset D, another element E' in the same dataset D such as the distance between E and E' is smaller than every other distances for all elements of D except for E itself (because the distance between E and E is zero, duh).

The way to find information on such problems is to look at the nearest neighbors algorithms.

The exact implementation you'll used will vary depending on the amount of data. If you have under maybe 200000 rows, you could consider using the scikit-learn algorithm. Otherwise, Facebook released a Nearest Neighbors algorithm capable of dealing with billions of rows (assuming you have the hardware for it).

Say we use the scikit-learn one, mainly because I never used the other one. What's nice about this is we can specify the metric to use to compute the distances. You can use your implementation, or you could use the scipy one!

Starting with the haves dataframe (btw, what does this mean? Maybe that's a sign it should be named otherwise). This is only a draft of the code you should used, I don't guarantee it'll compile, but the idea is there :

from sklearn.neighbors import NearestNeighbors
from sklearn.metrics.pairwise import haversine_distances

# First, I'd split the numeric values from the identifiers.
identifiers = haves["id"]
coordinates = haves[['latitude', 'longitude']]

# Adapt the hyperparameters to your needs, you may need to fiddle a bit to find the best ones for your case.
# However, we picked n_neighbors=2 because the first nearest neighbor will always be the element itself.
nn = NearestNeighbors(n_neighbors=2, radius=1.0, algorithm='auto', leaf_size=30, metric=haversine_distances, n_jobs=None)

# Here we give our data to the algorithm. It'll create a data structure made specially to find nearest neighbors, which is pretty much garanteed to be faster than your code unless you have like <100 rows.
nn = nn.fit(coordinates.values)

# Here, we ask the algorithm to find the 2 closest neighbors for each row of the dataframe
distances, nearest_neighbors_row_ids = n.kneighbors(coordinates.values)

# Get the closest neighbor that isn't the row itself.
nearest_neighbors_row_ids = [x[1] for x in nearest_neighbors_row_ids]

#...

Then, all you need to do is regroup the data, but your code does it already and I think your code is alright.

So, I think my main take away from your code is that it's okay, but when you want to optimize your code, the first think you should do is look for an established algorithm that does the job. These algorithms have been written by pros and tested by thousands before you, so they'll work.