获取我附近的商店方法(二):GeoHash算法

 上一篇提到根据坐标获取附近的商店根据半径计算的方法,这一篇说一下目前比较常用的GeoHash方法,先简单介绍一下GeoHash算法:

认识GeoHash

 GeoHash算法将二维经纬度坐标直接转换成字符串,每一个字符串代表一个矩形区域,也就是说,这个矩形区域内所有的点(经纬度坐标)都共享相同的GeoHash字符串,字符串的长度越大,矩形的区域就越小,经度也就越高。字符串相似的表示距离相近,这样可以利用字符串的前缀匹配来查询附近的POI信息

GeoHash算法的步骤

 地球纬度区间是[-90,90],经度区间是[-180,180],通过区间法对经度和纬度分别进行计算,假如我们获取到的当前坐标为经度-0.12866, 纬度38.534413,以纬度为例:

  1. 将纬度平均分成两个区间:[-90,0),[0,90],成为左区间和右区间,可以判断出38.534413属于右区间,则值为1,(如果属于左区间则值为0);
  2. 接着将右区间继续划分,就变成了[0,45),[45,90],此时,38.534413属于左区间,则值为0
  3. 递归上述过程,则区间的值会越来越逼近38.534413
  4. 随着算法的进行,我们将会得到一个序列,序列的长度跟递归的次数有关,但是一定要保证的是经度和纬度的序列长度是一样的,我这里设置的递归长度是30,经度和纬度加起来就是60,
  5. 根据算法我们最终得到经度的序列为[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0],纬度的序列为[1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0],然后我们根据此序列再组合一个新的序列偶数位放经度,奇数位放纬度,把2串编码组合生成新串[0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0],实际上这个序列是一串二进制
  6. 最后,我们将这个新串转换成十进制再使用0-9、b-z(去掉a, i, l, o)对这组十进制进行编码得到的字符串eyzgjnfr4p0p就是最终的GeoHash编码。下图是网上给出的不同编码长度给出的精度:


 得到GeoHash的值之后可以同样的保存近数据库中,每次查询离我最近的数据的时候理论上来说可以根据精确度截取GeoHash的值进行模糊查询,但是这样查询是有问题的,因为你没法保证你每次查询时你的当前坐标刚好在这个矩形的正中间,如果你的坐标处在矩形的边界,那么你就无法获取其附近的数据,那么这个问题怎么解决呢?其实也很简单,以你当前所在位置的矩形为九宫格的中间格子,再获取其相邻的8个矩形。

 获取其他8个区域的GeoHash也很简单,上面的表已经给出了每一个区域内经度和纬度的宽度,那么直接加减后就可以得出周边相邻的8个格子,我这里自己写了一套GeoHash的算法,得出当前坐标的GeoHash的值以及相邻8个格子的值,代码比较多就不贴上来了,在GitHub上有一个别人写好的JAVA版本的可以直接拿来用,叫geohash-java,貌似maven的仓库中也有

<dependency>
    <groupId>ch.hsr</groupId>
    <artifactId>geohash</artifactId>
    <version>1.3.0</version>
</dependency>

使用的方法也很简单

GeoHash geoHash = GeoHash.withCharacterPrecision(38.534413, -0.12866, 12);
System.out.println(geoHash.toBase32());//获取当前的GeoHash的值
GeoHash[] adjacent = geoHash.getAdjacent();//获取整个九宫格的GeoHash的值
for (GeoHash hash : adjacent) {
  System.out.println(hash.toBase32());
}

那么获取到整个九宫格之后至于查询和排序就简单多了,这里不再赘述。