经度/纬度的KDTree

Question

在Python中有没有什么包可以让你对球体表面的经度/纬度进行类似kdtree的操作？(这将需要适当地考虑球面距离，以及经度上的环绕)。

Answer 1

二分搜索树不能处理极坐标表示的环绕。您可能需要将坐标转换到3D笛卡尔空间，然后应用您最喜欢的搜索算法，例如kD-Tree、八叉树等。

或者，如果可以将坐标的输入范围限制为曲面上的一个小区域，则可以将适当的地图投影应用于此区域，即不会使区域的形状发生太大扭曲的区域，并在这些无包裹的笛卡尔地图坐标上应用标准的二进制搜索树。

Answer 2

我相信来自scikit learn with the Haversine指标的BallTree应该可以帮你完成这项工作。

举个例子：

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]

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

请参见：

• https://jakevdp.github.io/blog/2013/04/29/benchmarking-nearest-neighbor-searches-in-python/
• https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.BallTree.html
• https://scikit-learn.org/stable/modules/generated/sklearn.metrics.pairwise.haversine_distances.html#sklearn.metrics.pairwise.haversine_distances