浅析GeoHash

发表于 | 分类于 |

GeoHash算法能够将二维的经纬度转换成字符串。主要有以下几个特性:

  1. 每一个字符串代表了某一矩形区域.
  2. 字符串的长度越长，所表示的位置越精确。
  3. 字符串越相近的表示的举例越接近.

原理

GeoHash将经纬度转换为hash字符串主要分为三步：

  1. 将纬度(-90, 90)平均分成两个区间(-90, 0)、(0, 90)，如果坐标位置的纬度值在第一区间，则编码是0，否则编码为1
  2. 经纬度的编码合并，从0开始，奇数为是纬度，偶数为是经度
  3. 对经纬度合并后的编码，进行base32编码

大概过程如下图，不断的对经纬度进行切割，直到精准度达到要求。
IMAGE

代码实现

将经纬度转换成二进制编码

1
2
3
4
5
6
7
8
9
10
11
12
13
private void convert(double min, double max, double value, List<Character> list) {
        if (list.size() > (length - 1)) {
            return;
        }
        double mid = (max + min) / 2;
        if (value < mid) {
            list.add('0');
            convert(min, mid, value, list);
        } else {
            list.add('1');
            convert(mid, max, value, list);
        }
    }

合并经纬度的二进制编码

1
2
3
4
5
6
7
8
List<Character> latList = new ArrayList<Character>();
List<Character> lngList = new ArrayList<Character>();
convert(Min_Lat, Max_Lat, lat, latList);
convert(Min_Lng, Max_Lng, lng, lngList);
StringBuilder sb = new StringBuilder();
for (int index = 0; index < latList.size(); index++) {
    sb.append(lngList.get(index)).append(latList.get(index));
}

base32编码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private final String[] base32Lookup =
            {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "b", "c", "d", "e", "f", "g", "h",
                    "j", "k", "m", "n", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"};
    private String base32Encode(final String str) {
        String unit = "";
        StringBuilder sb = new StringBuilder();
        for (int start = 0; start < str.length(); start = start + 5) {
            unit = str.substring(start, start + 5);
            sb.append(base32Lookup[convertToIndex(unit.split(""))]);
        }
        return sb.toString();
    }
    private int convertToIndex(String str) {
        int length = str.length();
        int result = 0;
        for (int index = 0; index < length; index++) {
            result += str.charAt(index) == '0' ? 0 : 1 << (length - 1 - index);
        }
        return result;
    }

Redis中的Geo使用

在Redis中，Geo的内部结构实际上是一个zset。
Redis提供给Geo指定只有6个，但是它可以使用zset的所有指令。

增加-geoadd

geoadd指令传入多个经纬度名称三元组，Redis内存会调用函数计算出相应的geohash字符串。

1
2
3
4
5
6
7
8
127.0.0.1:6379> geoadd company 116.48105 39.996794 juejin
(integer) 1
127.0.0.1:6379> geoadd company 116.514203 39.905409 ireader
(integer) 1
127.0.0.1:6379> geoadd company 116.489033 40.007669 meituan
(integer) 1
127.0.0.1:6379> geoadd company 116.562108 39.787602 jd 116.334255 40.027400 xiaomi
(integer) 2

距离-geodist

geodist 指令可以用来计算两个元素之间的距离，携带集合名称、2 个名称和距离单位。

1
2
3
4
5
6
7
8
9
10
127.0.0.1:6379> geodist company juejin ireader km
"10.5501"
127.0.0.1:6379> geodist company juejin meituan km
"1.3878"
127.0.0.1:6379> geodist company juejin jd km
"24.2739"
127.0.0.1:6379> geodist company juejin xiaomi km
"12.9606"
127.0.0.1:6379> geodist company juejin juejin km
"0.0000"

获取元素位置-geopos

geopos 指令可以获取集合中任意元素的经纬度坐标，可以一次获取多个。

1
2
3
4
5
6
7
8
9
10
11
127.0.0.1:6379> geopos company juejin
1) 1) "116.48104995489120483"
   2) "39.99679348858259686"
127.0.0.1:6379> geopos company ireader
1) 1) "116.5142020583152771"
   2) "39.90540918662494363"
127.0.0.1:6379> geopos company juejin ireader
1) 1) "116.48104995489120483"
   2) "39.99679348858259686"
2) 1) "116.5142020583152771"
   2) "39.90540918662494363"

获取元素的 hash 值-geohash

1
2
3
4
127.0.0.1:6379> geohash company ireader
1) "wx4g52e1ce0"
127.0.0.1:6379> geohash company juejin
1) "wx4gd94yjn0"

附近元素-georadiusbymember

georadiusbymember 指令是最为关键的指令，它可以用来查询指定元素附近的其它元素，它的参数非常复杂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# 范围 20 公里以内最多 3 个元素按距离正排，它不会排除自身
127.0.0.1:6379> georadiusbymember company ireader 20 km count 3 asc
1) "ireader"
2) "juejin"
3) "meituan"
# 范围 20 公里以内最多 3 个元素按距离倒排
127.0.0.1:6379> georadiusbymember company ireader 20 km count 3 desc
1) "jd"
2) "meituan"
3) "juejin"
# 三个可选参数 withcoord withdist withhash 用来携带附加参数
# withdist 很有用，它可以用来显示距离
127.0.0.1:6379> georadiusbymember company ireader 20 km withcoord withdist withhash count 3 asc
1) 1) "ireader"
   2) "0.0000"
   3) (integer) 4069886008361398
   4) 1) "116.5142020583152771"
      2) "39.90540918662494363"
2) 1) "juejin"
   2) "10.5501"
   3) (integer) 4069887154388167
   4) 1) "116.48104995489120483"
      2) "39.99679348858259686"
3) 1) "meituan"
   2) "11.5748"
   3) (integer) 4069887179083478
   4) 1) "116.48903220891952515"
      2) "40.00766997707732031"