python - 在 Python 中以 1000 秒为单位测量两个经纬度点之间的距离

Question

我有两个数据框。
df1 有 580 条唯一记录 - 包含经纬度信息
df2 有 490000 条唯一记录 - 包含经纬度信息
我试图找出 - 从这 580 个位置中，在 490000 个位置的 400 米半径内存在多少个位置。
我正在使用以下代码并且它正在工作。

from __future__ import print_function
from config import conn
from pandas import DataFrame
import pandas as pd
import math

def distance(origin, destination):
    lat1, lon1 = origin
    lat2, lon2 = destination
    radius = 6371 *1000# km

    dlat = math.radians(lat2-lat1)
    dlon = math.radians(lon2-lon1)
    a = math.sin(dlat/2) * math.sin(dlat/2) + math.cos(math.radians(lat1)) \
        * math.cos(math.radians(lat2)) * math.sin(dlon/2) * math.sin(dlon/2)
    c = 2 * math.atan2(math.sqrt(a), math.sqrt(1-a))
    d = radius * c
    return d

def convertTuple(tup): 
    str =  ''.join(tup) 
    return str


df1 = pd.read_csv("/home/ubuntu/maid80.csv")
df2 = pd.read_csv("/home/ubuntu/iodr.csv")
ll = []
for index,rows in df2.iterrows():
        lat1 = rows['latitude']
        lon1 = rows['longitude']
        for i,r in df1.iterrows():
                k = distance((lat1,lon1),(r['latitude'],r['longitude']))
                if (k <= 400):
                        ll.append(rows['id'])
#                       print(ll)
        print(index)
        myset = set(ll)
        print(myset)

我正在用我的笔记本电脑运行它，完成所有 580 次迭代需要 2 个多小时。我担心第二个数据集中的记录数量会增加。
有没有更好的方法来做到这一点，这样我就可以节省时间。

Answer 1

按纬度对两个数据框进行排序。如果纬度显着不同，这将允许不计算点对之间的距离。在最好的情况下，您可以获得 580 倍的加速。
这个想法是你遍历 df1 的行，并为该数组的每一行找到第二个数组的左右索引，纬度离该行不远

df1.sort_values(by='latitude')
df2.sort_values(by='latitude')
n1 = df1.shape[0]
n2 = df2.shape[0]
left = 0
right = 0
threshold = 400
lat_threshold = threshold / radius # latitude difference that corresponds to 400 m
for i in range(n1):
    row1 = df1.iloc[[i]]
    lat1 = row1['latitude']
    lon1 = row1['longitude']
    while left < n2 and df2.iloc[[left]]['latitude'] < lat1 - lat_threshold:
        left += 1
    while right < n2 and df2.iloc[[right]]['latitude'] < lat1 + lat_threshold:
        right += 1
    for j in range(left, right):
        row2 = df2.iloc[[j]]
        lat2 = row2['latitude']
        lon2 = row2['longitude']
        k = distance((lat1, lon1), (lat2, lon2))
        if (k <= threshold):
            ll.append(row2)