GeoHash算法小记

本是古典何须时尚 2022-06-07 12:47 223阅读 0赞

昨天被问到一道题目，感觉挺有意思，这里记录一下:

题目:给定一个m\*m的矩形区域，已知一点的(x,y)坐标,如何找到离周围xkm的所有店家?

这里需要用到一个叫做GeoHash的算法。

这个算法是什么作用呢?

GeoHash可以将地图网格化，然后把一个位置的坐标转换成一个可以排序的，可以比较的字符串编码,说到底就是将一个二维的数据映射成一个一维的数据。

核心代码:

public static String GeohashEncode(double latitude,double longitude,int precision=12){
 boolean even=true;
 int bit=0;
 int ch=0;
 String geohash="";
 double[] lat={-90.0,90.0};
 double[] lon={-180.0,180.0};
 if(precision<1||precision>20) precision=12;
 while(geohash.length()<precision){
 double mid;
 if(even){
 mid=(lon[0]+lon[1])/2;
 if(longitude>mid){
 ch|=Bits[bit];
 lon[0]=mid;
 
 }
 else{
 lon[1]=mid;
 }
 }
 else{
 mid=(lon[0]+lon[1])/2;
 if(latitude>mid){
 ch|=Bits[bit];
 lat[0]=mid;
 }
 else{
 lat[1]=mid;
 }
 }
 even=!even;
 if(bit<4) bit++;
 else{
 geohash+=Base32[ch];
 bit=0;
 ch=0;
 
 }
 }
 return geohash;
 }

![1004194-20161220202300729-1590277913.jpg][]

结合上边的代码以及图示我们可以知道，算法的目的就是不断对(-90,90)和(-180,180)这两个区间进行划分,然后查看给定的坐标是不是在这个区间里边，如果在这个区间中,那么设置为1，如果不在这个区间中那么设置为0，直到划分的区间满足对应的精度结束循环，并且得到一串二进制数，然后再将这个二进制数变化成10进制的数，通过base32编码得到一串字符串。

base32编码表如下:

下面回到这个题目,题目要求我们找到所有距离坐标Xkm的商店,我们可以采取以下的方法:

以给定的点向外拓xkm，分别对周围8个坐标进行GeoHash(如下图),然后提取字符串的公共部分，最后查找周围点的GeoHash值以xx开头的就是满足题意的商家。

![Center][]

[1004194-20161220202300729-1590277913.jpg]: /images/20220607/10163b290bbc47cc930a99ac8b9bbfc1.png
[Center]: /images/20220607/7e797e7f28994e9fab4b3fb290ed2b8f.png