在Pandas中实现两组点的快速距离计算与迭代优化

原嵌套循环的复杂度是O(n*m)，数据量增大后速度会急剧下降，以下是几种更高效的实现方式：

方法一：Scipy KDTree 近邻搜索（推荐大场景使用） #

KDTree可以将近邻查询的复杂度降到O(n log m)，适合轨迹点或固定地点数量较多的场景：

import pandas as pd
import numpy as np
from scipy.spatial import KDTree

# 提取固定地点的坐标数组
location_coords = locations[['Latitude', 'Longitude']].values
# 构建KDTree索引
kdtree = KDTree(location_coords)

# 提取轨迹点坐标
movement_coords = movements[['Lat', 'Lng']].values
# 批量查询每个轨迹点最近的固定点，返回距离和对应索引
distances, indices = kdtree.query(movement_coords, k=1)

# 给轨迹数据标记结果
movements['distance'] = distances
movements['visit'] = np.where(
    distances < 0.05,
    locations.iloc[indices]['Location'].values,
    'no visit'
)

方法二：NumPy广播向量化运算（中小数据量适用） #

利用NumPy的广播机制一次性计算所有点对的距离，避免循环，代码简洁：

import pandas as pd
import numpy as np

# 将固定地点坐标转为列向量，实现广播运算
lat_loc = locations['Latitude'].values[:, np.newaxis]
lon_loc = locations['Longitude'].values[:, np.newaxis]
# 轨迹点坐标
lat_move = movements['Lat'].values
lon_move = movements['Lng'].values

# 计算所有轨迹点到固定点的距离矩阵
distance_matrix = np.sqrt((lat_loc - lat_move)**2 + (lon_loc - lon_move)**2)

# 提取每个轨迹点的最小距离和对应固定点索引
min_distances = distance_matrix.min(axis=0)
min_indices = distance_matrix.argmin(axis=0)

# 赋值结果到轨迹数据表
movements['distance'] = min_distances
movements['visit'] = np.where(
    min_distances < 0.05,
    locations.iloc[min_indices]['Location'].values,
    'no visit'
)

注意：如果固定地点和轨迹点数量都很大（比如十万级以上），距离矩阵会占用大量内存，此时不推荐该方法。

方法三：Geopandas空间索引（地理空间场景适配） #

如果后续需要切换为真实地理距离（而非欧氏距离），或者需要更灵活的空间查询，Geopandas的空间索引是更好的选择：

import geopandas as gpd
from shapely.geometry import Point

# 转换为GeoDataFrame
locations_gdf = gpd.GeoDataFrame(
    locations,
    geometry=gpd.points_from_xy(locations['Longitude'], locations['Latitude'])
)
movements_gdf = gpd.GeoDataFrame(
    movements,
    geometry=gpd.points_from_xy(movements['Lng'], movements['Lat'])
)

# 构建固定地点的空间索引
sindex = locations_gdf.sindex

# 定义函数：查找轨迹点是否在阈值范围内的固定地点
def check_visit(point, threshold=0.05):
    # 先通过空间索引筛选候选点，减少计算量
    candidate_idx = list(sindex.intersection(point.buffer(threshold).bounds))
    candidates = locations_gdf.iloc[candidate_idx]
    # 计算欧氏距离
    distances = np.sqrt((candidates['Latitude'] - point.y)**2 + (candidates['Longitude'] - point.x)**2)
    valid = distances < threshold
    if valid.any():
        return candidates.loc[valid, 'Location'].iloc[0]
    return 'no visit'

# 批量处理轨迹点
movements_gdf['visit'] = movements_gdf['geometry'].apply(check_visit)
# 可选：添加最小距离字段
movements_gdf['distance'] = movements_gdf.apply(
    lambda row: np.min(np.sqrt((locations['Latitude'] - row['Lat'])**2 + (locations['Longitude'] - row['Lng'])**2)),
    axis=1
)

内容的提问来源于stack exchange，提问作者Darren Teo