隨著移動互聯(lián)網(wǎng)的興起，越來越多的App中加入了LBS的元素。而在各種LBS應(yīng)用中，查找附近的地點是一種最基本也是最常見的形式。前段時間項目中加入了一個新的特性，需要根據(jù)用戶所在的位置，查找附近的用戶和用戶發(fā)表的廣播。本文將對此項目中使用的一些關(guān)鍵技術(shù)和遇到的問題做個簡單的介紹。

在進(jìn)行具體的技術(shù)介紹之前，需要先從產(chǎn)品層面做一些基本的條件設(shè)定。首先，地理位置信息是有時效性的，用戶A一個月前來過某個地點，一個月后再向出現(xiàn)在同一個地點的其他用戶推薦A就沒有太大的意義了。所以我們需要根據(jù)實際情況對數(shù)據(jù)進(jìn)行定期清理，例如只保存最近一周或者最近15天內(nèi)的數(shù)據(jù)，這樣不僅能夠給用戶提供最“有效”的數(shù)據(jù)，而且能夠控制總的數(shù)據(jù)量，減少server端的壓力。其次，LBS應(yīng)用對于精度的要求沒有那么高，通過移動設(shè)備進(jìn)行定位本身就有一定的誤差，因此server端在進(jìn)行算法設(shè)計和實現(xiàn)時也并不一定要求100%的準(zhǔn)確（實際上也很難做到），只要能把誤差控制在一定的范圍內(nèi)即可。

關(guān)于查找附近地點的算法和實現(xiàn)，網(wǎng)上有不少相關(guān)的文章，下面重點介紹一下在本項目開發(fā)過程中嘗試和研究過的各種方案，以及最終選擇的實現(xiàn)方式。

1. geohash

geohash是一種地址編碼方式，它可以把用經(jīng)緯度表示的地理位置信息編碼成一個字符串，例如銀科大廈所在位置的經(jīng)緯度為（116.306785，39.981998），對應(yīng)的geohash編碼為wx4eqws0。Geohash的編碼算法很簡單，我們就以（116.306785，39.981998）為例進(jìn)行簡單的介紹。首先將緯度范圍（-90,90）平分為（-90,0）和（0,90）兩個區(qū)間，如果目標(biāo)緯度位于前一個區(qū)間，則編碼為0，否則編碼為1。由于39.981998屬于（0,90），所以編碼為1。然后再將（0,90）分為（0,45）和（45,90）兩個區(qū)間，而39.981998位于（0,45），所以編碼為0。以此類推，直到精度符合要求為止，得到緯度編碼為1011 1000 1101 1101 0000。用同樣的方法對經(jīng)度進(jìn)行編碼（經(jīng)度的取值范圍為（-180，180）），得到116.306785的編碼為1101 0010 1011 0101 0000。然后將經(jīng)度和緯度的編碼合并，奇數(shù)位為緯度，偶數(shù)位為經(jīng)度，得到編碼11100 11101 00010 01101 10110 11100 11000 00000。***用0-9、b-z（去掉a，i，l和o）進(jìn)行base32編碼，得到最終的geohash編碼wx4eqws0。

從以上的計算過程可以看出，geohash表示的是一個格子（矩形區(qū)域）而不是一個點，geohash長度越長，這個格子就越?。痪哂邢嗤熬Y的geohash編碼會落在同一個格子內(nèi)，相同的前綴越長，格子越小，在地理位置上就越接近，利用這一特點，可以實現(xiàn)我們想要的搜索附近的地點的功能。不過geohash編碼算法也有一些缺點，首先是位于格子邊界兩側(cè)的點雖然十分接近，但是編碼會完全不同。因此在實際的應(yīng)用中，我們不僅要搜索當(dāng)前格子，還要搜索當(dāng)前格子周圍的8個格子。除此之外，如果我們想要搜索特定范圍內(nèi)的地點，比如要查找周圍1Km內(nèi)的人，geohash無法實現(xiàn)這種控制，只能在返回的結(jié)果集里再進(jìn)行一次距離計算，過濾掉這個范圍之外的結(jié)果。

2. 基于球面距離公式的算法

查找附近地點算法的難點在于，數(shù)據(jù)庫中保存的是地點的坐標(biāo)信息，搜索條件是地點坐標(biāo)和給定坐標(biāo)之間的距離，兩者之間無法直接建立聯(lián)系。如果我們能把搜索的條件轉(zhuǎn)換為坐標(biāo)范圍的話，接下來的事情就比較簡單了。一般我們需要搜索一定范圍內(nèi)的地點，這個范圍實際上是一個圓，我們可以把搜索的范圍擴(kuò)大到這個圓的外接正方形，求出這個正方形對應(yīng)的經(jīng)緯度范圍，這樣就可以在數(shù)據(jù)庫中進(jìn)行查找了。因為實際的搜索范圍有所擴(kuò)大，所以可能需求對返回的結(jié)果進(jìn)行一次過濾，去除掉不符合條件的結(jié)果。要進(jìn)行上述的計算，我們要用到Haversine公式。Haversine公式的定義為：

haversine(d/R) = haversine(lat2-lat1) + cos(lat2)cos(lat1)haversine(lng2-lng1)

其中
haversine(a) = (1-cos(a))/2

d為兩點間的距離，R為地球半徑，取平均值6371km，lat1和lat2為兩點的緯度，lng1和lng2為兩點的經(jīng)度。通過這個公式，我們可以根據(jù)任意兩點的經(jīng)緯度計算出兩點間的球面距離。
利用Haversine公式，我們還可以反推出計算經(jīng)緯度搜索范圍的計算。在Haversin公式中，令lat1=lat2，可以得到
delta(lng)=2arcsin(sin(d/2R)/cos(lat1))

令lng1=lng2，可以得到
delta(lat)=d/R

根據(jù)當(dāng)前點的坐標(biāo)和經(jīng)緯度的范圍，就可以得出搜索范圍了。

這個算法的特點是簡單明了，搜索范圍可控，精度也可以接受。但是在實際使用中發(fā)現(xiàn)，即使在經(jīng)度和緯度列上建立索引（使用MySQL），數(shù)據(jù)量大的時候效率會比較差，達(dá)不到性能上的要求。

3. 基于Sptial Indexing的方案

方案2中基于球面距離公式的算法本身沒有太大的問題，瓶頸在于數(shù)據(jù)庫的效率。這里要介紹的Spatial Indexing——空間索引，就是要解決這個問題。不同于我們常用的BTree索引，基于RTree的空間索引可以在二維空間上進(jìn)行高效的查詢，非常適合類似查找附近的地點這樣的需求。主流的數(shù)據(jù)庫，包括MySQL，都在不同的程度上支持空間索引。MySQL中有一個類型Point，可以用來存儲每個位置對應(yīng)的經(jīng)緯度。在這一列上建立空間索引，按照方案2中得出的經(jīng)緯度范圍劃定一個矩形，利用MySQL提供的空間擴(kuò)展函數(shù)判斷某個點是否在這個矩形內(nèi)，就可以實現(xiàn)查找附近地點的目的了。

以上介紹了在整個項目開發(fā)過程中進(jìn)行的各種嘗試以及每種方案的優(yōu)缺點，最終采用的方案是以上各個方案的一個綜合：在數(shù)據(jù)庫中建立空間索引，對于任意一個請求，根據(jù)經(jīng)緯度（lng，lat）和查找范圍（d）以及Haversin公式計算出經(jīng)緯度范圍（delta(lng)，delta(lat)），然后利用MySQL的空間擴(kuò)展函數(shù)在數(shù)據(jù)庫中進(jìn)行查找，得到的結(jié)果除了排序、過濾并返回以外還要保存在cache中，cache的key為經(jīng)緯度（lng，lat）的geohash編碼。geohash編碼的長度是可以配置的，本項目中我們選擇了長度為7的geohash編碼，原因是7位geohash編碼表示的格子的大小大約在150m左右，也就是說150m范圍內(nèi)的搜索可以返回相同的結(jié)果，這基本滿足我們對于精度的要求。