优化 2 long 二维点阵之间的距离计算

Question

我试图通过使用 'apply' 函数在数据帧的所有行上应用内联函数来避免循环。

问题是，我有大约 800 个点（卡车停靠点），我正在尝试确定其中哪些点位于某条路线上，该路线本身由大约 100k 点定义。

我的方法是计算卡车停靠站到路线上每个点之间的欧氏距离，如果这些距离中的任何一个小于某个值，我将保留路线。

我最初是通过循环来做到这一点的，但它非常慢（假设我在距离小于某个值时不中断循环，就像 100k*800 次迭代）。

所以我尝试使用 'apply' 但它仍然很慢。有谁知道我可以优化它的方法吗？

完整代码：

import pandas as pd
import numpy as np
import time, os

BASE_DIR='C:\Users\aidenm\Desktop\geo'

rt_df = pd.read_csv(os.path.join(BASE_DIR, 'test_route.txt'))
'''
lon, lat
-118.410339, 34.019653
-118.410805, 34.020241
-118.411301, 34.020863
-118.411766, 34.021458
...
'''

fm_df = pd.read_csv(os.path.join(BASE_DIR, 'test_fm.txt'))
'''
lat, lon
41.033959, -77.515672
41.785524, -80.853175
41.128748, -80.769934
41.465085, -82.060677
...
'''



def is_on_route_inline(x, route_coordinates):
    '''

    :param route_coordinates:
    :param fencing_module_coordinate:
    :return: True if on route else False
    '''



    a = np.array((float(x[0]), float(x[1])))
    # bs = [np.array((c[1], c[0])) for c in rcs]


    def distance_inline(b, fcm_point):
        return np.linalg.norm(b-fcm_point)

    # bss = pd.Series(bs)
    distances = route_coordinates.apply(distance_inline, args=(a,), axis=1)   #np.linalg.norm(a-b))

    # distances = [np.linalg.norm(a-b) for b in bs]

    if min(distances)<0.1:
        print(x)
        return True

    return False

fm_df.apply(is_on_route_inline,  args=(rt_df,), axis=1)#rt_df)

Answer 1

要快速完成此操作，您需要将 DataFrame 中的数据转换为 Numpy 数组。首先，让我们计算一个卡车停靠点和所有路线点之间的距离–

# Create Numpy array of shape (100k, 2)
route_points = rt_df[['lat', 'lon']].values

truck_stop = # get one truck stop location shape (2, )

# Compute distances
dists = np.linalg.norm(route_points - truck_stop, axis=1)

这让 Numpy 广播可以为您处理所有路线位置的循环（非常快）。但是，听起来您真正需要的是 truck-stops 和 route-points 的 所有对 之间的距离。让 Numpy 广播来做到这一点很棘手，所以我建议使用 scipy.spatial.distance_matrix

from scipy.spatial import distance_matrix

route_points = rt_df[['lat', 'lon']].values  # shape (100k, 2)
truck_points = fm_df[['lat', 'lon']].values  # shape (800, 2)

all_distances = distance_matrix(route_points, truck_points) # shape (100k, 800)

现在 all_distances 是一个包含所有 pair-wise 距离的 Numpy 数组，因此 all_distances[i, j] 是路线 i 和卡车停靠点 j 之间的距离。同样，这让 Numpy 可以为您处理 100k * 800 次迭代的循环，而且速度非常快。（在我的笔记本电脑上，使用类似大小的数组完成此操作大约需要 3 秒）。

之后，你可以找到足够小的距离

all_distances < 0.1

优化 2 long 二维点阵之间的距离计算

Optimize distance calculations between 2 long, 2-D arrays of points

python

numpy

vectorization

pandas

优化 2 **long** 二维点阵之间的距离计算

Optimize distance calculations between 2 **long**, 2-D arrays of points

python

numpy

vectorization

pandas

优化 2 long 二维点阵之间的距离计算

Optimize distance calculations between 2 long, 2-D arrays of points