km에서 (km)을 십진수로 변환하십시오.

Question

scipy.KDTree을 사용하면 몇 가지 가장 가까운 이웃 검색을 수행 할 수 있습니다. 검색을 수행하려면 KDTree.query_ball_point(pnt, r=some_distance)을 사용하고 있습니다.

요점은 위도가 길기 때문에 검색 할 반경 값 (some_distance)은 십진수 여야합니다 (저는 믿습니다). 내가이 거리를 사용자가 접근 할 수있게하고 싶다면 킬로미터, 미터, 마일 등으로 그 거리가 주어질 것이라고 기대한다.

킬로미터 단위의 거리를 십진수 도 값? 나는 numpy, scipy를 사용하고 있고 PySAL로 약간 연주했다.

도움말 알, 루이

Answer 1

here에서

고전 계산 :

거리

이 두 점 사이의 큰 서클 거리를 계산하는 '하버 사인'공식을 사용하여 - 즉, 최단 지구 표면 위의 거리 - 포인트 사이에 '까마귀처럼'거리를 제공합니다 (물론 모든 언덕은 무시합니다!).

하버 사인 화학식 :

a = sin²(Δφ/2) + cos(φ1).cos(φ2).sin²(Δλ/2) 
c = 2.atan2(√a, √(1−a)) 
d = R.c 

φ는 위도, λ는 R이 지구 반경 (반경 = 6,371km 평균) 각도 함수 삼각 전달할 라디안되어야한다는 주이며, 경도이다!

해상 마일 (기호 M, NM 또는 NMI)에 대한 하나의 길이의 단위가된다

당신은 물론 해상 마일의 정의와 킬로미터에서 매우 거칠고 준비 근사 할 수 있습니다 분당 (바다 수준에서) 경도를 따라 측정 된 위도의 분, 또는 적도에서의 경도의 아크의 약 1 분. 국제 협약에 의해 1,852 미터 (정확히 6,076 피트)로 정해졌습니다.

Answer 2

이것은 직접적인 해결책은 아니지만 더 많은 참조입니다. 이전에 haversine 수식을 사용해 보았지만 가장 가까운 n 개의 이웃을 계산할 때이 수식을 사용하면 수천 개의 점에 사용할 때 참을성있게 길어졌습니다.

그래서 해쉬 클래스 (또는 매핑?)를 만들어서 빠른 검색을 위해 이진 트리에 넣을 수 있습니다. 거리가 아니라 각도 (위도, 경도)에서 작동합니다.

찾기 기능은 트리에서 가장 가까운 지점을 찾은 다음 n 개의 노드가 발견 될 때까지 트리를 다시 걷는 방식으로 작동합니다.

geocode.py :

units = [(31-q, 180.0/(2 ** q)) for q in range(32)] 

def bit_sum(bits): 
    return sum([2**bit for bit in bits]) 

class gpshash(object): 
    def __init__(self, longitude = None, latitude = None, **kwargs): 
     if(kwargs): 
      if(kwargs.has_key("longitude ") and kwargs.has_key("latitude ")): 
       self.longitude = geohash(degrees=kwargs["degrees"]) 
       self.latitude = geohash(degrees=kwargs["hash"]) 
     else: 
      if(longitude == None or latitude == None): 
       self.longitude = geohash(degrees=0) 
       self.latitude = geohash(degrees=0) 
      else: 
       self.longitude = geohash(degrees=longitude) 
       self.latitude = geohash(degrees=latitude) 
     long_hash = self.longitude.bin_hash 
     lat_hash = self.latitude.bin_hash 
     hash_str = "" 
     if(len(long_hash) == len(lat_hash)): 
      for i in range(len(long_hash)): 
       hash_str += (long_hash[i]+lat_hash[i]) 
     self.bin_hash = hash_str 
    def __str__(self): 
     return "%s, %s" % (str(self.longitude.hash), str(self.latitude.hash)) 
    def __repr__(self): 
     return str("<gpshash long: %f lat: %f>" % (self.longitude.degrees, self.latitude.degrees)) 
    def __eq__(self, other): 
     if(isinstance(self, gpshash) and isinstance(other, gpshash)): 
      return (((self.longitude._hash^other.longitude._hash) == 0) and ((self.latitude._hash^other.latitude._hash) == 0)) 
     else: 
      return False 

class geohash(object): 
    def __init__(self, degrees = 0, **kwargs): 
     if(kwargs): 
      if(kwargs.has_key("degrees")): 
       self.degrees = kwargs["degrees"] % 360 
       self._hash = self.encode() 
      elif(kwargs.has_key("hash")): 
       self._hash = kwargs["hash"] % ((2 << 31) - 1) 
       self.degrees = self.decode() 
     else: 
      self.degrees = degrees % 360 
      self._hash = self.encode() 
    def __str__(self): 
     return str(self.hash) 
    def __repr__(self): 
     return str("<geohash degrees: %f hash: %s>" % (self.degrees, self.hash)) 
    def __add__(self, other): 
     return geohash(hash=(self._hash + other._hash)) 
    def __sub__(self, other): 
     return geohash(hash=(self._hash - other._hash)) 
    def __xor__(self, other): 
     return geohash(hash=(self._hash^other._hash)) 
    def __eq__(self, other): 
     if(isinstance(self, geohash) and isinstance(other, geohash)): 
      return ((self._hash^other._hash) == 0) 
     else: 
      return False 
    def encode(self): 
     lesser = filter(lambda (bit, angle): self.degrees >= angle, units) 
     combined = reduce(lambda (bits, angles), (bit, angle): (bits+[bit], angles + angle) if((angles + angle) <= self.degrees) else (bits, angles), lesser, ([], 0)) 
     return bit_sum(combined[0]) 
    def decode(self): 
     lesser = filter(lambda (bit, angle): self._hash>= (2 ** bit), units) 
     combined = reduce(lambda (bits, angles), (bit, angle): (bits+[bit], angles + angle) if((bit_sum(bits+[bit])) <= self._hash) else (bits, angles), lesser, ([], 0)) 
     return combined[1] 
    @property 
    def hash(self): 
     self._hash = self.encode() 
     return "%08x" % self._hash 
    @property 
    def inv_hash(self): 
     self._inv_hash = self.decode() 
     return self._inv_hash 
    @property 
    def bin_hash(self): 
     self._bin_hash = bin(self._hash)[2:].zfill(32) 
     return self._bin_hash 

class gdict(object): 
    ''' 
    Base Geo Dictionary 
    Critical Components taken from Python26\Lib\UserDict.py 
    ''' 
    __slots__ = ["parent", "left", "right", "hash_type"] 
    hash_type = None 
    def __init__(self, ihash=None, iparent=None): 
     def set_helper(iparent, cur_hex, hex_list): 
      ret_bin_tree = self.__class__(None, iparent) 
      if(hex_list): 
       ret_bin_tree.set_child(cur_hex, set_helper(ret_bin_tree, hex_list[0], hex_list[1:])) 
       return ret_bin_tree 
      elif(cur_hex): 
       ret_bin_tree.set_child(cur_hex, ihash) 
       return ret_bin_tree 
     self.parent = self 
     self.left = None 
     self.right = None 
     if(iparent != None): 
      self.parent = iparent 
     if(isinstance(ihash, self.hash_type)): 
      ilist = list(ihash.bin_hash) 
      if(len(ilist) > 1): 
       ret_bin_tree = set_helper(self, ilist[1], ilist[2:]) 
      if(ret_bin_tree): 
       self.set_child(ilist[0], ret_bin_tree) 
    def set_child(self, istr, ichild): 
     if(istr == "0"): 
      self.left = ichild 
     elif(istr == "1"): 
      self.right = ichild 
    def get_child(self, istr): 
     if(istr == "0"): 
      return self.left 
     elif(istr == "1"): 
      return self.right 
     else: 
      return "" 
    def __repr__(self): 
     def repr_print_helper(ibin_tree, fmt_str = "", depth = 1): 
      if(not isinstance(ibin_tree, self.__class__)): 
       fmt_str += "\n" 
       fmt_str += ("%%%ds" % (depth)) % "" 
       fmt_str += ibin_tree.__repr__() 
      else: 
       if((ibin_tree.left != None and ibin_tree.right == None) or (ibin_tree.left == None and ibin_tree.right != None)): 
        if(ibin_tree.left != None): 
         fmt_str += "0" 
         fmt_str = repr_print_helper(ibin_tree.left, fmt_str, depth + 1) 
        elif(ibin_tree.right != None): 
         fmt_str += "1" 
         fmt_str = repr_print_helper(ibin_tree.right, fmt_str, depth + 1) 
       else: 
        if(ibin_tree.left != None): 
         fmt_str += "\n" 
         fmt_str += ("%%%ds" % (depth - 1)) % "" 
         fmt_str += "0" 
         fmt_str = repr_print_helper(ibin_tree.left, fmt_str, depth + 1) 
        if(ibin_tree.right != None): 
         fmt_str += "\n" 
         fmt_str += ("%%%ds" % (depth - 1)) % "" 
         fmt_str += "1" 
         fmt_str = repr_print_helper(ibin_tree.right, fmt_str, depth + 1) 
      return fmt_str 
     return repr_print_helper(self) 
    def find(self, ihash, itarget = 1): 
     class flat(list): 
      pass 
     def find_helper_base(iparent, ibin_tree, ihash): 
      ret_find = None 
      if(isinstance(ibin_tree, self.hash_type)): 
       ret_find = iparent 
      elif(len(ihash) > 0): 
       if(ibin_tree.get_child(ihash[0])): 
        ret_find = find_helper_base(ibin_tree, ibin_tree.get_child(ihash[0]), ihash[1:]) 
       else: 
        ret_find = ibin_tree 
      return ret_find 
     def up_find(iflat, iparent, ibin_tree, ibias = "0"): 
      if((ibin_tree != iparent) and (len(iflat) < itarget)): 
       if(iparent.left): 
        if(len(iflat) >= itarget): 
         return 
        if(iparent.left != ibin_tree): 
         down_find(iflat, iparent.left, ibias) 
       if(iparent.right): 
        if(len(iflat) >= itarget): 
         return 
        if(iparent.right != ibin_tree): 
         down_find(iflat, iparent.right, ibias) 
       up_find(iflat, ibin_tree.parent.parent, ibin_tree.parent, ibias) 
     def down_find(iflat, ibin_tree, ibias = "0"): 
      if(len(iflat) >= itarget): 
       return 
      elif(isinstance(ibin_tree, self.hash_type)): 
       iflat += [ibin_tree] 
      else: 
       if(ibias == "1"): 
        if(ibin_tree.left): 
         down_find(iflat, ibin_tree.left, ibias) 
        if(ibin_tree.right): 
         down_find(iflat, ibin_tree.right, ibias) 
       else: 
        if(ibin_tree.right): 
         down_find(iflat, ibin_tree.right, ibias) 
        if(ibin_tree.left): 
         down_find(iflat, ibin_tree.left, ibias) 
     if(isinstance(ihash, self.hash_type)): 
      flatter = flat() 
      hasher = ihash.bin_hash 
      base = find_helper_base(self, self.get_child(hasher[0]), hasher[1:]) 
      if(base): 
       down_find(flatter, base) 
       bias = flatter[0].bin_hash[0] 
       up_find(flatter, base.parent, base, bias) 
      return list(flatter) 
    def merge(self, from_bin_tree): 
     def merge_helper(to_bin_tree, from_bin_tree): 
      if(isinstance(from_bin_tree, self.__class__)): 
       if(from_bin_tree.left != None): 
        if(to_bin_tree.left != None): 
         merge_helper(to_bin_tree.left, from_bin_tree.left) 
        else: 
         from_bin_tree.left.parent = to_bin_tree 
         to_bin_tree.left = from_bin_tree.left 
       elif(from_bin_tree.right != None): 
        if(to_bin_tree.right != None): 
         merge_helper(to_bin_tree.right, from_bin_tree.right) 
        else: 
         from_bin_tree.right.parent = to_bin_tree 
         to_bin_tree.right = from_bin_tree.right 
     merge_helper(self, from_bin_tree) 

class geodict(gdict): 
    ''' 
    Geo Dictionary 
    ''' 
    hash_type = geohash 
    def __init__(self, ihash=None, iparent=None): 
     gdict.__init__(self, ihash, iparent) 

class gpsdict(gdict): 
    ''' 
    GPS Dictionary 
    ''' 
    hash_type = gpshash 
    def __init__(self, ihash=None, iparent=None): 
     gdict.__init__(self, ihash, iparent) 

if(__name__ == "__main__"): 
    gpses = \ 
    [ 
     gpshash(90, 90), 
     gpshash(68, 24), 
     gpshash(144, 60), 
     gpshash(48, 91), 
     gpshash(32, 105), 
     gpshash(32, 150), 
     gpshash(167, 20), 
     gpshash(49, 116), 
     gpshash(81, 82), 
     gpshash(63, 79), 
     gpshash(129, 76) 
    ] 

    base_dict = gpsdict() 
    for cur_hash in gpses: 
     base_dict.merge(gpsdict(cur_hash)) 

    print "All locations added:" 
    print base_dict 
    print "" 
    print "Trying to find 3 nearest points to:" 
    to_find = gpshash(60, 20) 
    print to_find.__repr__() 
    found = base_dict.find(to_find, 3) 
    print "" 
    print "Found the following:" 
    for x in found: 
     print x.__repr__()