KDTree为经度/纬度

ast*_*rog 9 python kdtree latitude-longitude data-structures

Python中是否有任何包允许对球体表面的经度/纬度进行类似kdtree的操作?(这需要适当考虑球面距离,以及经度环绕).

moo*_*eep 6

二叉搜索树无法通过设计处理极坐标表示的环绕.您可能需要将坐标转换为3D笛卡尔空间,然后应用您最喜欢的搜索算法,例如kD-Tree,Octree等.

或者,如果您可以将坐标的输入范围限制为曲面上的小区域,则可以将适当的地图投影应用于此区域,即不会过度扭曲区域形状的投影,并应用标准二进制在这些无环绕的笛卡尔地图坐标上搜索树.


小智 6

我相信来自 scikit-learn 的 BallTree 和 Haversine 度量应该可以为您解决问题。

举个例子:

from sklearn.neighbors import BallTree
import numpy as np
import pandas as pd

cities = pd.DataFrame(data={
    'name': [...],
    'lat': [...],
    'lon': [...]
})

query_lats = [...]
query_lons = [...]

bt = BallTree(np.deg2rad(cities[['lat', 'lon']].values), metric='haversine')
distances, indices = bt.query(np.deg2rad(np.c_[query_lats, query_lons]))

nearest_cities = cities['name'].iloc[indices]
Run Code Online (Sandbox Code Playgroud)

请注意,这将返回假设半径为 1 的球体的距离 - 得到地球上的距离乘以半径 = 6371km

看:

  • 除了 1 件事外,效果很好,请注意,由半正弦度量计算的距离假设半径为 1 的球体,因此您需要乘以半径 = 6371km 才能获得实际距离。https://scikit-learn.org/stable/modules/generated/sklearn.metrics.pairwise.haversine_distances.html#sklearn.metrics.pairwise.haversine_distances 我认为节省的总体计算/时间可能与在 moooeeeep 的答案中转换为 3D 笛卡尔坐标,但这应该可以节省一些空间,而不必存储 3D 坐标 (2认同)