| 用户 | 纬度 | 经度 |
|---|---|---|
| u1 | x1 | y1 |
| u1 | x2 | y2 |
| u1 | x3 | y3 |
| u2 | x4 | y4 |
| u2 | x5 | y5 |
| u2 | x6 | y6 |
| u3 | x7 | y7 |
| u3 | x8 | y8 |
| 用户 | 最大距离（公里） |
|---|---|
| u1 | 15.2 |
| u2 | 23.7 |
| u3 | 8.3 |
实现了一个快速算法，可在线性时间内运行
具有线性复杂度，即O(N)
执行以下步骤：
import numpy as np
def lat_lon_to_xyz(lat, lon):
'''
Convert latitude/longitude to x, y, z in Earth centered coordinates (assuming spherical earth)
lat, lon are in degrees radian
Source: https://dev59.com/LnM_5IYBdhLWcg3w4nfb
'''
lat_radians = np.deg2rad(lat)
lon_radians = np.deg2rad(lon)
R = 1 # use unit sphere rather than 6371 radius of earth in km
x = R * np.cos(lat_radians) * np.cos(lon_radians)
y = R * np.cos(lat_radians) * np.sin(lon_radians)
z = R *np.sin(lat_radians)
return np.array([x, y, z])
def furthest_points_spadsman(points):
'''
Based upon the following technique which scales linearly with the number of points
- Initialize P1 to the center of mass of the points
- Repeat the following 3 times (once is normally enough but multiple times handles corner cases):
- Set P0 = P1
- Set P1 = the point in points with maximum distance from P0
- P0 and P1 are the furthest two points in x, y, z
Technique from following reference.
Reference: https://dev59.com/k2Qn5IYBdhLWcg3wZGZ4/
'''
# Initialize to mean
p_1 = np.mean(points, axis = 0)
for _ in range(3): # Iterating mitigates corner cases
p_0 = p_1
# Point in points furthest distance from p_0
# note: can use squared distance since monotonical
p_1 = points[np.argmax(np.sum(np.square(points - p_0), axis = -1))]
return p_0, p_1
def haversine(point1, point2):
'''
Data in point1 and point2 are latitude/longitude pairs,
with first number is the latitude (north-south),
and the second number is the longitude (east-west)
Source: https://medium.com/@petehouston/calculate-distance-of-two-locations-on-earth-using-python-1501b1944d97
'''
R = 6371 # Earth radius in km
point1 = np.deg2rad(point1)
point2 = np.deg2rad(point2)
delta = point2 - point1
a = (np.sin(delta[0] / 2) ** 2 +
np.cos(point1[0]) * np.cos(point2[0]) * np.sin(delta[1] / 2) ** 2)
return 2 * R * np.arcsin(np.sqrt(a))
def process(df, user = 'user', lat_field ='lat', lon_field = 'lon'):
'''
Generates the Dataframe containing the maximum distance by user of a set of points
The process works as following steps.
1. Group latitude/longitude data by user
2. Repeat steps 3-7 for each user
3. Map latitudes/longitudes points to x, y, z coordinates using spherical earth approximation)
4. Find two furthest points as follows:
i. calculate the center of mass M of the points
ii. find the point P0 that has the maximum distance to M
iii. find the point P1 that has the maximum distance to P0
iv. P0 and P1 are the furthest two points in x, y, z
5. Use indexes of P0 & P1 to lookup latitude/longitude from original lat/log data
6. Calcualte distance between P0 & P1 using Haversine
7. Update results
8. Return results as a dataframe
Process based upon following references:
a. https://dev59.com/k2Qn5IYBdhLWcg3wZGZ4#16870359
b. https://medium.com/@petehouston/calculate-distance-of-two-locations-on-earth-using-python-1501b1944d97
'''
results = [] # holds list of tuples of (user, distance)
for user_, g in df.groupby(user): # Step 1--Group latitude/longitude data by user
# Step 2--Repeat steps 2-4 for each user
points_lat_lon = g[[lat_field, lon_field]].to_numpy()
# Step 3--map latitudes/longitudes points to x, y, z coordinates
points_xyz = lat_lon_to_xyz(points_lat_lon[:, 0], points_lat_lon[:, 1]).transpose()
# Step 4--Find two furthest points
# Find two furthest points in xyz (using spherical earth aproximation)
p_0, p_1 = furthest_points_spadsman(points_xyz)
# Step 5--Use indexes of P0 & P1 to lookup latitude/longitude from original lat/log data
# Index of p_0 and p_1 in points_xyz (so we also corresponds to the index in points_lat_lon)
index_0 = np.where(np.prod(points_xyz == p_0, axis = -1))[0][0]
index_1 = np.where(np.prod(points_xyz == p_1, axis = -1))[0][0]
lat_lon_0 = points_lat_lon[index_0, :]
lat_lon_1 = points_lat_lon[index_1, :]
# Step 6--Calcualte distance between P0 & P1 using Haversine
distance = haversine(lat_lon_0, lat_lon_1)
# Step 7--update results
results.append((user_, distance))
# Step 8--Return results as a dataframe
return pd.DataFrame(results, columns = [user, 'Max_Distance_km'])
计算美国城市之间的最大距离
from time import time
import pandas as pd
# CSV file downloadable from https://simplemaps.com/data/us-cities
# Datafile with 30, 409 records
cities = pd.read_csv('simplemaps_uscities_basicv1.75/uscities.csv')
t0 = time()
result = process(cities, user = 'state_id', lat_field = 'lat', lon_field = 'lng')
print(f'Processing time: {time()-t0:.3f} seconds')
print(f'Results:\n{result}')
Processing time: 0.104 seconds
Results:
state_id Max_Distance_km
0 AK 3586.855864
1 AL 569.292071
2 AR 492.544129
3 AZ 712.434590
4 CA 1321.284443
5 CO 697.572158
6 CT 182.286421
7 DC 0.000000
8 DE 156.778146
9 FL 936.595405
10 GA 589.700716
11 HI 574.129490
12 IA 538.297210
13 ID 825.044994
14 IL 622.014829
15 IN 496.787181
16 KS 682.563079
17 KY 633.576282
18 LA 601.891459
19 MA 301.815349
20 MD 397.753918
21 ME 509.556000
22 MI 743.578849
23 MN 751.324104
24 MO 707.260076
25 MS 534.872877
26 MT 961.640222
27 NC 778.308918
28 ND 582.080515
29 NE 763.370612
30 NH 249.275265
31 NJ 259.273945
32 NM 747.581138
33 NV 807.834661
34 NY 641.785757
35 OH 471.708115
36 OK 826.431505
37 OR 649.340103
38 PA 508.693319
39 PR 205.710138
40 RI 81.539958
41 SC 435.894534
42 SD 688.135798
43 TN 751.286457
44 TX 1240.972424
45 UT 611.262766
46 VA 729.361836
47 VT 285.877877
48 WA 616.073484
49 WI 570.813035
50 WV 441.834382
51 WY 682.873519
查找动物追踪数据中动物行程的最远距离。
from time import time
import pandas as pd
# Data downloaded from above kaggle link
df = pd.read_csv('migration_original.csv/migration_original.csv')
t0 = time()
result = process(df, user = 'individual-local-identifier', lat_field = 'location-lat', lon_field = 'location-long')
print(f'Processing time: {time()-t0:.3f} seconds')
print(f'Results:\n{result}')
Processing time: 0.325 seconds
Results:
individual-local-identifier Max_Distance_km
0 91732A 7073.629785
1 91733A 65.788571
2 91734A 3446.277830
3 91735A 231.789762
4 91737A 5484.820693
.. ... ...
121 91920A 2535.920902
122 91921A 26.698255
123 91924A 14.518173
124 91929A 0.806871
125 91930A 10.427890
[126 rows x 2 columns]
np.max(np.sum(np.square(points - pt))) 的建议 -- 这不会给我最大距离的值，而不是具有最大距离的 points 中的点吗？ - DarrylGimport pandas as pd
import numpy as np
import random as rn
data = [[rn.randint(1, 10), rn.randint(1, 10)] for x in range(9)]
users = ['user1', 'user2', 'user3'] * 3
rn.shuffle(users)
df1 = pd.DataFrame(data, columns=['x', 'y'], index=users)
选项1
为了测量两点之间的距离（由地理坐标表示），如我上面所提到的，可以使用我在这里分享的函数之一，其中我们将找到更好的解释。
该函数称为haversine，受Haversine公式的启发而来。
def haversine(lon1, lat1, lon2, lat2):
"""
Calculate the great-circle distance (in km) between two points
using their longitude and latitude (in degrees).
"""
# Radius of the Earth
r = 6371.0
# Convert degrees to radians
# First point
lat1 = radians(lat1)
lon1 = radians(lon1)
# Second Point
lat2 = radians(lat2)
lon2 = radians(lon2)
# Haversine formula
dlon = lon2 - lon1
dlat = lat2 - lat1
a = sin(dlat / 2)**2 + cos(lat1) * cos(lat2) * sin(dlon / 2)**2
c = 2 * atan2(sqrt(a), sqrt(1 - a))
return r * c
由于我们想要最大距离，因此让我们创建一个使用先前函数的函数。
def max_distance(lat1, lon1, lat2, lon2):
# Calculate distance between two points
distance = haversine(lon1, lat1, lon2, lat2)
# Return max distance
return np.max(distance)
df2。[In]: df2 = df1.groupby(df1.index).apply(lambda x: pd.Series({'max_distance': max_distance(x['x'].iloc[0], x['y'].iloc[0], x['x'].iloc[1], x['y'].iloc[1])}))
[Out]: max_distance
user1 866.714728
user2 867.428750
user3 247.358878
选项2
根据需求，以下函数也可以用于计算两点之间的最大距离，假设想要计算最大距离，则使用以下函数即可。
def max_distance(lat1, lon1, lat2, lon2):
# Calculate distance between two points
distance = np.sqrt((lat1 - lat2)**2 + (lon1 - lon2)**2)
# Return max distance
return np.max(distance)
df1的索引），其中包含一个名为max_dist_km的列，该列将具有给定用户之间的最大距离（使用前面的函数），应执行以下操作。df2 = df1.groupby(df1.index).apply(lambda x: pd.Series({'max_distance': max_distance(x['x'].iloc[0], x['y'].iloc[0], x['x'].iloc[1], x['y'].iloc[1])}))
这种方法使用pandas groupby与sklearn空间函数相结合。速度相当快（大约与@DarrylG相同）。
我们定义了一个自定义的groupby函数，使用Convex Hull在组内提取边缘点，并使用Distance Metric Haversine计算最大距离。
这个想法是最大距离可以通过仅考虑凸包的边缘来进行尖锐的近似。由于滥用它用于纬度/经度对而导致其不足的边缘情况存在。
import pandas as pd
import numpy as np
from sklearn.metrics import DistanceMetric
from scipy.spatial import ConvexHull
from math import radians
dist = DistanceMetric.get_metric('haversine')
def max_distance_within_group(df):
EARTH_RADIUS = 6371.009
group_gps = df[['location-lat','location-long']].values
if len(group_gps) > 10:
"""
If more than 10 point, lets create a convex-hull,
and only use the edge points.
"""
convex_hull_idx = ConvexHull(group_gps)
group_gps = group_gps[convex_hull_idx.vertices]
haversine_distances = dist.pairwise(np.radians(group_gps))
haversine_distances *= EARTH_RADIUS
return np.max(haversine_distances)
我使用了与@DarrylG相同的第二个测试用例，以便您可以进行比较。我们的速度非常相似，以至于我无法确定哪个更快。
migration = pd.read_csv('work/migration_original.csv')
应用
migration.groupby('individual-local-identifier').apply( max_distance_within_group )
它返回
individual-local-identifier
91732A 7073.639777
91733A 65.788664
91734A 3446.282699
91735A 231.790090
91737A 5484.828441
...
91920A 2535.924485
91921A 26.698292
91924A 14.518194
91929A 0.806872
91930A 10.427905
Length: 126, dtype: float64
你可以在 scipy 中使用 distance_matrix
首先创建一个包含随机值和 3 个用户的数据框
import pandas as pd
from scipy.spatial import distance_matrix
import random as rn
data = [[rn.randint(1, 10), rn.randint(1, 10)] for x in range(9)]
users = ['user1', 'user2', 'user3'] * 3
rn.shuffle(users)
df = pd.DataFrame(data, columns=['x', 'y'], index=users)
df
| x | y | |
|---|---|---|
| 用户2 | 9 | 7 |
| 用户2 | 5 | 4 |
| 用户3 | 3 | 10 |
| 用户1 | 8 | 3 |
| 用户1 | 5 | 7 |
| 用户1 | 8 | 5 |
| 用户2 | 10 | 2 |
| 用户3 | 3 | 9 |
| 用户3 | 2 | 2 |
然后进行分组并应用距离矩阵
df.groupby(df.index).apply(lambda x: distance_matrix(x, x).max())
输出：
user1 5.000000
user2 5.385165
user3 8.062258
dtype: float64