KDTree用于经度/纬度

Question

是否有Python中的包可以在球面上执行类似于kdtree的操作以处理经度/纬度？（这需要正确考虑球面距离以及经度的循环绕组）。

- astrofrog

Answer 1

我认为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]

注意，此处返回的距离是假定半径为1的球体距离 - 要获得地球上的距离，请乘以半径= 6371公里。

参见：

• 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

- backbord

---

除了一个问题，它的表现非常好。请注意，由haversine度量计算的距离假定半径为1的球体，因此您需要乘以半径= 6371km才能获得真实距离。https://scikit-learn.org/stable/modules/generated/sklearn.metrics.pairwise.haversine_distances.html#sklearn.metrics.pairwise.haversine_distances 我认为整体计算/节省时间可能与moooeeeep答案中的转换为3D笛卡尔坐标系没有太大区别，但这应该可以节省一些空间，因为不必存储3D坐标。 - Hansang

Answer 2

一个二叉搜索树本质上不能处理极坐标系统的环绕问题。你可能需要先将坐标转换到三维笛卡尔空间，然后再应用你喜欢的搜索算法，例如kD-Tree, Octree等。

或者，如果你能将坐标输入范围限制在表面的小区域内，你可以将这个区域应用适当的投影映射，即不会过分扭曲区域形状的映射，并在这些无环绕的笛卡尔平面地图坐标上应用标准的二叉搜索树。

- moooeeeep

---

“wraparound”指的是纵向吗？如果是，您能解释一下为什么二叉树不能处理它，但三维空间可以吗？ - pstatix

@pstatix 我指的是有序二叉树，比如kd-tree，它将数据集在超平面上分割成子空间。当坐标环绕时，例如在极坐标中的角度，这种方法不起作用，因为相关点可能在两端。显然，还有一些基于距离计算而不是在超平面上进行分割的二叉树，例如Ball Tree。所以这实际上可能是我当时不知道的一个选项。 - moooeeeep