1.場(chǎng)景
隨著智能手機(jī)和傳感器技術(shù)的發(fā)展，LBS（Location based service）類的應(yīng)用也逐漸多了起來。幾乎每一個(gè)軟件或多或少都要牽扯上點(diǎn)位置的事褥芒。這篇文章主要來講解下怎么快速的搜尋某個(gè)位置點(diǎn)周邊的數(shù)據(jù)。
將問題模型化就是，給一組數(shù)據(jù)亩钟，每個(gè)數(shù)據(jù)包括了這個(gè)數(shù)據(jù)的位置信息（經(jīng)緯度）和其他信息乓梨，給一個(gè)搜尋點(diǎn)（經(jīng)度和緯度）和搜尋范圍（radius），在最少的計(jì)算和時(shí)間內(nèi)將在搜尋點(diǎn)的搜尋范圍內(nèi)的數(shù)據(jù)找出來清酥。
2.目前的解決方案
（1）圓形區(qū)域一一匹配搜索扶镀。
將list中的數(shù)據(jù)一個(gè)一個(gè)同搜索位置進(jìn)行距離計(jì)算。幾乎沒有人這樣用焰轻，每一個(gè)數(shù)據(jù)都需要進(jìn)行開根號(hào)操作臭觉，數(shù)據(jù)量大的時(shí)候不可想象。
（2）先對(duì)數(shù)據(jù)庫中的經(jīng)度（longitude）和緯度（latitude）添加B+樹索引辱志，然后搜索以radius的兩倍為邊長的正方形蝠筑，如下圖：
（3）使用目前現(xiàn)成的擁有地理位置搜索的數(shù)據(jù)庫，比如mongoDB荸频，HBase等等菱肖。
（4）使用geohash數(shù)據(jù)結(jié)構(gòu)，見下面介紹
3.geohash介紹
（1）感性認(rèn)識(shí)GeoHash
首先來點(diǎn)感性認(rèn)識(shí)旭从，http://openlocation.org/geohash/geohash-js/ 提供了在地圖上顯示geohash編碼的功能稳强。
1）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)）棒坏，又比較容易做緩存，比如左上角這個(gè)區(qū)域內(nèi)的用戶不斷發(fā)送位置信息請(qǐng)求餐館數(shù)據(jù)遭笋，由于這些用戶的GeoHash字符串都是WX4ER坝冕，所以可以把WX4ER當(dāng)作key，把該區(qū)域的餐館信息當(dāng)作value來進(jìn)行緩存瓦呼，而如果不使用GeoHash的話喂窟，由于區(qū)域內(nèi)的用戶傳來的經(jīng)緯度是各不相同的，很難做緩存央串。
2）字符串越長磨澡，表示的范圍越精確。如圖所示质和，5位的編碼能表示10平方千米范圍的矩形區(qū)域稳摄，而6位編碼能表示更精細(xì)的區(qū)域（約0.34平方千米）
4.png
3）字符串相似的表示距離相近（特殊情況后文闡述），這樣可以利用字符串的前綴匹配來查詢附近的POI信息饲宿。如下兩個(gè)圖所示秩命，一個(gè)在城區(qū)尉共，一個(gè)在郊區(qū)，城區(qū)的GeoHash字符串之間比較相似弃锐，郊區(qū)的字符串之間也比較相似袄友，而城區(qū)和郊區(qū)的GeoHash字符串相似程度要低些。
城區(qū)
郊區(qū)
通過上面的介紹我們知道了GeoHash就是一種將經(jīng)緯度轉(zhuǎn)換成字符串的方法霹菊，并且使得在大部分情況下剧蚣，字符串前綴匹配越多的距離越近，回到我們的案例旋廷，根據(jù)所在位置查詢來查詢附近餐館時(shí)鸠按，只需要將所在位置經(jīng)緯度轉(zhuǎn)換成GeoHash字符串，并與各個(gè)餐館的GeoHash字符串進(jìn)行前綴匹配饶碘，匹配越多的距離越近目尖。
（2）GeoHash算法的步驟
下面以北海公園為例介紹GeoHash算法的計(jì)算步驟
7.png
2.1. 根據(jù)經(jīng)緯度計(jì)算GeoHash二進(jìn)制編碼地球緯度區(qū)間是[-90,90]， 北海公園的緯度是39.928167扎运，可以通過下面算法對(duì)緯度39.928167進(jìn)行逼近編碼:1）區(qū)間[-90,90]進(jìn)行二分為[-90,0),[0,90]瑟曲，稱為左右區(qū)間，可以確定39.928167屬于右區(qū)間[0,90]豪治，給標(biāo)記為1洞拨；2）接著將區(qū)間[0,90]進(jìn)行二分為 [0,45),[45,90]，可以確定39.928167屬于左區(qū)間 [0,45)负拟，給標(biāo)記為0烦衣；3）遞歸上述過程39.928167總是屬于某個(gè)區(qū)間[a,b]。隨著每次迭代區(qū)間[a,b]總在縮小掩浙，并越來越逼近39.928167花吟；4）如果給定的緯度x（39.928167）屬于左區(qū)間，則記錄0厨姚，如果屬于右區(qū)間則記錄1示辈，這樣隨著算法的進(jìn)行會(huì)產(chǎn)生一個(gè)序列1011100，序列的長度跟給定的區(qū)間劃分次數(shù)有關(guān)遣蚀。
首先將緯度范圍(-90, 90)平分成兩個(gè)區(qū)間(-90, 0)、(0, 90)纱耻， 如果目標(biāo)緯度位于前一個(gè)區(qū)間芭梯，則編碼為0，否則編碼為1弄喘。
由于39.92324屬于(0, 90)玖喘，所以取編碼為1。
然后再將(0, 90)分成 (0, 45), (45, 90)兩個(gè)區(qū)間蘑志，而39.92324位于(0, 45)累奈，所以編碼為0贬派。
以此類推，直到精度符合要求為止澎媒，得到緯度編碼為1011 1000 1100 0111 1001搞乏。
經(jīng)度也用同樣的算法，對(duì)(-180, 180)依次細(xì)分戒努，得到116.3906的編碼為1101 0010 1100 0100 0100
2.2. 組碼通過上述計(jì)算请敦，緯度產(chǎn)生的編碼為10111 00011，經(jīng)度產(chǎn)生的編碼為11010 01011储玫。偶數(shù)位放經(jīng)度侍筛，奇數(shù)位放緯度，把2串編碼組合生成新串：11100 11101 00100 01111撒穷。最后使用用0-9匣椰、b-z（去掉a, i, l, o）這32個(gè)字母進(jìn)行base32編碼，首先將11100 11101 00100 01111轉(zhuǎn)成十進(jìn)制端礼，對(duì)應(yīng)著28禽笑、29、4齐媒、15蒲每，十進(jìn)制對(duì)應(yīng)的編碼就是wx4g。同理喻括，將編碼轉(zhuǎn)換成經(jīng)緯度的解碼算法與之相反邀杏，具體不再贅述。
8.png
（3）GeoHash Base32編碼長度與精度
下表摘自維基百科：http://en.wikipedia.org/wiki/Geohash可以看出唬血，當(dāng)geohash base32編碼長度為8時(shí)望蜡，精度在19米左右，而當(dāng)編碼長度為9時(shí)拷恨，精度在2米左右脖律，編碼長度需要根據(jù)數(shù)據(jù)情況進(jìn)行選擇。
（4）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赞别，編碼是相鄰的畏陕，但距離相差很大。
10.png
除Peano空間填充曲線外仿滔，還有很多空間填充曲線惠毁，如圖所示，其中效果公認(rèn)較好是Hilbert空間填充曲線崎页，相較于Peano曲線而言鞠绰，Hilbert曲線沒有較大的突變。為什么GeoHash不選擇Hilbert空間填充曲線呢飒焦？可能是Peano曲線思路以及計(jì)算上比較簡(jiǎn)單吧蜈膨，事實(shí)上，Peano曲線就是一種四叉樹線性編碼方式牺荠。
（5）使用注意點(diǎn)
1）由于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)生在邊界處。
12.png
解決的思路很簡(jiǎn)單担扑，我們查詢時(shí)恰响，除了使用定位點(diǎn)的GeoHash編碼進(jìn)行匹配外魁亦，還使用周圍8個(gè)區(qū)域的GeoHash編碼羔挡，這樣可以避免這個(gè)問題间唉。2）我們已經(jīng)知道現(xiàn)有的GeoHash算法使用的是Peano空間填充曲線，這種曲線會(huì)產(chǎn)生突變利术，造成了編碼雖然相似但距離可能相差很大的問題呈野，因此在查詢附近餐館時(shí)候，首先篩選GeoHash編碼相似的POI點(diǎn)印叁，然后進(jìn)行實(shí)際距離計(jì)算被冒。
4.實(shí)踐
geohash
<?php
class Geohash{
private $coding="0123456789bcdefghjkmnpqrstuvwxyz";
private $codingMap=array();
public function Geohash()
{
for($i=0; $i<32; $i++)
{
$this->codingMap[substr($this->coding,$i,1)]=str_pad(decbin($i), 5, "0", STR_PAD_LEFT);
}
}
public function decode($hash)
{
$binary="";
$hl=strlen($hash);
for($i=0; $i<$hl; $i++)
{
$binary.=$this->codingMap[substr($hash,$i,1)];
}
$bl=strlen($binary);
$blat="";
$blong="";
for ($i=0; $i<$bl; $i++)
{
if ($i%2)
$blat=$blat.substr($binary,$i,1);
else
$blong=$blong.substr($binary,$i,1);
}
$lat=$this->binDecode($blat,-90,90);
$long=$this->binDecode($blong,-180,180);
// $lat=$this->binDecode($blat,2,54);
// $long=$this->binDecode($blong,72,136);
$latErr=$this->calcError(strlen($blat),-90,90);
$longErr=$this->calcError(strlen($blong),-180,180);
$latPlaces=max(1, -round(log10($latErr))) - 1;
$longPlaces=max(1, -round(log10($longErr))) - 1;
$lat=round($lat, $latPlaces);
$long=round($long, $longPlaces);
return array($lat,$long);
}
public function encode($lat,$long)
{
$plat=$this->precision($lat);
$latbits=1;
$err=45;
while($err>$plat)
{
$latbits++;
$err/=2;
}
$plong=$this->precision($long);
$longbits=1;
$err=90;
while($err>$plong)
{
$longbits++;
$err/=2;
}
$bits=max($latbits,$longbits);
$longbits=$bits;
$latbits=$bits;
$addlong=1;
while (($longbits+$latbits)%5 != 0)
{
$longbits+=$addlong;
$latbits+=!$addlong;
$addlong=!$addlong;
}
$blat=$this->binEncode($lat,-90,90, $latbits);
$blong=$this->binEncode($long,-180,180,$longbits);
$binary="";
$uselong=1;
while (strlen($blat)+strlen($blong))
{
if ($uselong)
{
$binary=$binary.substr($blong,0,1);
$blong=substr($blong,1);
}
else
{
$binary=$binary.substr($blat,0,1);
$blat=substr($blat,1);
}
$uselong=!$uselong;
}
$hash="";
for ($i=0; $i<strlen($binary); $i+=5)
{
$n=bindec(substr($binary,$i,5));
$hash=$hash.$this->coding[$n];
}
return $hash;
}
private function calcError($bits,$min,$max)
{
$err=($max-$min)/2;
while ($bits--)
$err/=2;
return $err;
}
private function precision($number)
{
$precision=0;
$pt=strpos($number,'.');
if ($pt!==false)
{
$precision=-(strlen($number)-$pt-1);
}
return pow(10,$precision)/2;
}
private function binEncode($number, $min, $max, $bitcount)
{
if ($bitcount==0)
return "";
$mid=($min+$max)/2;
if ($number>$mid)
return "1".$this->binEncode($number, $mid, $max,$bitcount-1);
else
return "0".$this->binEncode($number, $min, $mid,$bitcount-1);
}
private function binDecode($binary, $min, $max)
{
$mid=($min+$max)/2;
if (strlen($binary)==0)
return $mid;
$bit=substr($binary,0,1);
$binary=substr($binary,1);
if ($bit==1)
return $this->binDecode($binary, $mid, $max);
else
return $this->binDecode($binary, $min, $mid);
}
}
測(cè)試
<?php
require_once("db_config.php");
require_once('geohash.class.php');
$geohash=new Geohash;
//經(jīng)緯度轉(zhuǎn)換成Geohash
//獲取附近的信息
$n_latitude = 34.236080797698;
$n_longitude = 109.0145193757;
echo "當(dāng)前位置為：經(jīng)度108.7455，緯度34.3608<br/><br/>
以下網(wǎng)點(diǎn)離我最近：";
//開始
$b_time = microtime(true);
//方案A轮蜕，直接利用數(shù)據(jù)庫存儲(chǔ)函數(shù)昨悼，遍歷排序
//方案B geohash求出附近，然后排序
//當(dāng)前 geohash值
$n_geohash = $geohash->encode($n_latitude,$n_longitude);
//附近
$n = 3;
$like_geohash = substr($n_geohash, 0, $n);
$sql = 'select * from retailersinfotable where geohash like
"'.$like_geohash.'%"';
$query = mysql_query($sql);
if(mysql_num_rows($query))
{
while($row=mysql_fetch_array($query))
{
$data[] = array (
"latitude" =>$row["Latitude"],
"longitude"=>$row["Longitude"],
"name"
=>$row["RetailersName"],
);
}
}
//算出實(shí)際距離
foreach($data as $key=>$val)
{
$distance = getDistance($n_latitude,$n_longitude,$val['latitude'],$val['longitude']
);
$data[$key]['distance'] = $distance;
//排序列
$sortdistance[$key] = $distance;
}
//距離排序
array_multisort($sortdistance,SORT_ASC,$data);
//結(jié)束
$e_time = microtime(true);
echo "（計(jì)算耗時(shí)：" ;
echo $e_time - $b_time;
echo "秒）<br/>";
//var_dump($data);
foreach($data as $key=>$val)
{
echo "</br>";
echo $val['distance']. " 米-------".$val['name'];
}
/**
* @desc 根據(jù)兩點(diǎn)間的經(jīng)緯度計(jì)算距離
* @param float $latitude 緯度值
* @param float $longitude 經(jīng)度值
*/
function getDistance($latitude1, $longitude1, $latitude2, $longitude2)
{
$earth_radius = 6371000; //approximate radius of earth in meters
$dLat = deg2rad($latitude2 - $latitude1);
$dLon = deg2rad($longitude2 - $longitude1);
/*
Using the
Haversine formula
http://en.wikipedia.org/wiki/Haversine_formula
http://www.codecodex.com/wiki/Calculate_Distance_Between_Two_Points_on_a_Globe
驗(yàn)證：百度地圖 http://developer.baidu.com/map/jsdemo.htm#a6_1
calculate the distance
*/
$a = sin($dLat/2) * sin($dLat/2) + cos(deg2rad($latitude1)) * cos(deg2rad($latitude2)) * sin($dLon/2) * sin($dLon/2);
$c = 2 * asin(sqrt($a));
$d = $earth_radius * $c;
return round($d); //四舍五入
}
?>
5.備注
在緯度相等的情況下：
經(jīng)度每隔0.00001度跃洛，距離相差約1米率触；
每隔0.0001度，距離相差約10米汇竭；
每隔0.001度葱蝗，距離相差約100米；
每隔0.01度细燎，距離相差約1000米两曼；
每隔0.1度，距離相差約10000米玻驻。
在經(jīng)度相等的情況下：
緯度每隔0.00001度悼凑，距離相差約1.1米；
每隔0.0001度击狮，距離相差約11米佛析；
每隔0.001度，距離相差約111米彪蓬；
每隔0.01度寸莫，距離相差約1113米；
每隔0.1度档冬，距離相差約11132米膘茎。
6.參考
查找附近點(diǎn)--Geohash方案討論
Haversine formula球面距離公式
球面距離公式代碼實(shí)現(xiàn)
球面距離公式驗(yàn)證
?>
