地理空間編碼算法之GeoHash
基本原理
通過一個給定的經(jīng)緯度坐標(biāo)(經(jīng)度 146.842813452468、緯度 -54.9432909847213)來介紹該算法的基本原理及流程
基于二分查找的經(jīng)緯度編碼
眾所周知，經(jīng)度范圍-180～180，緯度范圍-90～90。這里利用二分查找分別計算該經(jīng)緯度坐標(biāo)下經(jīng)度、緯度的編碼。其中，位于左區(qū)間、右區(qū)間的值分別記為0、1。下面即是對經(jīng)度146.842813452468進行區(qū)間二分的過程。這里左區(qū)間是左閉右開區(qū)間、右區(qū)間是左閉右閉區(qū)間
-----------------------------------------------------------------------------------------------
左區(qū)間 右區(qū)間 結(jié)果
-----------------------------------------------------------------------------------------------
[-180.000000000000000, 0.000000000000000) [ 0.000000000000000, 180.000000000000000] 1
[ 0.000000000000000, 90.000000000000000) [ 90.000000000000000, 180.000000000000000] 1
[ 90.000000000000000, 135.000000000000000) [ 135.000000000000000, 180.000000000000000] 1
[ 135.000000000000000, 157.500000000000000) [ 157.500000000000000, 180.000000000000000] 0
[ 135.000000000000000, 146.250000000000000) [ 146.250000000000000, 157.500000000000000] 1
[ 146.250000000000000, 151.875000000000000) [ 151.875000000000000, 157.500000000000000] 0
[ 146.250000000000000, 149.062500000000000) [ 149.062500000000000, 151.875000000000000] 0
[ 146.250000000000000, 147.656250000000000) [ 147.656250000000000, 149.062500000000000] 0
[ 146.250000000000000, 146.953125000000000) [ 146.953125000000000, 147.656250000000000] 0
[ 146.250000000000000, 146.601562500000000) [ 146.601562500000000, 146.953125000000000] 1
[ 146.601562500000000, 146.777343750000000) [ 146.777343750000000, 146.953125000000000] 1
[ 146.777343750000000, 146.865234375000000) [ 146.865234375000000, 146.953125000000000] 0
[ 146.777343750000000, 146.821289062500000) [ 146.821289062500000, 146.865234375000000] 1
[ 146.821289062500000, 146.843261718750000) [ 146.843261718750000, 146.865234375000000] 0
[ 146.821289062500000, 146.832275390625000) [ 146.832275390625000, 146.843261718750000] 1
[ 146.832275390625000, 146.837768554687500) [ 146.837768554687500, 146.843261718750000] 1
[ 146.837768554687500, 146.840515136718750) [ 146.840515136718750, 146.843261718750000] 1
[ 146.840515136718750, 146.841888427734380) [ 146.841888427734380, 146.843261718750000] 1
[ 146.841888427734380, 146.842575073242200) [ 146.842575073242200, 146.843261718750000] 1
[ 146.842575073242200, 146.842918395996100) [ 146.842918395996100, 146.843261718750000] 0
-----------------------------------------------------------------------------------------------
我們將每次二分的結(jié)果匯總起來，則該經(jīng)度編碼即為：11101000011010111110。同理，我們對緯度-54.9432909847213進行編碼，二分過程如下所示
-----------------------------------------------------------------------------------------------
左區(qū)間 右區(qū)間 結(jié)果
-----------------------------------------------------------------------------------------------
[ -90.000000000000000, 0.000000000000000) [ 0.000000000000000, 90.000000000000000] 0
[ -90.000000000000000, -45.000000000000000) [ -45.000000000000000, 0.000000000000000] 0
[ -90.000000000000000, -67.500000000000000) [ -67.500000000000000, -45.000000000000000] 1
[ -67.500000000000000, -56.250000000000000) [ -56.250000000000000, -45.000000000000000] 1
[ -56.250000000000000, -50.625000000000000) [ -50.625000000000000, -45.000000000000000] 0
[ -56.250000000000000, -53.437500000000000) [ -53.437500000000000, -50.625000000000000] 0
[ -56.250000000000000, -54.843750000000000) [ -54.843750000000000, -53.437500000000000] 0
[ -56.250000000000000, -55.546875000000000) [ -55.546875000000000, -54.843750000000000] 1
[ -55.546875000000000, -55.195312500000000) [ -55.195312500000000, -54.843750000000000] 1
[ -55.195312500000000, -55.019531250000000) [ -55.019531250000000, -54.843750000000000] 1
[ -55.019531250000000, -54.931640625000000) [ -54.931640625000000, -54.843750000000000] 0
[ -55.019531250000000, -54.975585937500000) [ -54.975585937500000, -54.931640625000000] 1
[ -54.975585937500000, -54.953613281250000) [ -54.953613281250000, -54.931640625000000] 1
[ -54.953613281250000, -54.942626953125000) [ -54.942626953125000, -54.931640625000000] 0
[ -54.953613281250000, -54.948120117187500) [ -54.948120117187500, -54.942626953125000] 1
[ -54.948120117187500, -54.945373535156250) [ -54.945373535156250, -54.942626953125000] 1
[ -54.945373535156250, -54.944000244140625) [ -54.944000244140625, -54.942626953125000] 1
[ -54.944000244140625, -54.943313598632810) [ -54.943313598632810, -54.942626953125000] 1
[ -54.943313598632810, -54.942970275878906) [ -54.942970275878906, -54.942626953125000] 0
[ -54.943313598632810, -54.943141937255860) [ -54.943141937255860, -54.942970275878906] 0
-----------------------------------------------------------------------------------------------
故，該緯度編碼即為：00110001110110111100
合并
對于經(jīng)度、緯度的編碼，我們按照經(jīng)度、緯度、經(jīng)度、緯度...順序，分別依次取一位進行合并。合并結(jié)果如下所示
Base32編碼
利用下述Base32編碼表，對合并后的經(jīng)緯度編碼按5位一組進行編碼
編碼過程如下所示
故，最終該經(jīng)緯度(經(jīng)度146.842813452468、緯度-54.9432909847213)的GeoHash值即為pq0rmmzs
Note
上文我們提到GeoHash算法計算出來的值實際上表示的是一個矩形網(wǎng)格的區(qū)域范圍。所以在上述區(qū)間二分的過程中，事實上可以不斷的持續(xù)下去，以獲得該經(jīng)(或緯)度更多位數(shù)的編碼值，進而縮小該GeoHash值所表示的區(qū)域范圍，從而能更準(zhǔn)確的反映出該經(jīng)緯度坐標(biāo)的位置
如果兩個網(wǎng)格的GeoHash值共同前綴越長，說明這兩個網(wǎng)格區(qū)域越接近。這也是為什么在地理信息空間通常將經(jīng)緯度坐標(biāo)轉(zhuǎn)換為GeoHash值可以提高查詢、檢索效率(前綴匹配)。但反之并不成立，即兩個很接近的網(wǎng)格區(qū)域，可能GeoHash值的共同前綴很短甚至完全沒有共同前綴。即所謂的邊緣場景，例如兩個很鄰近的區(qū)域如果分別在格林威治子午線(經(jīng)度為0)的兩側(cè)，顯然它們的GeoHash值完全沒有共同的前綴
GeoHash算法，事實上是空間填充曲線中Z階曲線(Z-Order Curve)的一種典型應(yīng)用
對于Redis而言，其從3.2開始增加了對空間地理位置的支持，提供了GeoHash數(shù)據(jù)類型。下面即是一個利用geoadd、geohash命令計算經(jīng)緯度坐標(biāo)的GeoHash值示例
