安全

是什么能讓 APP 快速精準定位到我們的位置?

廣告
廣告

本文作者:smallyang,騰訊 IEG 開發工程師

什么是geohash?它的原理是什么?它幫助我們解決了哪些痛點,本文為你娓娓道來。

本文包含以下內容,閱讀完需要約10分鐘:

  • 我們日常生活中遇到哪些定位的場景
  • 簡單復習一下經緯度
  • geohash原理解析
  • geohash存在的邊界問題
  • 如何解決邊界問題
  • 計算兩點距離的計算
  • geohash 在redis中的實現

我們日常生活中遇到哪些定位的場景

我們上下班經常會用APP打車和共享單車,下面2張圖,應該都很熟悉,打開定位,查找我附近的車,那么,這個是怎么實現的呢?

我腦海中第一個實現方式是:實時上報經緯度。在數據庫里,把經緯度都標記為索引,通過查找對比經緯度的值,來找到附近1km的車子,但是這種做法第一是索引比較多,數值比較大,二是需要循環遍歷經緯度,查詢會很慢,效率很低。

那么,這些APP是怎么做到,既能精準定位,又能快速查找呢?答案就是 geohash

geohash通過算法將1個定位的經度和緯度2個數值,轉換成1個hash字符串。如果2個地方距離越近,那么他們的hash值的前綴越相同。然后通過數據庫中like操作符 “ like wtw366%” 快速查找到附近的車。

比如上海騰訊大廈的經緯度是:(31.1688749, 121.3975184),那么轉換成geohash就是 wtw366ngz5qt,我們想找附近的車子,可以用:

select * from cart where geohash like 'wtw366%' ;
select * from cart where LEFT(geohash, 6) = 'wtw366';

簡單復習一下經緯度

在大致了解什么是geohash之后,我們先來復習一下什么是經緯度(高中學的,可能已經忘記光了(逃)),這對于理解geohash有很大的幫助。

我們將地球鋪平開來,會得到下面這個平面圖。

以赤道和本初子午線為界,將地球分為經度和緯度。赤道是在0度,本初子午線也在0度。以赤道作為經度X橫坐標,以本初子午線作為緯度 Y 豎坐標。

經度(longitude)`和`緯度(latitude)`簡稱?`lng`?和?`lat

其中,從本初子午線向東劃分180度稱為東經,用”E”表示:(0, 180];向西劃分180度為西經,用“W”表示:[-180, 0)

以赤道為0度,向南北各分出90度,南北極的讀數均是90度,北緯用“N”表示 :(0, 90] ,南緯用“S”表示: [-90, 0)

緯線和緯線是角度數值,并不是米。
[ 表示等于, (表示小于

所以,我們常用十字坐標法來表示經緯度坐標圖:

我們一般讀“經緯度”,其實,表示一個定位的書面經緯度是 “(緯度,經度)”。

比如上海騰訊大廈的定位就是:(31.1688749, 121.3975184)表示的是:緯度=31.1688749,經度=121.3975184

geohash原理解析

在了解什么是經緯度之后,現在我們就可以開始來說下geohash的原理了,geohash通過以下步驟,實現了將一個經緯度數子串,轉換成1個hash字符串。

  1. 指定一個位置的經緯度坐標值。
  2. 根據十字坐標圖和二分法,將緯度和經度劃分成1和0的二進制數字串。
  3. 按照“偶數位放經度,奇數位放緯度”算法,合并經度和緯度這2個二進制數字串。
  4. 合并后的二進制數字串,按照從前往后,每隔5位,換算成十進制數字,最后不足5位的用0補齊。
  5. 十進制數字,對應base32字符串算法的所在位置,一一匹配,得到了最后的字符串結果。
  6. 按照進度劃分截取,得到最終的geohash值。

我們按照這個順序,結合實際的例子,依次計算操作一下。

1. 找出一個位置的經緯度

我們可以用各種地圖和定位工具,比如依靠Google地圖,通過定位或者搜索一個地點,就容易找出經緯度。

這樣,我們就找出了上海騰訊大廈的經緯度是 (31.1688749, 121.3975184)

2. 將經緯度按照二分算法變成01二進制

上海騰訊大廈的經緯度是 (31.1688749, 121.3975184)

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

  1. 由于31.1688749屬于(0, 90),所以取編碼為1。
  2. 然后再將(0, 90)分成 (0, 45), (45, 90)兩個區間,而31.1688749位于(0, 45),所以編碼為0。
  3. 然后再將(0, 45)分成 (0, 22.5), (22.5, 45)兩個區間,而31.1688749位于(22.5, 45),所以編碼為1。
    ….
    ….

依次類推可得上海騰訊大廈緯度編碼為:

101011000101010000111101101101

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

110101100101001110111110011010

我們用php代碼來具體實現一下這個算法:

//緯度
$minLat = -90;
$maxLat = 90;

//經度
$minLng = -180;
$maxLng = 180;

//2分查找計算,將經緯度轉換成二進制數字串
$latLength = $lngLength = 0;
$latList = $lngList = [];

//$precision 精度最大是12,代表12個字符,1個字符由5個二進制組成,也就是 12 * 5 = 60
//精度和緯度對半開,得除以2,也就是最大長度為30個二進制。

$originPrecision = 30;

//緯度
while ($latLength < $originPrecision) {

    //大于中間值,則為右區間,值為1 ,反之,則為0
    if ($lat >= $middle = ($minLat + $maxLat) / 2) {
        $latList[] = 1;
        $minLat = $middle;
    } else {
        $latList[] = 0;
        $maxLat = $middle;
    }

    $latLength++;
}

//經度
while ($lngLength < $originPrecision) {

    //大于中間值,則為右區間,值為1 ,反之,則為0
    if ($lng >= $middle = ($minLng + $maxLng) / 2) {
        $lngList[] = 1;
        $minLng = $middle;
    } else {
        $lngList[] = 0;
        $maxLng = $middle;
    }

    $lngLength++;
}

var_dump(implode("", $latList), implode("", $lngList));die;

3. 偶數位放經度,奇數位放緯度

通過二分算法,我們得到了騰訊大廈的緯度和經度的二級制串為:

string(30)?"101011000101010000111101101101"
string(30)?"110101100101001110111110011010"

現在需要按照”偶數位放經度,奇數位放緯度”,將這2個數字串,合二為一。那么這個到底怎么理解呢?我剛開始不理解到底怎么操作,后來經過一系列的思考,可以如下操作:

由于無法用文字表述,我截了個操作圖,如圖上的箭頭操作順序所示,就是把緯度往右移動一個位置,然后依次串起來。

用php代碼實現,或許看起來更好理解:

//偶數位放經度,奇數位放緯度
$stringList = '';
 for ($i = 0; $i < 30; $i++) {
    $stringList .= $lngList[$i];
    $stringList .= $latList[$i];
}
var_dump($stringList);die;

這樣,合并之后,我們得了一個60個字符長度的的二進制數字串:

string(60)?"111001100111100000110011000110101000111111111001011011011001"

4. 二進制轉換成十進制

我們把這個60位的二進制,按照從左往右,每5位劃分成1個組,最后一組如果不足5位就用0補齊到5位。劃分后如下所示:

11100?11001?11100?00011?00110?00110?10100?01111?11111?00101?10110?11001

然后,把分好的二進制,轉換成十進制:

?28?25?28?3?6?6?20?15?31?5?22?25

用php實現也很簡單:

$stringList = "111001100111100000110011000110101000111111111001011011011001";

//二進制轉成十進制,5個一組
$stringListLen = strlen($stringList) / 5;
$code = [];
for ($i = 0; $i < $stringListLen; $i++) {
    $code[] = bindec(substr($stringList, 5 * $i, 5));
}

var_dump(implode(" ",$code));die;

5. 匹配對應base32表算法的所在位置

base32表是用0-9、b-z(去掉a, i, l, o)這32個字母進行組合的編碼集合,base-32如下所示:

0123456789bcdefghjkmnpqrstuvwxyz

為了更好理解和一一對應,我們把base32各個字符的位置信息和它的字符串用表對應起來:

所以, 28 25 28 3 6 6 20 15 31 5 22 25 對應上面的表的位置就得到了,是:

wtw366ngz5qt

同樣,我們也用php算法來實現一下:

//base32 映射
$base32Code = "0123456789bcdefghjkmnpqrstuvwxyz";
$encodeString = '';
foreach ($code as $value) {
    $encodeString .= $base32Code{$value};
}

var_dump($encodeString);die;

這樣,最后我們得到了,上海騰訊大廈的經緯度(31.1688749, 121.3975184) 對應的 geohash 為 wtw366ngz5qt

geohash 的精度問題

geohash其實表示的是一個矩形的塊狀區間,它總共分成最大12個字符串,也就是表示從 1-12 級。字符數越大,塊區間就越小,那么定位就越精準。

我們剛才計算上海騰訊大廈的geohash采用的是12級,基本計算出來的位置就是毫秒級別了,可以說是非常的精準了。

上面是geohash字符串長度對應的區間精度,我們可以看到,當geohash為12位時,表示是37毫米范圍的區間,已經是非常的精準了。當geohash為6位時,表示為1.2k米范圍內的矩形位置。

所以,當2個定位的geohash 前7位是一樣的時,表示他們在附近1.2km的范圍內。

那我們還是用騰訊大廈的geohash值,分別截取經度為前7,6,5位看看,在地圖上是怎么樣的:

所以,根據上面的圖,隨著字符越來越少,精度越來越小,這個矩形也越來越大,這一整塊區間都共用一個geohash來表示。在實際應用中,我們就可以動態的調整精度,實現更大或者更小范圍內的搜索,既能精準定位,又可以隱藏住一個地點的具區位信息。

geohash存在的邊界問題

由于geohash表示的是一個區塊信息,在同一個區塊里的2個位置,它會認為是最近的,然而,其實更近的位置可能剛好在另一個區間,這樣就造成了不匹配的問題。這就存在一個邊界問題。

我們用實際例子來看。我們想找騰大附近1.5km范圍內的便利店,我們選取geohash精度為6。園區有2家 A 和 B。B距離我們更近一點,但是,由于A 和騰大在一個hash區塊內,所以,就得出了A是最佳的選擇。這就是邊界的問題。

如何解決邊界問題

那么如何解決這個邊界問題,給出最近最優的算法方案呢?答案就是:把定位附近的8個方向的geohash都算出來。最后分別計算這些點和自己的距離(由于范圍很小,點的數量就也很少,計算量就很少)過濾掉不滿足條件的點就ok了。

計算兩點距離的計算

通過余弦定理以及弧度計算方法,最終推導出來的算式A為:

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

目前大多使用的是Google公開的距離計算公司,推導算式B為:

$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為地球半徑

用PHP實現一下:

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

/*
 *求兩個已知經緯度之間的距離,單位為米
 * @param lat1,lat2 緯度
 * @param lng1,lng2 經度
 * @return float 距離,單位米
*/
function getDistanceByGoogle($lat1, $lng1, $lat2, $lng2)
{
    //地球半徑
    $R = 6378137;

    //deg2rad()函數將角度轉換為弧度
    $radLat1 = deg2rad($lat1);
    $radLat2 = deg2rad($lat2);
    $radLng1 = deg2rad($lng1);
    $radLng2 = deg2rad($lng2);
    $a = $radLat1 - $radLat2;
    $b = $radLng1 - $radLng2;

    $s = 2 * asin(sqrt(pow(sin($a / 2), 2) + cos($radLat1) * cos($radLat2) * pow(sin($b / 2), 2))) * $R;
    return $s;
}

geohash 在redis中的實現

redis在 3.2.0中加入了geo相關的命令,對geohash的支持。

redis中經緯度使用52位的整數進行編碼,放進zset中,zset的value元素是key,score是GeoHash的52位整數值。在使用redis進行Geo查詢時,其內部對應的操作其實只是zset(skiplist)的操作。通過zset的score進行排序就可以得到坐標附近的其它元素,通過將score還原成坐標值就可以得到元素的原始坐標

redis中處理這些地理位置坐標點的思想是: 二維平面坐標點 —> 一維整數編碼值 —> zset(score為編碼值) —> zrangebyrank(獲取score相近的元素)、zrangebyscore —> 通過score(整數編碼值)反解坐標點 —> 附近點的地理位置坐標。

redis 中有6個命令,對地理位置的算法支持,可以去redis官網具體查看其用法 : https://redis.io/commands#geo

GEOADD
GEOPOS
GEODIST
GEORADIUS
GEORADIUSBYMEMBER
GEOHASH

其他資料

  • geohash在線換算: http://geohash.co/
  • 換算+地圖定位: https://www.movable-type.co.uk/scripts/geohash.html
我還沒有學會寫個人說明!

96秒100億!如何抗住雙11高并發流量?

上一篇

對話蔣杰、丁奇,騰訊云數據庫之路

下一篇

你也可能喜歡

是什么能讓 APP 快速精準定位到我們的位置?

長按儲存圖像,分享給朋友

ITPUB 每周精要將以郵件的形式發放至您的郵箱


微信掃一掃

微信掃一掃
重庆时时后一8码方法 卖果树盆景赚钱吗 欢乐捕鱼人01期 在家做手工赚钱有什么项目 腾讯游戏麻将 福彩3d杀号定胆 彩票中奖海南 北京11选五开奖走势图 kk棋牌官网 七星彩內部3组直码 五子棋大师技巧 开个室内装饰公司赚钱吗 财神捕鱼送金币 天津体彩十一选五 旅游运营商怎么赚钱吗 天津十一选五规则 东莞市做什么生意赚钱