Python: как сгруппировать точки на заданном расстоянии?

Question

У меня есть dataframe, который содержит маршруты отправления по назначению пользователей между разными точками (широта/долгота). Таким образом, мы имеем Origin_X, Origin_Y и Destination_X, Destination_Y

df: 

Trip Origin_X Origin_Y Destination_X Destination_Y 
1 -33.55682 -70.78614 -33.44007  -70.6552 
2 -33.49097 -70.77741 -33.48908  -70.76263 
3 -33.37108 -70.6711 -33.73425  -70.76278 

Я хочу, чтобы сгруппировать вместе все Trip, что есть в радиусе 1km как в начале координат и назначения. Две поездки можно сгруппировать, если их расстояние до места назначения и их расстояние в пункте назначения - d<=1km. Чтобы вычислить расстояние между двумя координатами, я использую функцию haversine.

def haversine(lon1, lat1, lon2, lat2): 
    """ 
    Calculate the great circle distance between two points 
    on the earth (specified in decimal degrees) 
    """ 
    # convert decimal degrees to radians 
    lon1, lat1, lon2, lat2 = map(radians, [lon1, lat1, lon2, lat2]) 

    # haversine formula 
    dlon = lon2 - lon1 
    dlat = lat2 - lat1 
    a = sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2 
    c = 2 * asin(sqrt(a)) 
    r = 6371 # Radius of earth in kilometers. Use 3956 for miles 
    return c * r 

Answer 1

Вы можете перебирать каждую точку, вычислить расстояние до всех остальных точек, а затем проверить, если расстояние меньше или равно 1 км и добавить его в словарь, где ключ является исходная точка и значение массив всех близких точек ...

Answer 2

Вот как вы можете это сделать:

import pandas as pd 
from math import * 

def haversine(row): 
    """ 
    Calculate the great circle distance between two points 
    on the earth (specified in decimal degrees) 
    """ 
    # convert decimal degrees to radians 
    lon1 = row[1] 
    lat1 = row[2] 
    lon2 = row[3] 
    lat2 = row[4] 
    lon1, lat1, lon2, lat2 = map(radians, [lon1, lat1, lon2, lat2]) 

    # haversine formula 
    dlon = lon2 - lon1 
    dlat = lat2 - lat1 
    a = sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2 
    c = 2 * asin(sqrt(a)) 
    r = 6371 # Radius of earth in kilometers. Use 3956 for miles 
    return c * r 

#Copy the trip details provided by in this question 

df = pd.read_clipboard() 
df['dist'] = df.apply(haversine, axis=1) 

print df 

    Trip Origin_X Origin_Y Destination_X Destination_Y  dist 
0  1 -33.55682 -70.78614  -33.44007  -70.65520 15.177680 
1  2 -33.49097 -70.77741  -33.48908  -70.76263 1.644918 
2  3 -33.37108 -70.67110  -33.73425  -70.76278 16.785898 
#To group 
dfg = df.groupby(df['dist'] < 1) 

#Just to select all the trips that are less than 2 radius 
df[df['dist']<2] 
    Trip Origin_X Origin_Y Destination_X Destination_Y  dist 
1  2 -33.49097 -70.77741  -33.48908  -70.76263 1.644918