PHP進階學習之Geo的地圖定位算法詳解

本文實例講述了PHP進階學習之Geo的地圖定位算法。分享給大家供大家參考，具體如下：

前言

日常開發(fā)中我們經(jīng)常需要查找某個物體的定位,或者查找附近的范圍等，我們自然而然會想到的方法就是利用各種提供服務(wù)的地圖網(wǎng)站的API，基于API，用經(jīng)緯度去實現(xiàn)定位和查找附近范圍等等。然而，由于原理沒有做一個了解和一定的認識，在對比距離遠近關(guān)系或者控制精確程度方面，我們并不了解怎么利用這些經(jīng)緯度數(shù)值去實現(xiàn)距離轉(zhuǎn)化和對比。本章節(jié)我們就來探討一下基于geo的位置算法原理。

概念

1. 緯線：緯線是與地軸垂直的線，著東西方向環(huán)繞地球一周，所有的緯度都是平行的。其中，赤道是最長的緯線，緯度為0度，緯線數(shù)值是角度數(shù)值，從赤道開始分為北緯和南緯，都是0-90°；
2. 經(jīng)線：地球儀上的豎線，是連接南北兩極并且與緯線垂直相交的半圓，子午線為0°，分為西經(jīng)和東經(jīng)，都是0-180°，經(jīng)線也是角度數(shù)值；
3. 經(jīng)緯線和米的換算：經(jīng)度或者緯度0.00001度，約等于1米，這個在GPS測算距離的時候可以體會到，GPS只要精確到小數(shù)點后五位，就是10米范圍內(nèi)的精度；
4. 為了便于理解，將地球看成一個基于經(jīng)緯度線的坐標系。經(jīng)度范圍為-180~180°，緯度范圍為-90~90°，地球上任意一點都可以用經(jīng)緯度這樣兩個維度去唯一確定。

在實際應用中，如果要用兩個維度去確定一個點，則計算量會很大，因為一個二維確定一個平面，如果我們把二維平面上的所有點都用一個數(shù)字表示，即經(jīng)緯度換算成一個字符串，則可以轉(zhuǎn)為一維坐標來表示，大大減少計算量。這就是現(xiàn)在應用廣泛的geoHash。

geoHash：Geohash是公共領(lǐng)域地理編碼系統(tǒng)，它將地理位置編碼為一串字母和數(shù)字。Geohash提供了像任意精度這樣的屬性，以及逐漸從代碼末尾刪除字符以減小其大?。ú⒅饾u失去精度）的可能性。由于逐步精度下降的結(jié)果，附近的地方往往（但不總是）呈現(xiàn)類似的前綴。共享前綴越長，兩個地方越接近。

原理

能將一個地球上的點表示成一串字母，并且相近的地點字母的共同前綴越多。這能讓位置搜索在開發(fā)中變得很容易。它的原理就是依據(jù)上述說的geoHash值。下面就來詳細說明geoHash值是怎么算出來的：

1. 根據(jù)經(jīng)緯度計算GeoHash二進制編碼（以經(jīng)緯度值：(116.389550,39.928167)進行算法說明）
2. 先計算緯度二進制：
   2.1 區(qū)間[-90,90]進行二分為[-90,0),[0,90]，稱為左右區(qū)間，可以確定39.928167屬于右區(qū)間[0,90]，給標記為1；
   2.2 接著將區(qū)間[0,90]進行二分為 [0,45),[45,90]，可以確定39.928167屬于左區(qū)間 [0,45)，給標記為0；
   2.3 遞歸上述過程39.928167總是屬于某個區(qū)間[a,b]。隨著每次迭代區(qū)間[a,b]總在縮小，并越來越逼近39.928167；
   2.4 這樣隨著算法的進行會產(chǎn)生一個序列1011100011的緯度二進制編碼；

3. 同理，計算出地球經(jīng)度二進制，區(qū)間是[-180,180]，可以對經(jīng)度116.389550進行編碼。算出結(jié)果1101001011；

4. 組碼：通過上述計算，緯度產(chǎn)生的編碼為10111 00011，經(jīng)度產(chǎn)生的編碼為11010 01011。偶數(shù)位放經(jīng)度，奇數(shù)位放緯度，把2串編碼組合生成新串：11100 11101 00100 01111。
5. 使用用0-9、b-z（去掉a, i, l, o）這32個字母進行base32編碼，首先將11100 11101 00100 01111轉(zhuǎn)成十進制，對應著28、29、4、15，十進制對應的編碼就是wx4g。

Geohash其實就是將整個地圖或者某個分割所得的區(qū)域進行一次劃分，由于采用的是base32編碼方式，即Geohash中的每一個字母或者數(shù)字（如wx4g0e中的w）都是由5bits組成（2^5 = 32，base32），這5bits可以有32中不同的組合（0~31），這樣我們可以將整個地圖區(qū)域分為32個區(qū)域，通過00000 ~ 11111來標識這32個區(qū)域。第一次對地圖劃分后的情況如下圖所示（每個區(qū)域中的編號對應于該區(qū)域所對應的編碼）：
進行多次分解后，我們就可以得到更精確的位置劃分，如上述計算的wx4g已經(jīng)可以精確到一個城市城區(qū)了：
從上圖中可以看出，相鄰城區(qū)的geoHash值的共同前綴越多，由此我們就可以應用共同前綴來判斷附近相鄰的位置了。當然精確范圍也是根據(jù)經(jīng)緯度和hash值的范圍來確定的，如下表，geo精確到8位的共同前綴，可以表示附近約20米內(nèi)的范圍了：

在PHP中的實現(xiàn)與應用

在了解了geo的位置算法原理后，PHP開發(fā)過程中我們便可以使用這一定位功能，目前解決位置定位和搜索功能的方案有很多種，基于PHP的，從本人自身實踐中推薦一下幾種：

1. 利用現(xiàn)成的地圖API實現(xiàn)geo定位、搜索范圍、計算距離等功能，如國內(nèi)的百度、高德等，很多免費API可以使用；如需更大更精確的范圍，可以使用google的geo api，缺點就是每日請求次數(shù)有限制，如果是企業(yè)級別的應用，付費增加請求次數(shù)的允許權(quán)限是必不可少的。可查閱鏈接：https://developers.google.com/maps/documentation/geocoding/start
2. 通過NoSQL存儲組件實現(xiàn)定位運算和存儲：由于我們經(jīng)常在計算了定位數(shù)據(jù)之后要把數(shù)據(jù)落地，所以目前行業(yè)內(nèi)已經(jīng)有了很多存儲組件提供了直接計算和存儲的方案，如MongoDB，適合在國內(nèi)云平臺直接使用。如果是AWS平臺，也提供了dynamodb這種NoSQL存儲組件。這些存儲組件均可以直接傳入經(jīng)緯度，自動換算為geoHash落地存儲，也提供了直接計算距離，搜索范圍數(shù)據(jù)返回的功能。
3. 本地部署服務(wù)器可用Redis：在Redis3.2版本之后，已經(jīng)提供了GEO的運算、搜索和落地功能，可以結(jié)合新版本的php-redis擴展實現(xiàn)geo的方法。參考鏈接：http://www.redis.cn/commands.html，在PHP中實現(xiàn)對redis的geo操作，可以參考GitHub上面已經(jīng)提供了的方法說明：https://github.com/phpredis/phpredis。redis其實是封裝了方法計算經(jīng)緯度參數(shù)，換算成geohash值作為Zset的Score存入Zset中，所以也可以將其當做一個普通的Zset進行操作。
   實際應用中我們常常以商品、人物作為value值，以geohash值作為score，這樣就可以搜索一定范圍內(nèi)score內(nèi)的人或事物了。如搜索一定半徑內(nèi)的value：

$redis->geoRadius($key, $longitude, $latitude, $radius, $unit [, Array $options]);

4. 利用PHP進行原生geoHash計算：這種方式計算較為復雜，即是根據(jù)geoHash原理，用PHP語言實現(xiàn)了這一算法，也通過PHP計算距離，搜索半徑等。相當于重新造了個輪子，當然如果業(yè)務(wù)復雜度較高，也有必要進行PHP對GeoHash算法的支持，或者自行封裝Geo類。在此推薦GitHub上面一個比較完善的PHP-GEO支持：https://github.com/geocoder-php/Geocoder
   或者如果只需要計算GeoHash值，可以使用網(wǎng)上廣泛轉(zhuǎn)發(fā)的一個計算Hash值的PHP方法：

private $coding = '0123456789bcdefghjkmnpqrstuvwxyz';
/**
* calculate geoHash by longitude and latitude
* @param $lat
* @param $long
* @return string
*/
public function calcGeoHash($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; $istrlen($binary); $i+=5)
{
$n=bindec(substr($binary,$i,5));
$hash=$hash.$this->coding[$n];
}
return $hash;
}
/**
* @param $number
* @return float|int
*/
private function precision($number)
{
$precision=0;
$pt=strpos($number,'.');
if ($pt!==false)
{
$precision=-(strlen($number)-$pt-1);
}
return pow(10,$precision)/2;
}
/**
* @param $number
* @param $min
* @param $max
* @param $bitcount
* @return string
*/
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);
}

總結(jié)

GeoHash算法是一種將二維坐標換算成一位字符串的算法，可以通過不同字符串的共同前綴來判斷相距遠近。在日常業(yè)務(wù)中也常常需要用到，本文也介紹了不同的實現(xiàn)方法，具體實現(xiàn)方案還需以實際業(yè)務(wù)需要為準。如果屬于精確度要求很高或者企業(yè)級的大規(guī)模應用，可以首先考慮MongoDB或者其他提供Geo功能的存儲組件，如果較為輕量級，可以借助第三方地區(qū)API、或者利用redis做geo的簡單應用。如果業(yè)務(wù)需求復雜度不高，在這里并不推薦直接使用PHP寫，畢竟效率會比較低，而且這也不是業(yè)務(wù)關(guān)注的重點，所以沒必要重新造輪子。

更多關(guān)于PHP相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《php面向?qū)ο蟪绦蛟O(shè)計入門教程》、《PHP數(shù)組(Array)操作技巧大全》、《PHP基本語法入門教程》、《PHP運算與運算符用法總結(jié)》、《php字符串(string)用法總結(jié)》、《php+mysql數(shù)據(jù)庫操作入門教程》及《php常見數(shù)據(jù)庫操作技巧匯總》

希望本文所述對大家PHP程序設(shè)計有所幫助。