安全

是什么能讓 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 每周精要將以郵件的形式發放至您的郵箱


微信掃一掃

微信掃一掃
30岁的男人干啥赚钱快赚钱多 福建36选7官网 六合现场最快开奖结果 最新福建31选7规则 微乐家乡麻将怎么换头像 第一代捕鱼达人千炮版 兴动哈尔滨麻将客服 捕鱼达人3官方下载 大众在线麻将游戏4人打麻将 天天捕鱼千炮版 下载欢乐真人麻将