GeoHash

LBS系统中的两大定位距离计算算法之一，原理就是根据经纬经纬的顺序进行二分，每五个bit合成一个32进制数，根据不同精度需要生成不同位的32进制数，最后使用这个数去进行前缀字符串匹配找到需要寻找的目标

class GeoHash:
    # @param {double} latitude, longitude a location coordinate pair
    # @param {int} precision an integer between 1 to 12
    # @return {string} a base32 string
    def encode(self, latitude, longitude, precision):
        # Write your code here
        result = ''
        tmpNum = ''
        base32 = '0123456789bcdefghjkmnpqrstuvwxyz'
        limit = precision * 5
        count = 0

        latitudeStart, latitudeEnd = float(-90), float(90)
        longitudeStart, longitudeEnd = float(-180), float(180)
        while count < limit:
            if count % 2:
                tmpMid = latitudeStart + (latitudeEnd - latitudeStart) / 2
                if latitude > tmpMid:
                    tmpNum += '1'
                    latitudeStart = tmpMid
                else:
                    tmpNum += '0'
                    latitudeEnd = tmpMid
            else:
                tmpMid = longitudeStart + (longitudeEnd - longitudeStart) / 2
                if longitude > tmpMid:
                    tmpNum += '1'
                    longitudeStart = tmpMid
                else:
                    tmpNum += '0'
                    longitudeEnd = tmpMid

            count += 1
            if count % 5 == 0:
                result += base32[int(tmpNum, 2)]
                tmpNum = ''

        return result

GeoHashII

上面是把经纬度信息编码成geohash字符串，这里是把geohash字符串解析回具体位置，这个步骤在系统中推测用的其实很少

class GeoHash:
    # @param {string} geohash a base32 string
    # @return {double[]} latitude and longitude a location coordinate pair
    def decode(self, geohash):
        # Write your code here 
        latitudeStart, latitudeEnd = float(-90), float(90)
        longitudeStart, longitudeEnd = float(-180), float(180)
        base32 = '0123456789bcdefghjkmnpqrstuvwxyz'

        n = len(geohash)
        count = 0


        for i in xrange(n):
            curNum = bin(base32.find(geohash[i]))[2:].zfill(5)
            for j in xrange(5):
                if count % 2 and curNum[j] == '1':
                    latitudeStart += (latitudeEnd - latitudeStart) / 2
                elif count % 2 and curNum[j] == '0':
                    latitudeEnd = latitudeStart + (latitudeEnd - latitudeStart) / 2
                elif count % 2 == 0 and curNum[j] == '1':
                    longitudeStart += (longitudeEnd - longitudeStart) / 2
                else:
                    longitudeEnd = longitudeStart + (longitudeEnd - longitudeStart) / 2
                count += 1

        return latitudeStart + (latitudeEnd - latitudeStart) / 2, longitudeStart + (longitudeEnd - longitudeStart) / 2