寻找两点之间的最短距离 Python
Finding the shortest distance between two points Python
我有两个数据框。一个包含 properties locations，另一个包含 railway stations locations.
属性数据框样本（原始数据框包含约 700 行）：
properties=pd.DataFrame({'propertyID':['13425','32535','43255','52521'],
'lat':[-37.79230,-37.86400,-37.85450,-37.71870],
'lon':[145.10290,145.09720,145.02190,144.94330]})
火车站数据框样本（原始数据框由~90行组成）：
stations=pd.DataFrame({'stationID':['11','33','21','34','22'],
'lat':[-37.416861,-37.703293,-37.729261,-37.777764,-37.579206],
'lon':[145.005372,144.572524,144.650631,144.772304,144.728165]})
我有一个函数可以计算两个位置之间的距离
from math import radians, cos, sin, asin, sqrt
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 = 6378 # Radius of earth in kilometers
return c * r
我想找出每个 属性 和所有车站之间的距离。然后再选择距离最短的车站。
我试图构造一个 for 循环，但它没有return最短距离（分钟）
lst=[]
for stopLat in stations['lat']:
for stopLon in stations['lon']:
for propLat in properties['lat']:
for propLon in properties['lon']:
lst.append(haversine(propLon,propLat,stopLon,stopLat))
我的最终输出应该是这样的。 （每个 属性 链接到最近的车站）。
stationID propertyID
11 52521
33 13425
21 32535
34 43255
有关如何处理此问题的任何建议都会有所帮助。谢谢
这是一种解决方法，但我首先将两个数据帧与一个额外的 'key' 合并。
然后我使用 apply 来计算距离：
properties['key'] = 1
stations['key'] = 1
df = properties.merge(stations,on='key')
del df['key']
df['distance'] = df.apply(lambda x: haversine(x['lon_x'],x['lat_x'],x['lon_y'],x['lat_y']),axis=1)
print(df)
df = df.loc[df.groupby("propertyID")["distance"].idxmin()]
df = df[['stationID','propertyID']]
print(df)
第一次打印：
propertyID lat_x lon_x stationID lat_y lon_y distance
0 13425 -37.7923 145.1029 11 -37.416861 145.005372 42.668639
1 13425 -37.7923 145.1029 33 -37.703293 144.572524 47.723406
2 13425 -37.7923 145.1029 21 -37.729261 144.650631 40.415507
3 13425 -37.7923 145.1029 34 -37.777764 144.772304 29.129338
4 13425 -37.7923 145.1029 22 -37.579206 144.728165 40.650436
5 32535 -37.8640 145.0972 11 -37.416861 145.005372 50.428078
6 32535 -37.8640 145.0972 33 -37.703293 144.572524 49.504807
7 32535 -37.8640 145.0972 21 -37.729261 144.650631 42.047056
8 32535 -37.8640 145.0972 34 -37.777764 144.772304 30.138684
9 32535 -37.8640 145.0972 22 -37.579206 144.728165 45.397047
10 43255 -37.8545 145.0219 11 -37.416861 145.005372 48.738487
11 43255 -37.8545 145.0219 33 -37.703293 144.572524 42.971083
12 43255 -37.8545 145.0219 21 -37.729261 144.650631 35.510616
13 43255 -37.8545 145.0219 34 -37.777764 144.772304 23.552690
14 43255 -37.8545 145.0219 22 -37.579206 144.728165 40.101407
15 52521 -37.7187 144.9433 11 -37.416861 145.005372 34.043280
16 52521 -37.7187 144.9433 33 -37.703293 144.572524 32.696875
17 52521 -37.7187 144.9433 21 -37.729261 144.650631 25.795774
18 52521 -37.7187 144.9433 34 -37.777764 144.772304 16.424364
19 52521 -37.7187 144.9433 22 -37.579206 144.728165 24.508280
第二次打印：
stationID propertyID
3 34 13425
8 34 32535
13 34 43255
18 34 52521
但根据这个输出站 34 总是最近的。对吗？
编辑：进一步解释：
我曾经试图找到一种方法来 "merge" 两个没有通常用于合并的唯一标识符的数据帧。
我还想将一个数据帧的每一行与另一个数据帧配对（在您的情况下，每个站与每个 属性）以便能够比较这些条目。
在我的研究中，我发现了使用虚拟密钥的巧妙解决方法。
合并通常基于唯一标识符合并数据框，但仅合并那些匹配的行。因此，数据框 A "ID" = 1 仅与数据框 B 中 "ID" = 1 的人匹配。（阅读此处：https://pandas.pydata.org/pandas-docs/version/0.19.1/generated/pandas.DataFrame.merge.html）
在使用的这个解决方法中，我们看到每一行的键都是 1，因此每一行都将与其他数据框中的每一行匹配，这正是我们想要的。
使用应用函数，您可以将任何函数逐行应用于数据框。
使用 BallTree from Sklearn 可以更快地找到最近的邻居
import numpy as np
import pandas as pd
from sklearn.neighbors import KDTree, BallTree
properties=pd.DataFrame({'propertyID':['13425','32535','43255','52521'],
'lat':[-37.79230,-37.86400,-37.85450,-37.71870],
'lon':[145.10290,145.09720,145.02190,144.94330]})
stations=pd.DataFrame({'stationID':['11','33','21','34','22'],
'lat':[-37.416861,-37.703293,-37.729261,-37.777764,-37.579206],
'lon':[145.005372,144.572524,144.650631,144.772304,144.728165]})
property_coords = properties.as_matrix(columns=['lat', 'lon'])
station_coords = stations.as_matrix(columns=['lat', 'lon'])
# Create BallTree using station coordinates and specify distance metric
tree = BallTree(station_coords, metric = 'haversine')
print('PropertyID StationID Distance')
for i, property in enumerate(property_coords):
dist, ind = tree.query(property.reshape(1, -1), k=1) # distance to first nearest station
print(properties['propertyID'][i], stations['stationID'][ind[0][0]], dist[0][0], sep ='\t')
输出
PropertyID StationID Distance
13425 34 0.329682946662
32535 34 0.333699645179
43255 34 0.259425428922
52521 34 0.180690281514
性能
总结--BallTree > 比合并数据帧的方法快 5 倍
详细信息（假设预加载库和数据）
方法一--使用BallTree
%%timeit
property_coords = properties.as_matrix(columns=['lat', 'lon'])
station_coords = stations.as_matrix(columns=['lat', 'lon'])
# Create BallTree using station coordinates and specify distance metric
tree = BallTree(station_coords, metric = 'haversine')
for i, property in enumerate(property_coords):
dist, ind = tree.query(property.reshape(1, -1), k=1) # distance to first nearest station
100 loops, best of 3: 1.79 ms per loop
方法 2--合并两个数据帧
%%timeit
properties['key'] = 1
stations['key'] = 1
df = properties.merge(stations,on='key')
del df['key']
df['distance'] = df.apply(lambda x: haversine(x['lon_x'],x['lat_x'],x['lon_y'],x['lat_y']),axis=1)
#print(df)
df = df.loc[df.groupby("propertyID")["distance"].idxmin()]
df = df[['stationID','propertyID']]
100 loops, best of 3: 10 ms per loop
我有两个数据框。一个包含 properties locations，另一个包含 railway stations locations.
属性数据框样本（原始数据框包含约 700 行）：
properties=pd.DataFrame({'propertyID':['13425','32535','43255','52521'],
'lat':[-37.79230,-37.86400,-37.85450,-37.71870],
'lon':[145.10290,145.09720,145.02190,144.94330]})
火车站数据框样本（原始数据框由~90行组成）：
stations=pd.DataFrame({'stationID':['11','33','21','34','22'],
'lat':[-37.416861,-37.703293,-37.729261,-37.777764,-37.579206],
'lon':[145.005372,144.572524,144.650631,144.772304,144.728165]})
我有一个函数可以计算两个位置之间的距离
from math import radians, cos, sin, asin, sqrt
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 = 6378 # Radius of earth in kilometers
return c * r
我想找出每个 属性 和所有车站之间的距离。然后再选择距离最短的车站。
我试图构造一个 for 循环，但它没有return最短距离（分钟）
lst=[]
for stopLat in stations['lat']:
for stopLon in stations['lon']:
for propLat in properties['lat']:
for propLon in properties['lon']:
lst.append(haversine(propLon,propLat,stopLon,stopLat))
我的最终输出应该是这样的。 （每个 属性 链接到最近的车站）。
stationID propertyID
11 52521
33 13425
21 32535
34 43255
有关如何处理此问题的任何建议都会有所帮助。谢谢
这是一种解决方法，但我首先将两个数据帧与一个额外的 'key' 合并。 然后我使用 apply 来计算距离：
properties['key'] = 1
stations['key'] = 1
df = properties.merge(stations,on='key')
del df['key']
df['distance'] = df.apply(lambda x: haversine(x['lon_x'],x['lat_x'],x['lon_y'],x['lat_y']),axis=1)
print(df)
df = df.loc[df.groupby("propertyID")["distance"].idxmin()]
df = df[['stationID','propertyID']]
print(df)
第一次打印：
propertyID lat_x lon_x stationID lat_y lon_y distance
0 13425 -37.7923 145.1029 11 -37.416861 145.005372 42.668639
1 13425 -37.7923 145.1029 33 -37.703293 144.572524 47.723406
2 13425 -37.7923 145.1029 21 -37.729261 144.650631 40.415507
3 13425 -37.7923 145.1029 34 -37.777764 144.772304 29.129338
4 13425 -37.7923 145.1029 22 -37.579206 144.728165 40.650436
5 32535 -37.8640 145.0972 11 -37.416861 145.005372 50.428078
6 32535 -37.8640 145.0972 33 -37.703293 144.572524 49.504807
7 32535 -37.8640 145.0972 21 -37.729261 144.650631 42.047056
8 32535 -37.8640 145.0972 34 -37.777764 144.772304 30.138684
9 32535 -37.8640 145.0972 22 -37.579206 144.728165 45.397047
10 43255 -37.8545 145.0219 11 -37.416861 145.005372 48.738487
11 43255 -37.8545 145.0219 33 -37.703293 144.572524 42.971083
12 43255 -37.8545 145.0219 21 -37.729261 144.650631 35.510616
13 43255 -37.8545 145.0219 34 -37.777764 144.772304 23.552690
14 43255 -37.8545 145.0219 22 -37.579206 144.728165 40.101407
15 52521 -37.7187 144.9433 11 -37.416861 145.005372 34.043280
16 52521 -37.7187 144.9433 33 -37.703293 144.572524 32.696875
17 52521 -37.7187 144.9433 21 -37.729261 144.650631 25.795774
18 52521 -37.7187 144.9433 34 -37.777764 144.772304 16.424364
19 52521 -37.7187 144.9433 22 -37.579206 144.728165 24.508280
第二次打印：
stationID propertyID
3 34 13425
8 34 32535
13 34 43255
18 34 52521
但根据这个输出站 34 总是最近的。对吗？
编辑：进一步解释：
我曾经试图找到一种方法来 "merge" 两个没有通常用于合并的唯一标识符的数据帧。
我还想将一个数据帧的每一行与另一个数据帧配对（在您的情况下，每个站与每个 属性）以便能够比较这些条目。 在我的研究中，我发现了使用虚拟密钥的巧妙解决方法。
合并通常基于唯一标识符合并数据框，但仅合并那些匹配的行。因此，数据框 A "ID" = 1 仅与数据框 B 中 "ID" = 1 的人匹配。（阅读此处：https://pandas.pydata.org/pandas-docs/version/0.19.1/generated/pandas.DataFrame.merge.html）
在使用的这个解决方法中，我们看到每一行的键都是 1，因此每一行都将与其他数据框中的每一行匹配，这正是我们想要的。
使用应用函数，您可以将任何函数逐行应用于数据框。
使用 BallTree from Sklearn 可以更快地找到最近的邻居
import numpy as np
import pandas as pd
from sklearn.neighbors import KDTree, BallTree
properties=pd.DataFrame({'propertyID':['13425','32535','43255','52521'],
'lat':[-37.79230,-37.86400,-37.85450,-37.71870],
'lon':[145.10290,145.09720,145.02190,144.94330]})
stations=pd.DataFrame({'stationID':['11','33','21','34','22'],
'lat':[-37.416861,-37.703293,-37.729261,-37.777764,-37.579206],
'lon':[145.005372,144.572524,144.650631,144.772304,144.728165]})
property_coords = properties.as_matrix(columns=['lat', 'lon'])
station_coords = stations.as_matrix(columns=['lat', 'lon'])
# Create BallTree using station coordinates and specify distance metric
tree = BallTree(station_coords, metric = 'haversine')
print('PropertyID StationID Distance')
for i, property in enumerate(property_coords):
dist, ind = tree.query(property.reshape(1, -1), k=1) # distance to first nearest station
print(properties['propertyID'][i], stations['stationID'][ind[0][0]], dist[0][0], sep ='\t')
输出
PropertyID StationID Distance
13425 34 0.329682946662
32535 34 0.333699645179
43255 34 0.259425428922
52521 34 0.180690281514
性能
总结--BallTree > 比合并数据帧的方法快 5 倍
详细信息（假设预加载库和数据）
方法一--使用BallTree
%%timeit
property_coords = properties.as_matrix(columns=['lat', 'lon'])
station_coords = stations.as_matrix(columns=['lat', 'lon'])
# Create BallTree using station coordinates and specify distance metric
tree = BallTree(station_coords, metric = 'haversine')
for i, property in enumerate(property_coords):
dist, ind = tree.query(property.reshape(1, -1), k=1) # distance to first nearest station
100 loops, best of 3: 1.79 ms per loop
方法 2--合并两个数据帧
%%timeit
properties['key'] = 1
stations['key'] = 1
df = properties.merge(stations,on='key')
del df['key']
df['distance'] = df.apply(lambda x: haversine(x['lon_x'],x['lat_x'],x['lon_y'],x['lat_y']),axis=1)
#print(df)
df = df.loc[df.groupby("propertyID")["distance"].idxmin()]
df = df[['stationID','propertyID']]
100 loops, best of 3: 10 ms per loop