Redis GEO 地理位置的使用與原理解析以及Java實現GEOHash演算法

語言: CN / TW / HK

持續創作,加速成長!這是我參與「掘金日新計劃 · 6 月更文挑戰」的第25天,點選檢視活動詳情

詳細介紹了Redis GEO儲存地理位置資訊的使用方式以及基本原理,基於Java如何實現GEOHash演算法。

Redis GEO 主要用於儲存地理位置資訊,並對儲存的資訊進行操作,該功能在 Redis 3.2 版本新增。

Redis GEO可被用來計算兩個經緯度點位之間的物理距離,常見的應用就是“附近的人”的功能,搖一搖附近的人功能,或者外賣中的騎手等距客戶多少米的功能,或者周邊商家、車輛功能等等,需要計算真實距離的場景都可以使用。

在 Redis 6.2.0的版本中提供了8個相關的操作命令,而且都是很簡單的。

@[toc]

1 GEOADD新增座標

GEOADD key [NX|XX] [CH] longitude latitude member [longitude latitude member ...]

將指定的一個或者多個地理空間項(經度、緯度、名稱)新增到指定的key。資料作為排序集儲存在key中,這樣就可以使用 GEOSEARCH 和GEORADIUSBYMEMBER命令查詢這些專案。

該命令採用標準格式 x,y 的引數,因此必須在緯度之前指定經度。可編入索引的座標有限制:非常靠近極點的區域不可編入索引。

  1. 有效經度為 -180 到 180 度。
  2. 有效緯度是從 -85.05112878 到 85.05112878 度。

返回新新增到鍵裡面的空間元素數量,不包括那些已經存在但是被更新的元素。

當用戶嘗試索引指定範圍之外的座標時,該命令將報告錯誤。這裡沒有 GEODEL 命令,因為地理索引結構只是一個Sorted Set,因此可以使用 ZREM 刪除元素。

如下案例,我們嘗試新增幾個地理位置:故宮、天安門、日壇公園、天壇公園、北京站(https://jingweidu.bmcx.com/):

shell 127.0.0.1:6379> GEOADD test 116.397128 39.916527 gugong (integer) 1 127.0.0.1:6379> GEOADD test 116.39798630688475 39.90382054860711 tiananmen (integer) 1 127.0.0.1:6379> GEOADD test 116.44381989453123 39.915605367786505 ritangongyuan (integer) 1 127.0.0.1:6379> GEOADD test 116.41077507946775 39.88208903170563 tiantangongyuan (integer) 1 127.0.0.1:6379> GEOADD test 116.42699707958982 39.90273413640524 beijingzhan (integer) 1

2 GEOPOS獲取座標

GEOPOS key member [member ...]

返回由key的Sorted set表示的地理空間索引的要給或者多個指定成員的位置(經度、緯度)。

當通過 GEOADD 填充地理空間索引時,座標被轉換為 52 位 geohash,因此返回的座標可能不完全是用於新增元素的座標,可能會有小精度錯誤,也就是說值不一定是插入值。

獲取故宮、北京站和日壇公園的地理座標:

shell 127.0.0.1:6379> GEOPOS test gugong 1) 1) "116.39712899923324585" 2) "39.91652647362980844" 127.0.0.1:6379> GEOPOS test beijingzhan ritangongyuan 1) 1) "116.4269980788230896" 2) "39.90273505580184832" 2) 1) "116.44382089376449585" 2) "39.91560636984896604"

3 GEODIST計算距離

GEODIST key member1 member2 [m|km|ft|mi]

返回由Sorted set表示的地理空間索引中兩個成員之間的距離,這個命令非常有用。

如果缺少一個或兩個成員,則該命令返回 NULL。

單位必須是以下之一,預設為m(米),還有km(千米),mi(英里),ft(英尺)。

該命令假設地球是一個完美的球體來計算距離,因此在邊緣情況下可能會出現高達 0.5% 的誤差。

案例,計算故宮和北京站的距離:

shell 127.0.0.1:6379> GEODIST test gugong beijingzhan "2974.4056"

結果約2.974公里,差不多(線上經緯度距離計算https://www.hhlink.com/%E7%BB%8F%E7%BA%AC%E5%BA%A6):

在這裡插入圖片描述

4 GEOHASH獲取geohash

返回有效的 Geohash 字串,表示一個或多個元素在表示地理空間索引的Sortedset中的位置(其中元素是使用 GEOADD 新增的)。

通常 Redis 使用 Geohash 技術的變體來表示元素的位置,其中位置使用 52 位無符號二進位制整數進行編碼。與標準相比,編碼也不同,因為在編碼和解碼過程中使用的初始最小和最大座標不同。但是,此命令以 Wikipedia 文章(https://en.wikipedia.org/wiki/Geohash)中所述的字串形式返回標準 Geohash,並與 http://geohash.org/網站相容。

也就是說,我們獲取到某個座標的hash值之後,就能直接去http://geohash.org/${hash}網站定位它。

該命令返回 11 個字元的 Geohash 字串,因此與 Redis 內部 52 位表示相比沒有精度損失。返回的 Geohashes 具有以下屬性:

  1. 它們可以從右邊刪除字元以縮短,這會使得定位失去精度,但仍會指向同一區域。
  2. 可以在 geohash.org的URL中使用它們,例如http://geohash.org/%3Cgeohash-string>。
  3. 具有相似字首的字串在附近,但反之則不然,具有不同字首的字串也可能在附近。

我們獲取故宮的座標的hash:

shell 127.0.0.1:6379> GEOHASH test gugong 1) "wx4g0dtf9e0"

去定位一下http://geohash.org/wx4g0dtf96x: 在這裡插入圖片描述

有時候下面的小圖載入不出來,點選圖中的“google”試試: 在這裡插入圖片描述

確實定位是在故宮。

5 GEORADIUSBYMEMBER成員半徑搜尋

GEORADIUSBYMEMBER key member radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [COUNT count [ANY]] [ASC|DESC] [STORE key] [STOREDIST key]

GEORADIUSBYMEMBER以指定名字的成員的位置用作查詢的中心,返回距中心的最大距離(半徑)指定的區域的邊界內的其他成員。

此命令的常見用例是檢索指定點附近不超過給定米數(或其他單位)的地理空間專案。例如,這允許向移動使用者推薦附近地點的應用程式,比如附近的餐館、附近的人等。

半徑單位必須是以下之一,預設為m(米),還有km(千米),mi(英里),ft(英尺)。

該命令可選地使用以下引數,用於返回更多的附加資訊:

  1. WITHDIST: 還要返回距離指定中心的距離,距離以與指定為命令的半徑引數的單位相同的單位返回。
  2. WITHCOORD:還返回匹配專案的經度,緯度座標。
  3. WITHHASH:還以 52 位無符號二進位制數的十進位制整數的形式返回專案的原始 geohash 編碼的sorted set score,這僅對低階黑客或除錯有用,否則一般使用者幾乎沒有興趣。

命令預設是返回未排序的專案,可以使用以下兩個引數呼叫兩種不同的排序方法:

  1. ASC: 相對於中心,從最近到最遠對返回的專案進行排序.
  2. DESC: 相對於中心,從最遠到最近的順序對返回的專案進行排序。

預設情況下,返回所有匹配的專案。可以使用 COUNT N引數將結果限制為前 N 個匹配項。

當新增ANY 引數時,該命令將在找到足夠的匹配項後立即返回,因此結果可能不是最接近要求的結果,但另一方面,將顯著降低伺服器的工作量,這個命令對於一個很大的範圍的搜尋來說對於減輕伺服器壓力非常有用。

預設情況下,該命令將專案返回給客戶端,可以使用以下引數之一儲存結果:

  1. STORE: 將專案儲存在填充了其地理空間資訊的Sorted set中.
  2. STOREDIST: 將專案儲存在一個Sorted set中,該集合以它們與中心的距離作為浮點數填充,在半徑中指定的單位相同。

返回值:

  1. 沒有指定任何 WITH 選項,該命令只返回一個線性陣列,如 ["New York","Milan","Paris"]
  2. 如果指定了 WITHCOORD、WITHDIST 或 WITHHASH 選項,則該命令返回一個數組的陣列,其中每個子陣列代表一個專案。
  3. 子陣列最多包含四項元素:元素名、與中心的距離的浮點數,單位與引數指定的單位相同、geohash 整數、兩個元素的陣列(經度和緯度)。

由於 GEORADIUS 和 GEORADIUSBYMEMBER 具有 STORE 和 STOREDIST 選項,因此它們在技術上被標記為 Redis 命令表中的寫入命令。因此,Redis 叢集的從伺服器接到這兩命令時,會將它們重定向到主伺服器。

從 Redis 3.2.10 和 Redis 4.0.0 開始,Reids分別提供了可在從伺服器中使用的只讀命令GEORADIUS_RO和GEORADIUSBYMEMBER_RO來代替GEORADIUS和GEORADIUSBYMEMBER,這兩個只讀命令與原始命令完全相同,但拒絕 STORE 和 STOREDIST 選項,可以安全的在從伺服器中使用。

5.1 使用案例

返回距離故宮不超過3km的最近的一個點位(這裡的COUNT 後面的數字是2,因為ASC不會排除自身):

shell 127.0.0.1:6379> GEORADIUSBYMEMBER test gugong 3 km COUNT 2 ASC WITHDIST 1) 1) "gugong" 2) "0.0000" 2) 1) "tiananmen" 2) "1.4152"

可以看到,3km以內的距離故宮最近的點位是天安門,它們距離約1415m:

再返回距離故宮不超過3km的最遠的一個點位:

shell 127.0.0.1:6379> GEORADIUSBYMEMBER test gugong 3 km COUNT 1 DESC WITHDIST 1) 1) "beijingzhan" 2) "2.9744"

可以看到,3km以內的距離故宮最遠的點位是北京站,它們距離約2977m。

返回距離故宮不超過3km的最近的3個點位,展示全部附加內容:

shell 127.0.0.1:6379> GEORADIUSBYMEMBER test gugong 3 km COUNT 4 ASC WITHCOORD WITHDIST WITHHASH 1) 1) "gugong" 2) "0.0000" 3) (integer) 4069885548668386 4) 1) "116.39712899923324585" 2) "39.91652647362980844" 2) 1) "tiananmen" 2) "1.4152" 3) (integer) 4069885361351847 4) 1) "116.39798730611801147" 2) "39.9038199164580405" 3) 1) "beijingzhan" 2) "2.9744" 3) (integer) 4069885468202423 4) 1) "116.4269980788230896" 2) "39.90273505580184832"

返回距離故宮不超過5km的最近的3個點位,展示全部附加內容:

shell 127.0.0.1:6379> GEORADIUSBYMEMBER test gugong 5 km COUNT 4 ASC WITHCOORD WITHDIST WITHHASH 1) 1) "gugong" 2) "0.0000" 3) (integer) 4069885548668386 4) 1) "116.39712899923324585" 2) "39.91652647362980844" 2) 1) "tiananmen" 2) "1.4152" 3) (integer) 4069885361351847 4) 1) "116.39798730611801147" 2) "39.9038199164580405" 3) 1) "beijingzhan" 2) "2.9744" 3) (integer) 4069885468202423 4) 1) "116.4269980788230896" 2) "39.90273505580184832" 4) 1) "ritangongyuan" 2) "3.9846" 3) (integer) 4069885683167475 4) 1) "116.44382089376449585" 2) "39.91560636984896604"

6 GEORADIUS座標半徑搜尋

GEORADIUS key longitude latitude radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [COUNT count [ANY]] [ASC|DESC] [STORE key] [STOREDIST key]

該命令與 GEORADIUSBYMEMBER完全相同,唯一不同的是,它不以Sorted Set表示的地理空間索引中已存在的成員的名稱作為要查詢的區域的中心,而是以指定的經緯度值作為查詢區域中心。

在使用GEORADIUS時,只需要將點位的名字改為經緯度值即可。

shell 127.0.0.1:6379> GEOPOS test gugong 1) 1) "116.39712899923324585" 2) "39.91652647362980844" 127.0.0.1:6379> GEORADIUS test 116.39712899923324585 39.91652647362980844 3 km COUNT 2 ASC WITHDIST 1) 1) "gugong" 2) "0.0000" 2) 1) "tiananmen" 2) "1.4152"

在 Redis 6.2.0的版本中,GEORADIUS 命令系列被視為已棄用,在新程式碼中優先選擇 GEOSEARCH 和 GEOSEARCHSTORE。

7 GEOSEARCH指定區域搜尋

GEOSEARCH key [FROMMEMBER member] [FROMLONLAT longitude latitude] [BYRADIUS radius m|km|ft|mi] [BYBOX width height m|km|ft|mi] [ASC|DESC] [COUNT count [ANY]] [WITHCOORD] [WITHDIST] [WITHHASH]

Redis 6.2 新增的命令。返回使用 GEOADD填充的地理空間資訊的Sorted set的成員,這些成員位於給定形狀指定的區域的邊界內。

該命令擴充套件了 GEORADIUS 命令,因此除了在圓形區域內搜尋外,它還支援在矩形區域內搜尋。應使用此命令代替已棄用的 GEORADIUS 和 GEORADIUSBYMEMBER 命令。

查詢的中心點由以下強制性引數之一提供:

  1. FROMMEMBER: 使用給定在的現有Sorted set中的成員的位置。
  2. FROMLONLAT: 使用給定的經度和緯度確定的位置。

這兩個引數使得GEOSEARCH完全替代了GEORADIUS 和 GEORADIUSBYMEMBER 命令。

查詢的形狀由以下強制性引數之一提供:

  1. BYRADIUS: 與 GEORADIUS 類似,根據給定的radius半徑在圓形區域內搜尋。
  2. BYBOX: 在軸對齊的矩形內搜尋,由height長和width確定長和寬。

該命令可選地使用以下引數,用於返回更多的附加資訊:WITHDIST、WITHCOORD、WITHHASH。其含義與在GEORADIUS和GEORADIUSBYMEMBER命令中的使用一致。

命令預設是返回未排序的專案。可以使用以下兩個引數呼叫兩種不同的排序方法:ASC、DESC。其含義與在GEORADIUS和GEORADIUSBYMEMBER命令中的使用一致。

其他命令引數,如COUNT N、ANY、STORE、STOREDIST等的含義與在GEORADIUS和GEORADIUSBYMEMBER命令中的使用一致。

返回值的格式與在GEORADIUS和GEORADIUSBYMEMBER命令中的使用一致。

相比於GEORADIUS和GEORADIUSBYMEMBER,該命令沒有提供STORESTOREDIST選項,因此是一個真正的只讀命令,可以在從伺服器中直接使用。

我們搜尋以故宮為中心,半徑為3km的圓形範圍內的目標:

shell 127.0.0.1:6379> GEOSEARCH test FROMMEMBER gugong BYRADIUS 3 km ASC COUNT 5 WITHDIST 1) 1) "gugong" 2) "0.0000" 2) 1) "tiananmen" 2) "1.4152" 3) 1) "beijingzhan" 2) "2.9744"

我們搜尋以故宮為中心,長寬為3km的矩形範圍內的目標:

shell 127.0.0.1:6379> GEOSEARCH test FROMMEMBER gugong BYBOX 3 3 km ASC COUNT 5 WITHDIST 1) 1) "gugong" 2) "0.0000" 2) 1) "tiananmen" 2) "1.4152"

很明顯,選擇不同的形狀,將可能返回不同的結果。

8 GEOSEARCHSTORE搜尋並存儲

GEOSEARCHSTORE destination source [FROMMEMBER member] [FROMLONLAT longitude latitude] [BYRADIUS radius m|km|ft|mi] [BYBOX width height m|km|ft|mi] [ASC|DESC] [COUNT count [ANY]] [STOREDIST]

Redis 6.2 新增的命令。此命令類似於 GEOSEARCH,但只是將結果儲存在目標key中,此命令代替現已棄用的 GEORADIUS 和 GEORADIUSBYMEMBER,這是一個寫命令。

預設情況下,它將結果與其地理空間資訊一起儲存在目標Sorted set中,score是geohash的52 位無符號二進位制數的十進位制形式。使用 STOREDIST 選項時,該命令將專案儲存在一個Sorted set集中,該Sorted set中填充了它們與圓或框中心的距離浮點數作為score,單位是指定的半徑單位。

如下案例,我們將以故宮為中心,半徑為3km的所有座標儲存在一個新的test2的Sorted set集合中,score為geohash的整數形式:

shell 127.0.0.1:6379> GEOSEARCHSTORE test2 test FROMMEMBER gugong BYRADIUS 3 km ASC (integer) 3 127.0.0.1:6379> ZRANGE test2 0 -1 WITHSCORES 1) "tiananmen" 2) "4069885361351847" 3) "beijingzhan" 4) "4069885468202423" 5) "gugong" 6) "4069885548668386"

如果我們加上STOREDIST選項,那麼新的Sorted set中的score就是距離,其單位與GEOSEARCHSTORE中指定的單位相同:

shell 127.0.0.1:6379> GEOSEARCHSTORE test2 test FROMMEMBER gugong BYRADIUS 3 km ASC STOREDIST (integer) 3 127.0.0.1:6379> ZRANGE test2 0 -1 WITHSCORES 1) "gugong" 2) "0" 3) "tiananmen" 4) "1.4151991392787893" 5) "beijingzhan" 6) "2.9744056471131772"

9 Redis GEO的原理

經緯度是經度與緯度的合稱組成一個座標系統,稱為地理座標系統,它是一種利用三度空間的球面來定義地球上的空間的球面座標系統,經度範圍是東經180到西經180,緯度範圍是南緯90到北緯90,我們設定西經為負,南緯為負,所以地球上的經度範圍就是[-180, 180],緯度範圍就是[-90,90]。

經緯度能夠標示地球上除了南北極點的任何一個位置,因為南北極是一個點,所有經線交匯於極點,極點的經度可以表示為0度到180度之間(東經)和0度到-180度之間(西經)的任意值。

9.1 GeoHash演算法的簡介

GeoHash是一種地址編碼方法,他能夠把二維的空間經緯度資料編碼成一個字串。Geohash比直接用經緯度的高效很多,而且使用者可以釋出地址編碼,既能表明自己位於北海公園附近,又不至於暴露自己的精確座標,有助於隱私保護。

GeoHash演算法分為三步,我們以故宮的座標(116.397128, 39.916527)為例子進行講解。

第一步:將經度和緯度使用極限逼近演算法轉換為二進位制數,這一步也採用了二分法的思想,以經度116.397128為例子:

  1. 將區間[-180,180]進行二分得到[-180,0),[0,180]兩個區間,設左區間的位為0,右邊區間的位為1,116.397128屬於右區間,那麼轉換為二進位制數的第1位為1。
  2. 將右區間[0,180]進行二分得到[0,90),[90,180]兩個區間,同理,116.397128屬於右區間,那麼轉換為二進位制數的第2位為1。
  3. 將右區間[90,180]進行二分得到[90,135),[135,180]兩個區間,同理,116.397128屬於左區間,那麼轉換為二進位制數的第3位為0。
  4. 將左區間[90,135)進行二分得到[90,112.5],[112.5,135)兩個區間,同理,116.397128屬於右區間,那麼轉換為二進位制數的第4位為1。
  5. 將右區間[112.5,135)進行二分得到[112.5,123.75),[123.75,135)兩個區間,同理,116.397128屬於左區間,那麼轉換為二進位制數的第5位為0。
  6. 將左區間[112.5,123.75)進行二分得到[112.5,118.125),[118.125,123.75)兩個區間,同理,116.397128屬於左區間,那麼轉換為二進位制數的第6位為0。

這樣不斷地進行二分下去,二分的次數越多,所得到的區間也就越逼近於真實的經度或者緯度值,最終得到的GeoHash定位也就越準確,範圍也就越小。

在 Redis 中,經緯度使用 52 位的無符號整數進行整體編碼。經過26次的二分法,最終得到的經度的26位的二進位制數就是:11010010110001010111001101,得到的緯度的26位的二進位制數就是10111000110001010010100111。

第二步:將經度和緯度的二進位制編碼從頭開始一位一位的合併,經度佔奇數位,緯度佔偶數位,最終得到的一個52位的無符號數:1110011101001000111100000011001100101110010010110111。

第三步,對得到的合併二進位制編碼進行Base32編碼(編碼表字符集有32個字元,0\~9,a\~z,去掉 a/i/l/o四個容易混淆的字母,編碼時以每五個位進行一次編碼,不夠的填充0),讓它變成一個真正的字串,最終的結果就是“wx4g0dtf9e3”,這就是我們獲取到的故宮的geihash值。可以看到該值與Redis GEO計算的值“wx4g0dtf9e0”有些許區別,因為各種GEO的實現稍有不同,但是最終的定位位置都會是在故宮的。

我們開啟http://geohash.org/wx4g0dtf9e3開啟,點選google,結果如下:

在這裡插入圖片描述 確實定位在故宮!

我們再換一個日壇公園的地址(116.44381989453123, 39.915605367786505),計算得到的geoHash為wx4g1drv382,和Redis GEO的計算結果“wx4g1drv380”差不多,同樣http://geohash.org/wx4g1drv382也能夠定位到日壇公園:

在這裡插入圖片描述 經過GeoHash演算法,二維的經緯度點位就能夠變成一個非常好儲存且保密性比較好的字串的形式,Redis GEO同樣採用了上面這種GeoHash演算法,並且將最終的資料存入一個Sorted set集合中,集合的每一個元素就是存入的座標的名字(比如gugong、ritangongyuan),每個元素的score則是經緯度的52位的無符號geoHash編碼的10進位制整數形式。

9.2 GeoHash演算法的Java實現

下面是GeoHash演算法的簡單Java實現。

```java /* * @author lx / public class GEOHash { static final String ONE = "1"; static final String ZERO = "0"; static final String TWO = "2"; static final String LONGITUDE_MAX = "180"; static final String LONGITUDE_MIN = "-180"; static final String LATITUDE_MAX = "90"; static final String LATITUDE_MIN = "-90"; static final int BIN_NUM = 26; static final int MERGE_BIN_NUM = 26 << 1;

/**
 * Base32編碼的字串池
 */
private final static char[] BASE_32_CHARS = {'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'};

/**
 * 與十進位制值的對應關係
 */
final static HashMap<Character, Integer> BASE_32_LOOKUP = new HashMap<Character, Integer>();


static {
    int i = 0;
    for (char c : BASE_32_CHARS) {
        BASE_32_LOOKUP.put(c, i++);
    }
}

public static void main(String[] args) {
    String longitude = getBin("116.44381989453123", true);
    System.out.println("longitudebin: " + longitude);
    String latitude = getBin("39.915605367786505", false);
    System.out.println("latitudebin: " + latitude);
    String merge = merge(longitude, latitude);
    System.out.println("mergebin: " + merge);
    String geoHash = base32Encode(merge);
    System.out.println("geohash: " + geoHash);
    double[] doubles = base32Decode(geoHash);
    System.out.println("longitude: " + doubles[0] + ",  latitude: " + doubles[1]);
}

/**
 * 經緯度的二進位制編碼
 */
private static String getBin(String longitudeOrLatitude, boolean isLongitudeOrLatitude) {
    String min, max;
    if (isLongitudeOrLatitude) {
        max = LONGITUDE_MAX;
        min = LONGITUDE_MIN;
    } else {
        max = LATITUDE_MAX;
        min = LATITUDE_MIN;
    }
    BigDecimal num = new BigDecimal(longitudeOrLatitude);
    BigDecimal two = new BigDecimal(TWO), x, y, z;
    StringBuilder stringBuilder = new StringBuilder();
    if (num.compareTo(new BigDecimal(ZERO)) >= 0) {
        stringBuilder.append(ONE);
        x = new BigDecimal(ZERO);
        y = new BigDecimal(max);
    } else {
        stringBuilder.append(ZERO);
        x = new BigDecimal(min);
        y = new BigDecimal(ZERO);
    }
    z = x.add(y).divide(two);
    for (int i = 1; i < 26; i++) {
        if (num.compareTo(z) >= 0) {
            stringBuilder.append(ONE);
            x = z;
            z = x.add(y).divide(two);
        } else {
            stringBuilder.append(ZERO);
            y = z;
            z = x.add(y).divide(two);
        }
    }
    return stringBuilder.toString();
}

/**
 * 合併經緯度的二進位制編碼
 */
private static String merge(String longitude, String latitude) {
    StringBuilder stringBuilder = new StringBuilder();
    for (int i = 0; i < BIN_NUM; i++) {
        stringBuilder.append(longitude.charAt(i));
        stringBuilder.append(latitude.charAt(i));
    }
    return stringBuilder.toString();
}


/**
 * geohash編碼
 */
public static String base32Encode(String longitudeAndLatitudeBinCode) {
    StringBuilder geohash = new StringBuilder();
    for (int i = 0; i < MERGE_BIN_NUM; ) {
        int j = i;
        String substring;
        if ((i += 5) > MERGE_BIN_NUM) {
            substring = longitudeAndLatitudeBinCode.substring(j, MERGE_BIN_NUM);
        } else {
            substring = longitudeAndLatitudeBinCode.substring(j, i);
        }
        int i1 = Integer.parseInt(substring, 2);
        geohash.append(BASE_32_CHARS[i1]);
    }
    return geohash.toString();
}

/**
 * geohash解碼
 */
public static double[] base32Decode(String geohash) {
    StringBuilder buffer = getBin(geohash);
    BitSet lonset = new BitSet();
    BitSet latset = new BitSet();

    //偶數位,經度
    int j = 0;
    for (int i = 0; i < MERGE_BIN_NUM; i += 2) {
        boolean isSet = false;
        if (i < buffer.length()) {
            isSet = buffer.charAt(i) == '1';
        }
        lonset.set(j++, isSet);
    }

    //奇數位,緯度
    j = 0;
    for (int i = 1; i < MERGE_BIN_NUM; i += 2) {
        boolean isSet = false;
        if (i < buffer.length()) {
            isSet = buffer.charAt(i) == '1';
        }
        latset.set(j++, isSet);
    }

    double lon = base32Decode(lonset, new BigDecimal(LONGITUDE_MIN), new BigDecimal(LONGITUDE_MAX));
    double lat = base32Decode(latset, new BigDecimal(LATITUDE_MIN), new BigDecimal(LATITUDE_MAX));

    return new double[]{lon, lat};
}

private static StringBuilder getBin(String geohash) {
    StringBuilder buffer = new StringBuilder();
    for (char c : geohash.toCharArray()) {
        int i = BASE_32_LOOKUP.get(c) + 32;
        buffer.append(Integer.toString(i, 2).substring(1));
    }
    return buffer;
}


private static double base32Decode(BitSet bs, BigDecimal floor, BigDecimal ceiling) {
    BigDecimal two = new BigDecimal(TWO);
    BigDecimal mid = new BigDecimal(ZERO);
    for (int i = 0; i < bs.length(); i++) {
        mid = (floor.add(ceiling).divide(two, 17, ROUND_HALF_EVEN));
        if (bs.get(i)) {
            floor = mid;
        } else {
            ceiling = mid;
        }
    }
    return mid.doubleValue();
}

} ```

9.3 GeoHash演算法的原理

為什麼對經度和緯度進行二分然後再合併、編碼後,就能使用一個一維的字串表示一個二維的區域(點)呢?這個問題我們使用圖解來回答。

首先,經緯度兩個數值可以完美的對映到一個封閉的二維的平面直角座標系中: 在這裡插入圖片描述

圖中地球上的每一個點位的經緯度(極點除外)都能在上面封閉的圖形內部找到。

根據我們此前提到的二分法,區間更小的為二進位制數為0,更大的二進位制數為1,如果分別對經度和緯度進行一次二分,那麼經緯度的合併GeoHash二進位制編碼(經度和緯度的GeoHash編碼長度分別為1)如下:

在這裡插入圖片描述

如上圖,整個經緯度平面分為四塊,每一塊都是用不同的二進位制編碼,所以說,這個GeoHash實際上是代表著一個區域的編碼,而不是某個“點位”,只不過,當這個區域劃分得足夠的小,那麼就會無限趨近於一個點,定位也就越精準。

上圖僅僅經歷了一次二分,地球平面僅僅被分為四塊,可以想象,這是遠遠達不到我們所需的精度的要求的。那麼如果我們對經緯度進行兩次二分呢?注意,每一次二分都是使用上一次二分得到的最小區域進行二分的: 在這裡插入圖片描述

對經緯度分別進行兩次二分之後,經緯度的合併GeoHash二進位制編碼(經度和緯度的GeoHash編碼長度分別為1)長度增長了一倍,整個地球平面即被劃分為16塊。

設經過x次數劃分,那麼合併GeoHash二進位制編碼長度y,x和y的關係為y=2*x。設整個地球平面就會被分為m塊,那麼x和m的關係為:m=4^x,這個函式的影象如下:

在這裡插入圖片描述

這是一個非常恐怖的指數函式,這類似於細胞分裂,隨著x的增加,m的結果增加得越來越快,不需要經過很多次的二分法,即可把地球平面劃分為足夠小的滿足經度需求的多個區域,下面的誤差對照表(https://en.wikipedia.org/wiki/Geohash):

在這裡插入圖片描述

從圖中可大概推算,緯度每隔0.00001度,距離相差約1.1米;經度每隔0.00001度,距離相差約1米。

在我們的GeoHash的Java實現中,對經緯度分別採用了26次二分,經緯度的編碼長度都為26位,合起來之後GeoHash的編碼的二進位制長度為52位,轉換為Base32編碼的字串長度為11(每5位進行一次編碼,不夠的補0),從圖中可知此時誤差不超過0.0001492km,即0.1492m,由於GepHash的長度沒有達到55位,因此精度會低一些,但是不會超過0.5971m(為了效能考慮)。

以上這點誤差(不超過1m)對於我們日常使用的:附近的人、附近的商店、加油站、騎手距離等功能來說,完全足夠了,Redis GEO的GeoHash的二進位制長度也是52位,編碼後的字串長度也是11位。

相關文章:

  1. https://redis.io

如有需要交流,或者文章有誤,請直接留言。另外希望點贊、收藏、關注,我將不間斷更新各種Java學習部落格!