Geohash原理

1. 引言

????????GeoHash本質(zhì)上是空間索引的一種方式届惋,其基本原理是將地球理解為一個(gè)二維平面髓帽,將平面遞歸分解成更小的子塊,每個(gè)子塊在一定經(jīng)緯度范圍內(nèi)擁有相同的編碼脑豹。以GeoHash方式建立空間索引郑藏,可以提高對(duì)空間poi數(shù)據(jù)進(jìn)行經(jīng)緯度檢索的效率。

2.認(rèn)識(shí)GeoHash

????????GeoHash將二維的經(jīng)緯度轉(zhuǎn)換成字符串瘩欺,比如下圖展示了北京9個(gè)區(qū)域的GeoHash字符串必盖,分別是WX4ER,WX4G2俱饿、WX4G3等等歌粥,每一個(gè)字符串代表了某一矩形區(qū)域。也就是說拍埠,這個(gè)矩形區(qū)域內(nèi)所有的點(diǎn)(經(jīng)緯度坐標(biāo))都共享相同的GeoHash字符串失驶,這樣既可以保護(hù)隱私(只表示大概區(qū)域位置而不是具體的點(diǎn)),又比較容易做緩存械拍。

????????Geohash編碼中突勇,字符串相似的表示距離相近(特殊情況后文闡述),這樣可以利用字符串的前綴匹配來查詢附近的POI信息坷虑。如下兩個(gè)圖所示甲馋,一個(gè)在城區(qū),一個(gè)在郊區(qū)迄损,城區(qū)的GeoHash字符串之間比較相似定躏,郊區(qū)的字符串之間也比較相似,而城區(qū)和郊區(qū)的GeoHash字符串相似程度要低些芹敌。此外痊远,不同的編碼長(zhǎng)度,表示不同的范圍區(qū)間氏捞,字符串越長(zhǎng)碧聪,表示的范圍越精確。

3.?GeoHash算法

????????以經(jīng)緯度值:(116.389550液茎, 39.928167)進(jìn)行算法說明逞姿,對(duì)緯度39.928167進(jìn)行逼近編碼 (地球緯度區(qū)間是[-90,90]

????a. 區(qū)間[-90,90]進(jìn)行二分為[-90,0),[0,90],稱為左右區(qū)間捆等,可以確定39.928167屬于右區(qū)間[0,90]滞造,給標(biāo)記為1

????b. 接著將區(qū)間[0,90]進(jìn)行二分為 [0,45),[45,90],可以確定39.928167屬于左區(qū)間 [0,45)栋烤,給標(biāo)記為0

????c. 遞歸上述過程39.928167總是屬于某個(gè)區(qū)間[a,b]谒养。隨著每次迭代區(qū)間[a,b]總在縮小,并越來越逼近39.928167

? ? d. 如果給定的緯度x(39.928167)屬于左區(qū)間明郭,則記錄0买窟,如果屬于右區(qū)間則記錄1丰泊,序列的長(zhǎng)度跟給定的區(qū)間劃分次數(shù)有關(guān),如下圖

????????e. 同理始绍,地球經(jīng)度區(qū)間是[-180,180]趁耗,可以對(duì)經(jīng)度116.389550進(jìn)行編碼。通過上述計(jì)算疆虚, 緯度產(chǎn)生的編碼為1 1 0 1 0 0 1 0 1 1 0 0 0 1 0苛败,經(jīng)度產(chǎn)生的編碼為1 0 1 1 1 0 0 0 1 1 0 0 0 ?1 1

????????f. 合并:偶數(shù)位放經(jīng)度,奇數(shù)位放緯度径簿,把2串編碼組合生成新串如下圖

????????g. 首先將11100 11101 00100 01111 0000 ?01101轉(zhuǎn)成十進(jìn)制罢屈,對(duì)應(yīng)著28、29篇亭、4缠捌、15,0译蒂,13 十進(jìn)制對(duì)應(yīng)的base32編碼就是wx4g0e,如下圖.

? ? ? ? ?h. 同理曼月,將編碼轉(zhuǎn)換成經(jīng)緯度的解碼算法與之相反

4.?GeoHash原理

????????Geohash其實(shí)就是將整個(gè)地圖或者某個(gè)分割所得的區(qū)域進(jìn)行一次劃分,由于采用的是base32編碼方式,即Geohash中的每一個(gè)字母或者數(shù)字(如wx4g0e中的w)都是由5bits組成(2^5 = 32,base32)执虹,這5bits可以有32中不同的組合(0~31),這樣我們可以將整個(gè)地圖區(qū)域分為32個(gè)區(qū)域聪姿,通過00000 ~ 11111來標(biāo)識(shí)這32個(gè)區(qū)域。第一次對(duì)地圖劃分后的情況如下圖所示(每個(gè)區(qū)域中的編號(hào)對(duì)應(yīng)于該區(qū)域所對(duì)應(yīng)的編碼)乙嘀。

????????Geohash的0末购、1串序列是經(jīng)度0、1序列和緯度0虎谢、1序列中的數(shù)字交替進(jìn)行排列的盟榴,偶數(shù)位對(duì)應(yīng)的序列為經(jīng)度序列,奇數(shù)位對(duì)應(yīng)的序列為緯度序列婴噩,在進(jìn)行第一次劃分時(shí)擎场,Geohash0、1序列中的前5個(gè)bits(11100)讳推,那么這5bits中有3bits是表示經(jīng)度顶籽,2bits表示緯度玩般,所以第一次劃分時(shí)银觅,是將經(jīng)度劃分成8個(gè)區(qū)段(2^3 = 8),將緯度劃分為4個(gè)區(qū)段(2^2 = 4)坏为,這樣就形成了32個(gè)區(qū)域究驴。如下圖

????????同理镊绪,可以按照第一次劃分所采用的方式對(duì)第一次劃分所得的32個(gè)區(qū)域各自再次劃分。

5.??GeoHash缺陷

????????上文講了GeoHash的計(jì)算步驟洒忧,僅僅說明是什么而沒有說明為什么蝴韭?為什么分別給經(jīng)度和維度編碼?為什么需要將經(jīng)緯度兩串編碼交叉組合成一串編碼熙侍?本節(jié)試圖回答這一問題榄鉴。

????????如圖所示,我們將二進(jìn)制編碼的結(jié)果填寫到空間中蛉抓,當(dāng)將空間劃分為四塊時(shí)候庆尘,編碼的順序分別是左下角00,左上角01巷送,右下腳10驶忌,右上角11,也就是類似于Z的曲線笑跛,當(dāng)我們遞歸的將各個(gè)塊分解成更小的子塊時(shí)付魔,編碼的順序是自相似的(分形),每一個(gè)子快也形成Z曲線飞蹂,這種類型的曲線被稱為Peano空間填充曲線几苍。

????????這種類型的空間填充曲線的優(yōu)點(diǎn)是將二維空間轉(zhuǎn)換成一維曲線(事實(shí)上是分形維),對(duì)大部分而言陈哑,編碼相似的距離也相近擦剑,但Peano空間填充曲線最大的缺點(diǎn)就是突變性,有些編碼相鄰但距離卻相差很遠(yuǎn)芥颈,比如0111與1000惠勒,編碼是相鄰的,但距離相差很大爬坑。

????????除Peano空間填充曲線外纠屋,還有很多空間填充曲線,如圖所示盾计,其中效果公認(rèn)較好是Hilbert空間填充曲線售担,相較于Peano曲線而言,Hilbert曲線沒有較大的突變署辉。但是由于Peano曲線實(shí)現(xiàn)更加簡(jiǎn)單族铆,在使用的時(shí)候配合一定的解決手段,可以很好的滿足大部分需求哭尝,因此TD內(nèi)部Geohash算法采用的是Peano空間填充曲線哥攘。

6.?使用注意點(diǎn)

? ? a.?由于GeoHash是將區(qū)域劃分為一個(gè)個(gè)規(guī)則矩形,并對(duì)每個(gè)矩形進(jìn)行編碼,這樣在查詢附近POI信息時(shí)會(huì)導(dǎo)致以下問題逝淹,比如紅色的點(diǎn)是我們的位置耕姊,綠色的兩個(gè)點(diǎn)分別是附近的兩個(gè)餐館,但是在查詢的時(shí)候會(huì)發(fā)現(xiàn)距離較遠(yuǎn)餐館的GeoHash編碼與我們一樣(因?yàn)樵谕粋€(gè)GeoHash區(qū)域塊上)栅葡,而較近餐館的GeoHash編碼與我們不一致茉兰。這個(gè)問題往往產(chǎn)生在邊界處。

????????解決的思路很簡(jiǎn)單欣簇,我們查詢時(shí)规脸,除了使用定位點(diǎn)的GeoHash編碼進(jìn)行匹配外,還使用周圍8個(gè)區(qū)域的GeoHash編碼熊咽,這樣可以避免這個(gè)問題燃辖。

????b.?我們已經(jīng)知道現(xiàn)有的GeoHash算法使用的是Peano空間填充曲線,這種曲線會(huì)產(chǎn)生突變网棍,造成了編碼雖然相似但距離可能相差很大的問題黔龟,因此在查詢附近餐館時(shí)候,首先篩選GeoHash編碼相似的POI點(diǎn)滥玷,然后進(jìn)行實(shí)際距離計(jì)算氏身。

? ? c.?GeoHash Base32編碼長(zhǎng)度與精度』蟪耄可以看出蛋欣,當(dāng)geohash base32編碼長(zhǎng)度為8時(shí),精度在19米左右如贷,而當(dāng)編碼長(zhǎng)度為9時(shí)陷虎,精度在2米左右,編碼長(zhǎng)度需要根據(jù)數(shù)據(jù)情況進(jìn)行選擇杠袱。

7.?計(jì)算圍欄內(nèi)所有Geohash

????????理解了geohash算法的基本原理之后尚猿,本節(jié)將介紹一個(gè)實(shí)際應(yīng)用中常見的場(chǎng)景:計(jì)算圍欄范圍內(nèi)所有的Geohash編碼。該場(chǎng)景封裝為函數(shù)可以表示如下:輸入組成圍欄的點(diǎn)經(jīng)緯度坐標(biāo)集合和指定的geohash長(zhǎng)度楣富,輸出一組geohash編碼凿掂。

????????public static Set getHashByFence(List points, int length)

????????具體算法步驟如下:

1. 輸入圍欄點(diǎn)坐標(biāo)集合List points和指定的geohash長(zhǎng)度length

2. 計(jì)算圍欄的外包矩形的左上角和右下角坐標(biāo)lat_min、lat_max纹蝴、lng_min庄萎、lng_max

3. 根據(jù)lat_min、lat_max塘安、lng_min糠涛、lng_max,計(jì)算外包矩形對(duì)角定點(diǎn)的距離d

4. 以外包矩形中心點(diǎn)為圓心兼犯,以d/2為半徑做一個(gè)圓忍捡,計(jì)算圓覆蓋范圍內(nèi)的geohash

????4.1 獲取圓的外包矩形左上角和右下角定點(diǎn)坐標(biāo)經(jīng)緯度集漾,存儲(chǔ)到double[] locs

????4.2 根據(jù)geohash字符長(zhǎng)度計(jì)算該長(zhǎng)度geohash編碼對(duì)應(yīng)的經(jīng)緯度間隔(latA,lngA)

????4.3 根據(jù)latA和lngA,計(jì)算出locs組成的矩形的左上角和右下角定點(diǎn)的經(jīng)緯度锉罐,在geohash劃分的網(wǎng)格的索引(也就是第幾個(gè)),分別記為lat_min,lat_max绕娘,lng_min脓规,lng_max

????4.4 計(jì)算lat_min,lat_max险领,lng_min侨舆,lng_max對(duì)應(yīng)范圍內(nèi)左右geohash的二進(jìn)制編碼,然后將經(jīng)緯度二進(jìn)制編碼uncode為geohash字符編碼绢陌,保存為Set sets

5. 剔除sets中g(shù)eohash編碼對(duì)應(yīng)矩形的中心點(diǎn)不在points圍欄范圍內(nèi)的geohash挨下,得到最終的geohash結(jié)果集

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市脐湾,隨后出現(xiàn)的幾起案子臭笆,更是在濱河造成了極大的恐慌,老刑警劉巖秤掌,帶你破解...
    沈念sama閱讀 217,277評(píng)論 6 503
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件愁铺,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡闻鉴,警方通過查閱死者的電腦和手機(jī)茵乱,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,689評(píng)論 3 393
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來孟岛,“玉大人瓶竭,你說我怎么就攤上這事∏撸” “怎么了斤贰?”我有些...
    開封第一講書人閱讀 163,624評(píng)論 0 353
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)次询。 經(jīng)常有香客問我腋舌,道長(zhǎng),這世上最難降的妖魔是什么渗蟹? 我笑而不...
    開封第一講書人閱讀 58,356評(píng)論 1 293
  • 正文 為了忘掉前任块饺,我火速辦了婚禮,結(jié)果婚禮上雌芽,老公的妹妹穿的比我還像新娘授艰。我一直安慰自己,他們只是感情好世落,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,402評(píng)論 6 392
  • 文/花漫 我一把揭開白布淮腾。 她就那樣靜靜地躺著,像睡著了一般。 火紅的嫁衣襯著肌膚如雪谷朝。 梳的紋絲不亂的頭發(fā)上洲押,一...
    開封第一講書人閱讀 51,292評(píng)論 1 301
  • 那天,我揣著相機(jī)與錄音圆凰,去河邊找鬼杈帐。 笑死,一個(gè)胖子當(dāng)著我的面吹牛专钉,可吹牛的內(nèi)容都是我干的挑童。 我是一名探鬼主播,決...
    沈念sama閱讀 40,135評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼跃须,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼站叼!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起菇民,我...
    開封第一講書人閱讀 38,992評(píng)論 0 275
  • 序言:老撾萬榮一對(duì)情侶失蹤尽楔,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后第练,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體翔试,經(jīng)...
    沈念sama閱讀 45,429評(píng)論 1 314
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,636評(píng)論 3 334
  • 正文 我和宋清朗相戀三年复旬,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了垦缅。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 39,785評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡驹碍,死狀恐怖壁涎,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情志秃,我是刑警寧澤怔球,帶...
    沈念sama閱讀 35,492評(píng)論 5 345
  • 正文 年R本政府宣布,位于F島的核電站浮还,受9級(jí)特大地震影響竟坛,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜钧舌,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,092評(píng)論 3 328
  • 文/蒙蒙 一担汤、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧洼冻,春花似錦崭歧、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,723評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽叔营。三九已至,卻和暖如春所宰,著一層夾襖步出監(jiān)牢的瞬間绒尊,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,858評(píng)論 1 269
  • 我被黑心中介騙來泰國(guó)打工仔粥, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留婴谱,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 47,891評(píng)論 2 370
  • 正文 我出身青樓件炉,卻偏偏與公主長(zhǎng)得像勘究,于是被迫代替她去往敵國(guó)和親矮湘。 傳聞我的和親對(duì)象是個(gè)殘疾皇子斟冕,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,713評(píng)論 2 354

推薦閱讀更多精彩內(nèi)容