GeoHash处理经纬度，降维，空间填充曲线

个人博客：无奈何杨（wnhyang）

个人语雀：wnhyang

共享语雀：在线知识共享

Github：wnhyang - Overview

参考

https://segmentfault.com/a/1190000042971576

GeoHash原理以及代码实现_geohash编码-CSDN博客

GeoHash代码实现–java_geohash java代码示例-CSDN博客

在线经纬度距离计算

http://geohash.co/

https://geohash.jorren.nl/

简介

Geohash是一种用于标识地理位置的编码方法。它将经纬度坐标转换为一个简短的字符串，这个字符串可以用来表示地球上的任意位置。Geohash的特点是，编码的长度越长，表示的位置就越精确；反之，编码越短，则表示的位置范围就越大。

接下来我们来一起探究一下这是个什么东西，有什么用？

参考的文章讲的也是非常不错，这里就啰嗦整理一下，并引申一下了。

经纬度

首先必须要从经纬度开始，我们都知道为了标记我们在地球上的位置，出现了经纬度，南北方向叫做纬度[-90,90]，东西方向是经度[-180,180]。在使用具有定位功能的设备时，通过人造地球卫星就能确定我们在地球上的位置，其使用的都是经纬度。

GeoHash

GeoHash是一种地理编码，就是用于处理经纬度的。其原理是使用空间填充曲线—— Z 阶曲线（Z-order curve），在地球表面的经纬度球面坐标系下，划分出许许多多不规则矩形，并将每个矩形进行编码，表示某个经纬度范围的面，本质上就是一种降维打击方案。

如果你对hash比较敏感的话，就会联想到计算机科学中还有很多hash，Java顶级父类Object的hashcode，数据结构的hashcode，散列hash算法如：md5，hash负载均衡策略，等等。提到这些是为了重复强调一下相比于无序的hash算法，GeoHash是有序的，毕竟它存在的意义就是为了降维，降维是将(x,y)表示的二维坐标系的点转换为一条直线上的点，虽然信息丢失是不可避免的，但是保留信息就是降维的重要目的之一。如下图，将平面划分成矩形，并将其串联起来，最终拉成一条直线，其是有序的，信息从(x,y)变为[起点,终点]，实现了降维。

结论出发一般会有一个很大的问题：放弃思考，不再问为什么？

提出问题往往是进步的开始！

为什么这样的曲线是可行？空间填充曲线都有什么特点？

我并不能回答所有相关问题，但至少可以知道这样的曲线一定是可微分的，也就是能通过数学表达式表示的。而且其还能一定程度上的转换二维信息，比如：二维坐标系下很重要的距离问题，在降维后通过大小就能判断。

实现原理

经纬度转GeoHash

1、经纬度，按照[-90,90]，[-180,180]逐渐二分，在左区间为0，在右区间为1，得到二进制编码，具体要得到多少位的二进制，看选取的精度，5位二进制对应1位GeoHash

2、合并经纬度，偶数位放经度，奇数位放纬度，注意第一位是0，放偶数，简单理解，经度纬度经度纬度…叠加

3、每5位对应以为base32编码，转译一下就得到了GeoHash编码

GeoHash转经纬度

反之即可，只是GeoHash代码的是一块区域，转换后的经纬度是区域的中心点的经纬度。

参考网站：

http://geohash.co/

https://geohash.jorren.nl/

局限性

GeoHash是有序的，但本质上都是从二维平面到曲线，无论如何都是会丢失信息的。

边界问题

很容易理解，所有的区域划分问题都会存在这样的问题，如下图，相比如参考点，明显红点更近一些，但是通过GeoHash编码，结论就是绿色的点更近。

通常的解决方案是除了本身区域还要使用周围的相邻区域辅助判断计算。

非线性问题

要知道我们讨论的是地球这个三维球体的表面，抛开地球本身就是不规则球体不讲，就算是规则，肯定不能完全套用在球面上吧，这本身就不是矩形啊。球面距离公式也不是简单平方差开根号的吧。0纬度的赤道移动一个经度和30纬度移动一个经度差别也是可想而知的。

球面的必然问题

这是不可避免的问题，还是和前面一样的原因，我们目标是球面，其是无边的！

因为我们经纬度的划分规则，体现在了经度上，-180和180是一样的一条线。

GeoHash是无法理解-179和179是相近的。

意义

尽管GeoHash具有一些局限性，但是在现实中还是有很多用处的。

顺带一讲，Redis中的Geo也有使用GeoHash哦！

1、附近，在使用某些带有地图功能的软件时，查找附近距离最近的xxx，有可能就用到了GeoHash哦，原因也很简单，GeoHash极大的加快了检索速度，相比如球面距离计算可想而知对比一串字符串要简单的多。

2、聚集，想要统计某片区域有多少用户，就可以利用GeoHash将经纬度编码，然后取不同位数，做不同精度的统计。

代码实现

下面是优化了性能的代码实现，其中使用了一些位运算，不过效果是一致的。

public class GeoHash {/*** geoHash 32位*/private static final char[] BASE32 = {'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 static final double MIN_LAT = -90.0, MAX_LAT = 90.0;/*** 经度范围*/private static final double MIN_LON = -180.0, MAX_LON = 180.0;/*** 将给定的纬度和经度编码为GeoHash字符串，指定精度。** @param latitude  纬度[-90,90]* @param longitude 经度[-180,180]* @param precision 精度[1,12]* @return GeoHash字符串*/public static String encode(double latitude, double longitude, int precision) {if (latitude < MIN_LAT || latitude > MAX_LAT || longitude < MIN_LON || longitude > MAX_LON) {throw new IllegalArgumentException("Latitude and longitude must be within valid ranges.");}if (precision <= 0 || precision > 12) {throw new IllegalArgumentException("precision must between 1 and 12");}long geoHashBits = 0;boolean isEven = true;double minLat = MIN_LAT, maxLat = MAX_LAT;double minLon = MIN_LON, maxLon = MAX_LON;int bitIndex = 0;// 每个字符代表5位二进制数int requiredBits = precision * 5;while (bitIndex < requiredBits) {double midValue;if (isEven) {midValue = (minLon + maxLon) / 2;if (longitude > midValue) {geoHashBits |= (1L << (requiredBits - bitIndex - 1));minLon = midValue;} else {maxLon = midValue;}} else {midValue = (minLat + maxLat) / 2;if (latitude > midValue) {geoHashBits |= (1L << (requiredBits - bitIndex - 1));minLat = midValue;} else {maxLat = midValue;}}isEven = !isEven;bitIndex++;}return bitsToBase32(geoHashBits, precision);}/*** 将给定的二进制位转换为GeoHash字符串。** @param bits      二进制位* @param precision 精度* @return GeoHash字符串*/private static String bitsToBase32(long bits, int precision) {char[] base32Chars = new char[precision];for (int i = 0; i < precision; i++) {// Extract 5 bitsint index = (int) ((bits >>> (i * 5)) & 0x1F);base32Chars[precision - i - 1] = BASE32[index];}return new String(base32Chars);}/*** 将给定的经度和纬度转换为7位GeoHash字符串。** @param latitude  纬度[-90,90]* @param longitude 经度[-180,180]* @return GeoHash字符串*/public static String geoHash7(double latitude, double longitude) {return encode(latitude, longitude, 7);}public static void main(String[] args) {long start = System.currentTimeMillis();// GeoHash 字符串长度int precision = 9;//30.2549529076, 120.1646161079System.out.println(encode(30.2549958229, 120.1647019386, precision));System.out.println(geoHash7(30.2549958229, 120.1647019386));System.out.println("耗时：" + (System.currentTimeMillis() - start));}
}