どのようにPythonの緯度と経度のポイントのための最近隣を見つけるのですか？

Question

入力：

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

出力： neighbors = pointからplaces近くのサブセット。 （len(neighbors)=L）

質問： 私は緯度と経度とポイントの迅速な最近傍ののルックアップのためのkdツリーを使用することはできますか？ （たとえば、scipyの実装）

座標x、yのポイントの地理座標（緯度と経度）を変換する必要がありますか？

これを解決する最善の方法はありますか？

Answer 1

私は正直なところ、kd-treeを使うと正しく動作するかどうかわかりませんが、私の勘違いは不正確であると言います。

正確な距離を得るためには、より大きな円距離のようなものを使用する必要があると思います。

# 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! 

    :p1:  (tup) lat,lon 
    :p2:  (tup) lat,lon 
    """ 
    lat1, lon1 = p1 
    lat2, lon2 = p2 
    for p in [p1, p2]: 
     validate_point(p) 

    R = 6371.0 # 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 

Answer 2

私はあなたがk Nearest Neighbor問題を解決しようとしていると思います。

データセットは2Dであるため、kd-treeはうまく動作しますが、一般的にスパイシーについてはわかりません。

しかし、あなたのポイントがより高い次元で生きていく場合は、kd-tree will not be a smart choiceです。