?隨著移動(dòng)互聯(lián)網(wǎng)的發(fā)展，很多基于地理位置信息的服務(wù)也越來越流行。比如說我們平常經(jīng)常使用的查找附近的人，或者是附近的餐館，共享單車等等。

那么，大家有沒有想過，這個(gè)查找功能是如何實(shí)現(xiàn)的嗎？作為受過高等教育的人，大家肯定立即就想到了可以通過經(jīng)緯度進(jìn)行計(jì)算。具體算法類似于這樣：

地球近似于一個(gè)球體，地球赤道周長(zhǎng)約40075.04公里，半徑約為6371公里，因此，可以很容易地用立體幾何的方法求出其距離，例如說最常見的大圓距離（Great-Circle Distance）。

公式如下：

其中， R為地球半徑，Aj、Aw分別表示A點(diǎn)的經(jīng)度、緯度；Bj、Bw分別表示B點(diǎn)的經(jīng)度、緯度。這樣，通過簡(jiǎn)單的立體幾何方法就可以很容易地求出其距離。

如果有人對(duì)于地理信息學(xué)比較了解的話，還會(huì)知道半正矢公式（Haversine公式），因?yàn)榇髨A距離公式用到了大量的余弦函數(shù)，因此在兩點(diǎn)距離過短的時(shí)候，會(huì)導(dǎo)致比較大的舍入誤差。而半正矢公式則因?yàn)椴捎昧苏液瘮?shù)的方法，因此即使距離過小，也可以保留足夠的有效數(shù)字。半正矢公式的形式如下所示：

其中

這里面的R為地球半徑，可取平均值 6371km；φ1, φ2 表示兩點(diǎn)的緯度；Δλ 表示兩點(diǎn)經(jīng)度的差值。

有了這些算法，那么理論上來查找附近的人就可以很方便地實(shí)現(xiàn)了。但是為什么要說從理論上講呢？因?yàn)樵诠こ虒?shí)踐中，這樣查找的計(jì)算量太大了。對(duì)于幾個(gè)經(jīng)緯度的數(shù)據(jù)而言還可以，但是對(duì)于大規(guī)模數(shù)據(jù)查詢而言，沒有實(shí)際可操作性。就比如想在一個(gè)一百萬(wàn)條數(shù)據(jù)的數(shù)據(jù)庫(kù)里查找附近5公里之內(nèi)的餐館有哪些，那么要對(duì)一百萬(wàn)條數(shù)據(jù)做各種三角函數(shù)操作，這顯然是不現(xiàn)實(shí)的事情，更別說在互聯(lián)網(wǎng)上應(yīng)用的數(shù)據(jù)體量遠(yuǎn)大于百萬(wàn)條。而且這樣的數(shù)據(jù)也很難對(duì)其查詢效率進(jìn)行優(yōu)化。

那么，要怎么解決這個(gè)問題呢？這就是我們今天要介紹的神奇算法，Geohash算法了。通過Geohash算法，我們可以把兩個(gè)坐標(biāo)的距離計(jì)算簡(jiǎn)化為兩個(gè)字符串的比較，從而可以最大限度的應(yīng)用速度更快的字符串相關(guān)函數(shù)，并且對(duì)其進(jìn)行排序或索引。

下面我們就來看看Geohash算法具體是怎么做到這一點(diǎn)的。

Geohash的本質(zhì)就是將用到的整個(gè)地圖區(qū)域進(jìn)行矩形分割，然后在各個(gè)矩形之中再次進(jìn)行矩形分割，而每一次分割中所在的區(qū)域用一個(gè)字符代表，這樣一次次分割之后，就可以最大可能的逼近實(shí)際坐標(biāo)所在地。而這個(gè)坐標(biāo)也就可以用一串字符來代替了。常用的Geohash算法中，每個(gè)字符用5個(gè)比特來標(biāo)識(shí)，這樣就會(huì)有32個(gè)不同的組合（0-31），于是我們就可以將這個(gè)地圖區(qū)域劃分為32個(gè)區(qū)域。這樣劃分之后，第一個(gè)字母劃分的區(qū)域就如下圖所示：

然后我們?cè)賹?duì)各個(gè)區(qū)域繼續(xù)進(jìn)行劃分，就會(huì)得到類似于wx4eqzrx，這樣的一個(gè)字符串了。

而這時(shí)，我們就可以方便地使用類似于：

Select * from world where geohash like 'wx4eqw%';

這樣的sql語(yǔ)句查詢到附近想要查詢的東西了。是不是很方便呢？通過這種方式，我們就把復(fù)雜的三角函數(shù)計(jì)算，轉(zhuǎn)化成了計(jì)算化處理效率非常高的字符串操作了。

那么，想必大家一定要問了，坐標(biāo)轉(zhuǎn)化成的字符串是怎么生成的呢？其實(shí)也很簡(jiǎn)單。

我們以緯度39.928167為例。

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，劃分次數(shù)越多，距離就越精確，字符串也就會(huì)越長(zhǎng)，如下圖所示：

這樣我們就得到了緯度的二進(jìn)制表示，同樣我們也可以對(duì)經(jīng)度進(jìn)行二進(jìn)制表示。然后，我們把經(jīng)度放到偶數(shù)位，緯度放到奇數(shù)位，把兩個(gè)二進(jìn)制串合并到一起，最后將得到的二進(jìn)制串編碼每5位進(jìn)行base32編碼，最終就得到了我們想要的，對(duì)于每個(gè)小方格進(jìn)行表示的Geohash字符串序列。

但是這樣做了之后，很多人會(huì)發(fā)現(xiàn)一個(gè)問題，那就是每個(gè)Geohash字符串事實(shí)上都是代表一個(gè)小方格的，那么就會(huì)產(chǎn)生邊界跨越的問題。就像下圖中的紅點(diǎn)，和上面的綠點(diǎn)并不在一個(gè)方格里，因此如果我們光查詢紅點(diǎn)所在的格子的話，就會(huì)查詢不到明明離它很近的上面的綠點(diǎn)，反而可以查詢到更遠(yuǎn)一點(diǎn)的下面的綠點(diǎn)。

那么怎么解決這個(gè)問題呢？其實(shí)也很簡(jiǎn)單，就是在查詢的時(shí)候，把周圍的8個(gè)格子也考慮進(jìn)來一起查詢就行了。那么具體是怎么做的呢？我們可以看到，周圍的8個(gè)格子，本質(zhì)上就是經(jīng)度緯度的格子二進(jìn)制數(shù)與中間的格子差1，所以我們只需要對(duì)紅點(diǎn)的經(jīng)緯度二進(jìn)制數(shù)，進(jìn)行加減1的操作就可以獲取到附近格子的字符串了。而這樣做本質(zhì)上就是損失了一個(gè)格子的精度。而在經(jīng)緯度位數(shù)足夠的情況下，這個(gè)誤差是可以忽略不計(jì)的。通過計(jì)數(shù)我們可以得出：

在緯度相等的情況下，經(jīng)度每隔0.00001度，距離相差約1米；在經(jīng)度相等的情況下，緯度每隔0.00001度，距離相差約1.1米；而在geohash的位數(shù)是9位數(shù)的時(shí)候，大概為附近2米；8位的話，大約為附近19米。對(duì)于大部分人來講，可以說是一個(gè)可以接受的誤差了哦。?