建站
咨詢
售后
建站咨詢
新聞中心
隨著移動(dòng)互聯(lián)網(wǎng)的興起，越來越多的App中加入了LBS的元素。而在各種LBS應(yīng)用中，查找附近的地點(diǎn)是一種最基本也是最常見的形式。前段時(shí)間項(xiàng)目中加入了一個(gè)新的特性，需要根據(jù)用戶所在的位置，查找附近的用戶和用戶發(fā)表的廣播。本文將對(duì)此項(xiàng)目中使用的一些關(guān)鍵技術(shù)和遇到的問題做個(gè)簡單的介紹。
創(chuàng)新互聯(lián)建站是一家集網(wǎng)站建設(shè),唐河企業(yè)網(wǎng)站建設(shè),唐河品牌網(wǎng)站建設(shè),網(wǎng)站定制,唐河網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營銷,網(wǎng)絡(luò)優(yōu)化,唐河網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。
在進(jìn)行具體的技術(shù)介紹之前，需要先從產(chǎn)品層面做一些基本的條件設(shè)定。首先，地理位置信息是有時(shí)效性的，用戶A一個(gè)月前來過某個(gè)地點(diǎn)，一個(gè)月后再向出現(xiàn)在同一個(gè)地點(diǎn)的其他用戶推薦A就沒有太大的意義了。所以我們需要根據(jù)實(shí)際情況對(duì)數(shù)據(jù)進(jìn)行定期清理，例如只保存最近一周或者最近15天內(nèi)的數(shù)據(jù)，這樣不僅能夠給用戶提供最“有效”的數(shù)據(jù)，而且能夠控制總的數(shù)據(jù)量，減少server端的壓力。其次，LBS應(yīng)用對(duì)于精度的要求沒有那么高，通過移動(dòng)設(shè)備進(jìn)行定位本身就有一定的誤差，因此server端在進(jìn)行算法設(shè)計(jì)和實(shí)現(xiàn)時(shí)也并不一定要求100%的準(zhǔn)確（實(shí)際上也很難做到），只要能把誤差控制在一定的范圍內(nèi)即可。
關(guān)于查找附近地點(diǎn)的算法和實(shí)現(xiàn)，網(wǎng)上有不少相關(guān)的文章，下面重點(diǎn)介紹一下在本項(xiàng)目開發(fā)過程中嘗試和研究過的各種方案，以及最終選擇的實(shí)現(xiàn)方式。
1. geohash
geohash是一種地址編碼方式，它可以把用經(jīng)緯度表示的地理位置信息編碼成一個(gè)字符串，例如銀科大廈所在位置的經(jīng)緯度為（116.306785，39.981998），對(duì)應(yīng)的geohash編碼為wx4eqws0。Geohash的編碼算法很簡單，我們就以（116.306785，39.981998）為例進(jìn)行簡單的介紹。首先將緯度范圍（-90,90）平分為（-90,0）和（0,90）兩個(gè)區(qū)間，如果目標(biāo)緯度位于前一個(gè)區(qū)間，則編碼為0，否則編碼為1。由于39.981998屬于（0,90），所以編碼為1。然后再將（0,90）分為（0,45）和（45,90）兩個(gè)區(qū)間，而39.981998位于（0,45），所以編碼為0。以此類推，直到精度符合要求為止，得到緯度編碼為1011 1000 1101 1101 0000。用同樣的方法對(duì)經(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。
從以上的計(jì)算過程可以看出，geohash表示的是一個(gè)格子（矩形區(qū)域）而不是一個(gè)點(diǎn)，geohash長度越長，這個(gè)格子就越小；具有相同前綴的geohash編碼會(huì)落在同一個(gè)格子內(nèi)，相同的前綴越長，格子越小，在地理位置上就越接近，利用這一特點(diǎn)，可以實(shí)現(xiàn)我們想要的搜索附近的地點(diǎn)的功能。不過geohash編碼算法也有一些缺點(diǎn)，首先是位于格子邊界兩側(cè)的點(diǎn)雖然十分接近，但是編碼會(huì)完全不同。因此在實(shí)際的應(yīng)用中，我們不僅要搜索當(dāng)前格子，還要搜索當(dāng)前格子周圍的8個(gè)格子。除此之外，如果我們想要搜索特定范圍內(nèi)的地點(diǎn)，比如要查找周圍1Km內(nèi)的人，geohash無法實(shí)現(xiàn)這種控制，只能在返回的結(jié)果集里再進(jìn)行一次距離計(jì)算，過濾掉這個(gè)范圍之外的結(jié)果。
2. 基于球面距離公式的算法
查找附近地點(diǎn)算法的難點(diǎn)在于，數(shù)據(jù)庫中保存的是地點(diǎn)的坐標(biāo)信息，搜索條件是地點(diǎn)坐標(biāo)和給定坐標(biāo)之間的距離，兩者之間無法直接建立聯(lián)系。如果我們能把搜索的條件轉(zhuǎn)換為坐標(biāo)范圍的話，接下來的事情就比較簡單了。一般我們需要搜索一定范圍內(nèi)的地點(diǎn)，這個(gè)范圍實(shí)際上是一個(gè)圓，我們可以把搜索的范圍擴(kuò)大到這個(gè)圓的外接正方形，求出這個(gè)正方形對(duì)應(yīng)的經(jīng)緯度范圍，這樣就可以在數(shù)據(jù)庫中進(jìn)行查找了。因?yàn)閷?shí)際的搜索范圍有所擴(kuò)大，所以可能需求對(duì)返回的結(jié)果進(jìn)行一次過濾，去除掉不符合條件的結(jié)果。要進(jìn)行上述的計(jì)算，我們要用到Haversine公式。Haversine公式的定義為：
haversine(d/R) = haversine(lat2-lat1) + cos(lat2)cos(lat1)haversine(lng2-lng1)
其中
haversine(a) = (1-cos(a))/2
d為兩點(diǎn)間的距離，R為地球半徑，取平均值6371km，lat1和lat2為兩點(diǎn)的緯度，lng1和lng2為兩點(diǎn)的經(jīng)度。通過這個(gè)公式，我們可以根據(jù)任意兩點(diǎn)的經(jīng)緯度計(jì)算出兩點(diǎn)間的球面距離。
利用Haversine公式，我們還可以反推出計(jì)算經(jīng)緯度搜索范圍的計(jì)算。在Haversin公式中，令lat1=lat2，可以得到
delta(lng)=2arcsin(sin(d/2R)/cos(lat1))
令lng1=lng2，可以得到
delta(lat)=d/R
根據(jù)當(dāng)前點(diǎn)的坐標(biāo)和經(jīng)緯度的范圍，就可以得出搜索范圍了。
這個(gè)算法的特點(diǎn)是簡單明了，搜索范圍可控，精度也可以接受。但是在實(shí)際使用中發(fā)現(xiàn)，即使在經(jīng)度和緯度列上建立索引（使用MySQL），數(shù)據(jù)量大的時(shí)候效率會(huì)比較差，達(dá)不到性能上的要求。
3. 基于Sptial Indexing的方案
方案2中基于球面距離公式的算法本身沒有太大的問題，瓶頸在于數(shù)據(jù)庫的效率。這里要介紹的Spatial Indexing——空間索引，就是要解決這個(gè)問題。不同于我們常用的BTree索引，基于RTree的空間索引可以在二維空間上進(jìn)行高效的查詢，非常適合類似查找附近的地點(diǎn)這樣的需求。主流的數(shù)據(jù)庫，包括MySQL，都在不同的程度上支持空間索引。MySQL中有一個(gè)類型Point，可以用來存儲(chǔ)每個(gè)位置對(duì)應(yīng)的經(jīng)緯度。在這一列上建立空間索引，按照方案2中得出的經(jīng)緯度范圍劃定一個(gè)矩形，利用MySQL提供的空間擴(kuò)展函數(shù)判斷某個(gè)點(diǎn)是否在這個(gè)矩形內(nèi)，就可以實(shí)現(xiàn)查找附近地點(diǎn)的目的了。
以上介紹了在整個(gè)項(xiàng)目開發(fā)過程中進(jìn)行的各種嘗試以及每種方案的優(yōu)缺點(diǎn)，最終采用的方案是以上各個(gè)方案的一個(gè)綜合：在數(shù)據(jù)庫中建立空間索引，對(duì)于任意一個(gè)請(qǐng)求，根據(jù)經(jīng)緯度（lng，lat）和查找范圍（d）以及Haversin公式計(jì)算出經(jīng)緯度范圍（delta(lng)，delta(lat)），然后利用MySQL的空間擴(kuò)展函數(shù)在數(shù)據(jù)庫中進(jìn)行查找，得到的結(jié)果除了排序、過濾并返回以外還要保存在cache中，cache的key為經(jīng)緯度（lng，lat）的geohash編碼。geohash編碼的長度是可以配置的，本項(xiàng)目中我們選擇了長度為7的geohash編碼，原因是7位geohash編碼表示的格子的大小大約在150m左右，也就是說150m范圍內(nèi)的搜索可以返回相同的結(jié)果，這基本滿足我們對(duì)于精度的要求。
文章名稱：附近地點(diǎn)搜索解決方案
網(wǎng)址分享：http://m.fisionsoft.com.cn/article/ccicjpj.html
