如何找到 python 上经纬度点的最近邻点?

How to find the nearest neighbors for latitude and longitude point on python?

输入:

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

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

问题: 我可以使用 kd-tree 快速最近邻 s 查找具有纬度和经度的点吗? (例如,scipy中的实现)

是否需要将坐标x,y中的点的地理坐标(经纬度)进行变换?

这是解决这个问题的最佳方法吗?

老实说,我不知道使用 kd-tree 是否能正常工作,但我的直觉说它不准确。

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


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

认为你正在尝试解决k Nearest Neighbor问题。

既然你的数据集是二维的,那么kd-tree就可以了,总的来说,我不知道辣

但是,如果你的点开始生活在更高的维度,那么

scikit-learn 提供 BallTree class that supports the Haversine metric. See also this SO question.