Geohash

Geohash is a hash function that convert a location coordinate pair into a base32 string.

Check how to generate geohash on wiki:Geohashor just google it for more details.

Tryhttp://geohash.co/.

You task is converting a (latitude, longitude) pair into a geohash string.

Example

Given lat =39.92816697, lng =116.38954991and precision =12which indicate how long the hash string should be. You should returnwx4g0s8q3jf9.

The precision is between 1 ~ 12.

S:

1. 对latitude和longtitude进行二分处理，得到 经度/2 长度的二进制序列
2. 合并经纬序列，先经后纬，经纬交替
3. 以2^5为base, 将二进制转化为index，得到最终序列

    string encode(double latitude, double longitude, int precision) {
        string _base32 = "0123456789bcdefghjkmnpqrstuvwxyz";
        int size = precision * 5;

        string hash_code = "";
        string b = "";
        //对latitude和longtitude进行二分处理，得到 经度/2 长度的二进制序列
        string lat_bin = getBin(latitude, -90, 90, size/2);
        string lng_bin = getBin(longitude, -180, 180, size/2);  
        //合并经纬序列，先经后纬，经纬交替    
        for (int i = 0; i < size/2; ++i) {
            b += lng_bin[i];
            b += lat_bin[i];
        }
        //以2^5为base, 将二进制转化为index，得到最终序列
        for (int i = 0; i < size; i += 5) {
            hash_code += _base32[b2i(b.substr(i, 5))];
        }

        return hash_code;
    }

    int b2i(string bin) {
        int base = 1, val = 0;
        for (int i = bin.size() - 1; i >= 0; --i) {
            if (bin[i] == '1')
                val += base;
            base *= 2;
        }
        return val;
    }

    string getBin(double value, double left, double right, int size) {
        string b = "";
        for (int i = 0; i < size; ++i) {
            double mid = (left + right) / 2.0;
            if (value > mid) {
                left = mid;
                b += "1";
            } else {
                right = mid;
                b += "0";
            }
        }
        return b;
    }