如何在Python中找到经纬度点的最近邻居？

Question

输入：

point = (lat, long)
places = [(lat1, long1), (lat2, long2), ..., (latN, longN)]
count = L

输出: neighbors = point附近的places子集。 (len(neighbors)=L)

问题: 我能否使用kd树快速查找具有纬度和经度的点的最近邻居? (例如，scipy中的实现)

需要将点的地理坐标（纬度和经度）转换为坐标x, y吗？

这是解决此问题的最佳方法吗？

- Andrei

Answer 1

我真的不知道使用kd树是否能正确工作，但我的直觉告诉我它可能不准确。

我认为你需要使用类似于大圆距离的东西来获得准确的距离。

from math import radians, cos, sin, asin, sqrt, degrees, atan2

def validate_point(p):
    lat, lon = p
    assert -90 <= lat <= 90, "bad latitude"
    assert -180 <= lon <= 180, "bad longitude"

# original formula from  http://www.movable-type.co.uk/scripts/latlong.html
def distance_haversine(p1, p2):
    """
    Calculate the great circle distance between two points 
    on the earth (specified in decimal degrees)
    Haversine
    formula: 
        a = sin²(Δφ/2) + cos φ1 ⋅ cos φ2 ⋅ sin²(Δλ/2)
                        _   ____
        c = 2 ⋅ atan2( √a, √(1−a) )
        d = R ⋅ c

    where   φ is latitude, λ is longitude, R is earth’s radius (mean radius = 6,371km);
            note that angles need to be in radians to pass to trig functions!
    """
    lat1, lon1 = p1
    lat2, lon2 = p2
    for p in [p1, p2]:
        validate_point(p)

    R = 6371 # km - earths's radius

    # convert decimal degrees to radians 
    lat1, lon1, lat2, lon2 = map(radians, [lat1, lon1, lat2, lon2])

    # haversine formula 
    dlon = lon2 - lon1
    dlat = lat2 - lat1

    a = sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2
    c = 2 * asin(sqrt(a)) # 2 * atan2(sqrt(a), sqrt(1-a))
    d = R * c
    return d

- Marcel Wilson

---

在这段代码中，如何找到validate_point函数？我猜它会检查纬度和经度是否介于-90和90之间？ - fmarm

这个答案有点不完整，没有回答 OP 的问题。函数 distance_haversine() 计算了两个经纬度坐标之间的距离（单位为公里），但它并没有回答如何使用这个度量找到最近的邻居的问题。 - lumbric

@lumbric 从技术上讲，你是正确的。我提供了计算距离的方法，因为问题的一部分是在问地理点是否需要转换。最终的答案是，如果使用distance_haversine，你不需要转换它们。你只需找到每组点之间的距离并选择最小值即可。 - Marcel Wilson

@MarcelWilson 是的，你说得对，你的答案可以轻松地用于计算所有成对距离，然后取最小值。这是可能的，但不是最优的。对于大量数据（比如>10,000个点），这将使用大量内存并花费很长时间。它需要O(n^2)的时间和内存，而最优解应该是O(n*log(n))的时间，例如使用某种索引，如k-trees。由于OP问到了k-trees，我假设他对最优解感兴趣。 - lumbric

@MarcelWilson 当然，如果距离很大，仅依赖欧几里得度量是有风险的。我认为可以使用Haversine度量找到O(n*log(n))解决问题的算法。我不确定KDTree，但是sklearn中的BallTree支持Haversine度量（我不确定是否存在任何陷阱）。 - lumbric

Answer 2

scikit-learn提供了一个BallTree类，支持Haversine度量。请参见此 SO 问题。

- Florian Brucker

---

这是最好的答案。 - Shashwat

Answer 3

我认为您正在尝试解决 k最近邻问题。

由于您的数据集位于2D中，因此 kd树通常可以很好地解决，但我不知道spicy是什么。

然而，如果您的点开始存在于更高的维度中，则 kd树将不是明智的选择。

- gsamaras

---

数据并不是以二维形式给出的，数据点以纬度/经度表示，无法精确转换为二维坐标。可以使用Haversine公式计算点之间的距离，但与二维坐标不完全相同（我不知道kd-tree是否适用）。 - lumbric