查找附近的xxx 球面距離以及Geohash方案探讨

http://www.wubiao.info/372

随着移動終端的普及，很多應用都基于LBS功能，附近的某某（餐館、銀行、妹紙等等）。

基礎資料中，一般儲存了目标位置的經緯度；利用使用者提供的經緯度，進行對比，進而獲得是否在附近。

目标：

查找附近的XXX，由近到遠傳回結果，且結果中有與目标點的距離。

針對查找附近的XXX，提出兩個方案，如下：

一、方案A:

=================================================================================================

抽象為球面兩點距離的計算，即已知道球面上兩點的經緯度；

點（緯度，經度），A($radLat1,$radLng1)、B($radLat2,$radLng2);

優點：通俗易懂，部署簡單便捷

缺點：每次都會查詢資料庫，性能堪憂

1、推導

通過餘弦定理以及弧度計算方法，最終推導出來的算式A為：

1	$s = acos(cos($radLat1)*cos($radLat2)*cos($radLng1-$radLng2)+sin($radLat1)*sin($radLat2))*$R;

目前網上大多使用Google公開的距離計算公司，推導算式B為：

1	$s = 2*asin(sqrt(pow(sin(($radLat1-$radLat2) /2 ),2)+cos($radLat1)*cos($radLat2)*pow(sin(($radLng1-$radLng2) /2 ),2)))*$R;

其中 :

$radLat1、$radLng1，$radLat2，$radLng2 為弧度

$R 為地球半徑

2、通過測試兩種算法，結果相同且都正确，但通過PHP代碼測試，兩點間距離，10W次性能對比，自行推導版本計算時長算式B較優，如下：

//算式A

0.56368780136108float(431)

0.57460689544678float(431)

0.59051203727722float(431)

//算式B

0.47404885292053float(431)

0.47808718681335float(431)

0.47946381568909float(431)

3、是以采用數學方法推導出的公式:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

<?php // 根據經緯度計算距離 其中A($lat1,$lng1)、B($lat2,$lng2) public static function getDistance($lat1,$lng1,$lat2,$lng2) { // 地球半徑 $R = 6378137; // 将角度轉為狐度 $radLat1 = deg2rad($lat1); $radLat2 = deg2rad($lat2); $radLng1 = deg2rad($lng1); $radLng2 = deg2rad($lng2); // 結果 $s = acos(cos($radLat1)*cos($radLat2)*cos($radLng1-$radLng2)+sin($radLat1)*sin($radLat2))*$R; // 精度 $s = round($s* 10000) /10000 ; return round($s); } ?>

4、在實際應用中，需要從資料庫中周遊取出符合條件，以及排序等操作，

将所有資料取出，然後通過PHP循環對比，篩選符合條件結果，顯然性能低下；是以我們利用下Mysql存儲函數來解決這個問題吧。

4.1、建立Mysql存儲函數,并對經緯度字段建立索引

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

DELIMITER $$ CREATE DEFINER=`root`@`%` FUNCTION `GETDISTANCE`(lat1 DOUBLE, lng1 DOUBLE, lat2 DOUBLE, lng2 DOUBLE) RETURNS double READS SQL DATA DETERMINISTIC BEGIN DECLARE RAD DOUBLE; DECLARE EARTH_RADIUS DOUBLE DEFAULT 6378137; DECLARE radLat1 DOUBLE; DECLARE radLat2 DOUBLE; DECLARE radLng1 DOUBLE; DECLARE radLng2 DOUBLE; DECLARE s DOUBLE; SET RAD = PI() / 180.0; SET radLat1 = lat1 * RAD; SET radLat2 = lat2 * RAD; SET radLng1 = lng1 * RAD; SET radLng2 = lng2 * RAD; SET s = ACOS(COS(radLat1)*COS(radLat2)*COS(radLng1-radLng2)+SIN(radLat1)*SIN(radLat2))*EARTH_RADIUS; SET s = ROUND(s * 10000) / 10000; RETURN s; END$$ DELIMITER ;

4.2、查詢SQL

通過SQL，可設定距離以及排序；可搜尋出符合條件的資訊，以及有一個較好的排序

1	SELECT *,latitude,longitude,GETDISTANCE(latitude,longitude,30.663262,104.071619) AS distance FROM  mb_shop_ext where 1 HAVING distance<1000 ORDER BY distance ASC LIMIT 0,10

二、方案B

=================================================================================================

Geohash算法；geohash是一種位址編碼，它能把二維的經緯度編碼成一維的字元串。

比如，成都永豐立交的編碼是wm3yr31d2524

優點:

1、利用一個字段，即可存儲經緯度；搜尋時，隻需一條索引，效率較高

2、編碼的字首可以表示更大的區域，查找附近的，非常友善。 SQL中，LIKE ‘wm3yr3%’，即可查詢附近的所有地點。

3、通過編碼精度可模糊坐标、隐私保護等。

缺點: 距離和排序需二次運算（篩選結果中運作，其實挺快）

1、geohash的編碼算法

成都永豐立交經緯度(30.63578,104.031601)

1.1、緯度範圍(-90, 90)平分成兩個區間(-90, 0)、(0, 90)， 如果目标緯度位于前一個區間，則編碼為0，否則編碼為1。

由于30.625265屬于(0, 90)，是以取編碼為1。

然後再将(0, 90)分成 (0, 45), (45, 90)兩個區間，而39.92324位于(0, 45)，是以編碼為0，

然後再将(0, 45)分成 (0, 22.5), (22.5, 45)兩個區間，而39.92324位于(22.5, 45)，是以編碼為1，

依次類推可得永豐立交緯度編碼為101010111001001000100101101010。

1.2、經度也用同樣的算法，對(-180, 180)依次細分，(-180，0)、(0,180) 得出編碼110010011111101001100000000000

1.3、合并經緯度編碼，從高到低，先取一位經度，再取一位緯度；得出結果 111001001100011111101011100011000010110000010001010001000100

1.4、用0-9、b-z（去掉a, i, l, o）這32個字母進行base32編碼，得到(30.63578,104.031601)的編碼為wm3yr31d2524。

1 2 3 4 5 6

11100 10011 00011 11110 10111 00011 00001 01100 00010 00101 00010 00100 => wm3yr31d2524 十進制  0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15 base32   0   1   2   3   4   5   6   7   8   9   b   c   d   e   f   g 十進制  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31 base32   h   j   k   m   n   p   q   r   s   t   u   v w   x   y   z

2、政策

1、在緯度和經度入庫時，資料庫新加一字段geohash，記錄此點的geohash值

2、查找附近，利用 在SQL中 LIKE ‘wm3yr3%’；且此結果可緩存；在小區域内，不會因為改變經緯度，而重新資料庫查詢

3、查找出的有限結果，如需要求距離或者排序，可利用距離公式和二維資料排序；此時也是少量資料，會很快的。

3、PHP基類

geohash.class.php

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169

<?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); $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); } } ?>

三、測試

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

<?php require_once( 'Mysql.class.php' ); require_once( 'geohash.class.php' ); //mysql $conf = array( 'host' => '127.0.0.1' , 'port' => 3306, 'user' => 'root' , 'password' => '123456' , 'database' => 'mocube' , 'charset' => 'utf8' , 'persistent' => false ); $mysql = new Db_Mysql($conf); $geohash=new Geohash; // 經緯度轉換成Geohash // 擷取附近的資訊 $n_latitude = $_GET[ 'la' ]; $n_longitude = $_GET[ 'lo' ]; // 開始 $b_time = microtime( true ); // 方案A，直接利用資料庫存儲函數，周遊排序 // 方案B geohash求出附近，然後排序 // 目前 geohash值 $n_geohash = $geohash->encode($n_latitude,$n_longitude); // 附近 $n = $_GET[ 'n' ]; $like_geohash = substr($n_geohash, 0, $n); $sql = 'select * from mb_shop_ext where geohash like "' .$like_geohash. '%"' ; echo $sql; $data = $mysql->queryAll($sql); // 算出實際距離 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); // 結束 $e_time = microtime( true ); echo $e_time - $b_time; var_dump($data); // 根據經緯度計算距離 其中A($lat1,$lng1)、B($lat2,$lng2) function getDistance($lat1,$lng1,$lat2,$lng2) { // 地球半徑 $R = 6378137; // 将角度轉為狐度 $radLat1 = deg2rad($lat1); $radLat2 = deg2rad($lat2); $radLng1 = deg2rad($lng1); $radLng2 = deg2rad($lng2); // 結果 $s = acos(cos($radLat1)*cos($radLat2)*cos($radLng1-$radLng2)+sin($radLat1)*sin($radLat2))*$R; // 精度 $s = round($s* 10000) /10000 ; return round($s); } ?>

四、總結

方案B的亮點在于：

1、搜尋結果可緩存，重複使用，不會因為使用者有小範圍的移動，直接穿透資料庫查詢。

2、先縮小結果範圍，再運算、排序，可提升性能。

254條記錄，性能對比，

在實際應用場景中，方案B資料庫搜尋可記憶體緩存；且如資料量更大，方案B結果會更優。

方案A:

0.016560077667236

0.032402992248535

0.040318012237549

方案B

0.0079810619354248

0.0079669952392578

0.0064868927001953

五、其他

兩種方案，根據應用場景以及負載情況合理選擇，當然推薦方案B;

不管哪種方案，都記得，給列加上索引，利于資料庫檢索。