http://www.cnblogs.com/LBSer/p/3310455.html
引子
機機是個好動又好學的孩子,平日裡就喜歡拿着手機地圖點點按按來查詢一些好玩的東西。某一天機機到北海公園遊玩,肚肚餓了,于是乎打開手機地圖,搜尋北海公園附近的餐館,并選了其中一家用餐。
飯飽之後機機開始反思了,地圖背景如何根據自己所在位置查詢來查詢附近餐館的呢?苦思冥想了半天,機機想出了個方法:計算所在位置P與北京所有餐館的距離,然後傳回距離<=1000米的餐館。小得意了一會兒,機機發現北京的餐館何其多啊,這樣計算不得了,于是想了,既然知道經緯度了,那它應該知道自己在西城區,那應該計算所在位置P與西城區所有餐館的距離啊,機機運用了遞歸的思想,想到了西城區也很多餐館啊,應該計算所在位置P與所在街道所有餐館的距離,這樣計算量又小了,效率也提升了。
機機的計算思想很樸素,就是通過過濾的方法來減小參與計算的餐館數目,從某種角度上講,機機在使用索引技術。
一提到索引,大家腦子裡馬上浮現出B樹索引,因為大量的資料庫(如MySQL、oracle、PostgreSQL等)都在使用B樹。B樹索引本質上是對索引字段進行排序,然後通過類似二分查找的方法進行快速查找,即它要求索引的字段是可排序的,一般而言,可排序的是一維字段,比如時間、年齡、薪水等等。但是對于空間上的一個點(二維,包括經度和緯度),如何排序呢?又如何索引呢?解決的方法很多,下文介紹一種方法來解決這一問題。
思想:如果能通過某種方法将二維的點資料轉換成一維的資料,那樣不就可以繼續使用B樹索引了嘛。那這種方法真的存在嘛,答案是肯定的。目前很火的GeoHash算法就是運用了上述思想,下面我們就開始GeoHash之旅吧。
一、感性認識GeoHash
首先來點感性認識,http://openlocation.org/geohash/geohash-js/ 提供了在地圖上顯示geohash編碼的功能。
1)GeoHash将二維的經緯度轉換成字元串,比如下圖展示了北京9個區域的GeoHash字元串,分别是WX4ER,WX4G2、WX4G3等等,每一個字元串代表了某一矩形區域。也就是說,這個矩形區域内所有的點(經緯度坐标)都共享相同的GeoHash字元串,這樣既可以保護隐私(隻表示大概區域位置而不是具體的點),又比較容易做緩存,比如左上角這個區域内的使用者不斷發送位置資訊請求餐館資料,由于這些使用者的GeoHash字元串都是WX4ER,是以可以把WX4ER當作key,把該區域的餐館資訊當作value來進行緩存,而如果不使用GeoHash的話,由于區域内的使用者傳來的經緯度是各不相同的,很難做緩存。
2)字元串越長,表示的範圍越精确。如圖所示,5位的編碼能表示10平方千米範圍的矩形區域,而6位編碼能表示更精細的區域(約0.34平方千米) 3)字元串相似的表示距離相近(特殊情況後文闡述),這樣可以利用字元串的字首比對來查詢附近的POI資訊。如下兩個圖所示,一個在城區,一個在郊區,城區的GeoHash字元串之間比較相似,郊區的字元串之間也比較相似,而城區和郊區的GeoHash字元串相似程度要低些。城區 | 郊區 |
通過上面的介紹我們知道了GeoHash就是一種将經緯度轉換成字元串的方法,并且使得在大部分情況下,字元串字首比對越多的距離越近,回到我們的案例,根據所在位置查詢來查詢附近餐館時,隻需要将所在位置經緯度轉換成GeoHash字元串,并與各個餐館的GeoHash字元串進行字首比對,比對越多的距離越近。
二、GeoHash算法的步驟
下面以北海公園為例介紹GeoHash算法的計算步驟
2.1. 根據經緯度計算GeoHash二進制編碼
地球緯度區間是[-90,90], 北海公園的緯度是39.928167,可以通過下面算法對緯度39.928167進行逼近編碼:
1)區間[-90,90]進行二分為[-90,0),[0,90],稱為左右區間,可以确定39.928167屬于右區間[0,90],給标記為1;
2)接着将區間[0,90]進行二分為 [0,45),[45,90],可以确定39.928167屬于左區間 [0,45),給标記為0;
3)遞歸上述過程39.928167總是屬于某個區間[a,b]。随着每次疊代區間[a,b]總在縮小,并越來越逼近39.928167;
4)如果給定的緯度x(39.928167)屬于左區間,則記錄0,如果屬于右區間則記錄1,這樣随着算法的進行會産生一個序列1011100,序列的長度跟給定的區間劃分次數有關。
根據緯度算編碼
bit | min | mid | max |
1 | -90.000 | 0.000 | 90.000 |
45.000 | |||
22.500 | |||
33.750 | |||
39.375 | |||
42.188 | |||
40.7815 | |||
40.07825 | |||
39.726625 | |||
39.9024375 |
同理,地球經度區間是[-180,180],可以對經度116.389550進行編碼。
根據經度算編碼
-180 | 180 | ||
135 | |||
112.5 | |||
123.75 | |||
118.125 | |||
115.3125 | |||
116.71875 | |||
116.015625 | |||
116.3671875 |
2.2. 組碼
通過上述計算,緯度産生的編碼為10111 00011,經度産生的編碼為11010 01011。偶數位放經度,奇數位放緯度,把2串編碼組合生成新串:11100 11101 00100 01111。
最後使用用0-9、b-z(去掉a, i, l, o)這32個字母進行base32編碼,首先将11100 11101 00100 01111轉成十進制,對應着28、29、4、15,十進制對應的編碼就是wx4g。同理,将編碼轉換成經緯度的解碼算法與之相反,具體不再贅述。
三、GeoHash Base32編碼長度與精度
下表摘自維基百科:http://en.wikipedia.org/wiki/Geohash
可以看出,當geohash base32編碼長度為8時,精度在19米左右,而當編碼長度為9時,精度在2米左右,編碼長度需要根據資料情況進行選擇。
三、GeoHash算法
上文講了GeoHash的計算步驟,僅僅說明是什麼而沒有說明為什麼?為什麼分别給經度和次元編碼?為什麼需要将經緯度兩串編碼交叉組合成一串編碼?本節試圖回答這一問題。
如圖所示,我們将二進制編碼的結果填寫到空間中,當将空間劃分為四塊時候,編碼的順序分别是左下角00,左上角01,右下腳10,右上角11,也就是類似于Z的曲線,當我們遞歸的将各個塊分解成更小的子塊時,編碼的順序是自相似的(分形),每一個子快也形成Z曲線,這種類型的曲線被稱為Peano空間填充曲線。
這種類型的空間填充曲線的優點是将二維空間轉換成一維曲線(事實上是分形維),對大部分而言,編碼相似的距離也相近, 但Peano空間填充曲線最大的缺點就是突變性,有些編碼相鄰但距離卻相差很遠,比如0111與1000,編碼是相鄰的,但距離相差很大。
除Peano空間填充曲線外,還有很多空間填充曲線,如圖所示,其中效果公認較好是Hilbert空間填充曲線,相較于Peano曲線而言,Hilbert曲線沒有較大的突變。為什麼GeoHash不選擇Hilbert空間填充曲線呢?可能是Peano曲線思路以及計算上比較簡單吧,事實上,Peano曲線就是一種四叉樹線性編碼方式。
四、使用注意點
1)由于GeoHash是将區域劃分為一個個規則矩形,并對每個矩形進行編碼,這樣在查詢附近POI資訊時會導緻以下問題,比如紅色的點是我們的位置,綠色的兩個點分别是附近的兩個餐館,但是在查詢的時候會發現距離較遠餐館的GeoHash編碼與我們一樣(因為在同一個GeoHash區域塊上),而較近餐館的GeoHash編碼與我們不一緻。這個問題往往産生在邊界處。
解決的思路很簡單,我們查詢時,除了使用定位點的GeoHash編碼進行比對外,還使用周圍8個區域的GeoHash編碼,這樣可以避免這個問題。
2)我們已經知道現有的GeoHash算法使用的是Peano空間填充曲線,這種曲線會産生突變,造成了編碼雖然相似但距離可能相差很大的問題,是以在查詢附近餐館時候,首先篩選GeoHash編碼相似的POI點,然後進行實際距離計算。
geohash隻是空間索引的一種方式,特别适合點資料,而對線、面資料采用R樹索引更有優勢(可參考:深入淺出空間索引:為什麼需要空間索引)。
參考文獻:
http://en.wikipedia.org/wiki/Geohash
http://openlocation.org/geohash/geohash-js/
Cantor空間填充曲線之演算法探討.pdf
轉載請标明源位址:http://www.cnblogs.com/LBSer