大数据

浅谈附近地点搜索

随着移动端的普及,很多 App应用 都有 LBS 功能。

附近的银行、

附近的饭店、

附近的超市、

附近的厕所、

以上的需求很类似,实现的原理也大致相同。

定位方式有哪些?

  • 基于 GPS
  • 基于运营商基站
  • 基于WiFi
  • 基于蓝牙
  • 基于传感器

我们主要应用基于 GPS 进行定位。

其他定位方式,大家可以 Google 了解下。

实现原理

以获取附近的饭店为例子。

数据采集:

首先将饭店数据(经纬度和其他信息)存储到数据库中。

附近算法:

用户将自己的坐标传给服务端,服务端通过用户当前坐标,查询出附近的饭店。

接下来,我们就主要聊聊如何通过坐标查询出附近饭店的算法?

当当当当,GeoHash 闪亮登场。

GeoHash 算法

GeoHash 算法 是一种地址编码,它能把二维的经纬度编码成一维的字符串。

重点:经纬度坐标为GPS坐标。

优点:

  • 利用一个字段表示经纬度,给字段加上索引,效率高。
  • 编码的前缀可以表示更大的区域,查找附近的,非常方便。
  • 编码暴露,也不会暴露自己的精确坐标,有助于隐私保护。

算法:

以 经纬度 (39.92324,116.3906) 为例进行分析。

首先将纬度范围 (-90, 90) 平分成两个区间 (-90,0)、(0, 90)。

如果目标纬度位于前一个区间,则编码为0,否则编码为1。

由于 39.92324 属于 (0, 90),所以取编码为1。

然后再将 (0, 90) 分成 (0, 45), (45, 90)两个区间。

然而 39.92324 位于 (0, 45),所以编码为 0。

以此类推,直到精度符合要求为止。

得到纬度编码为 1011 1000 1100 0111 1001。

纬度范围 区间(0) 区间(1) 区间
(-90, 90) (-90, 0.0) (0.0, 90) 1
(0.0, 90) (0.0, 45.0) (45.0, 90) 0
(0.0, 45.0) (0.0, 22.5) (22.5, 45.0) 1
(22.5, 45.0) (22.5, 33.75) (33.75, 45.0) 1
(33.75, 45.0) (33.75, 39.375) (39.375, 45.0) 1
(39.375, 45.0) (39.375, 42.1875) (42.1875, 45.0) 0
(39.375, 42.1875) (39.375, 40.7812) (40.7812, 42.1875) 0
(39.375, 40.7812) (39.375, 40.0781) (40.0781, 40.7812) 0
(39.375, 40.0781) (39.375, 39.7265) (39.7265, 40.0781) 1
(39.7265, 40.0781) (39.375, 39.7265) (39.7265, 40.0781) 1
(39.9023, 40.0781) (39.9023, 39.9902) (39.9902, 40.0781) 0
(39.9023, 39.9902) (39.9023, 39.9462) (39.9462, 39.9902) 0
(39.9023, 39.9462) (39.9023, 39.9243) (39.9243, 39.9462) 0
(39.9023, 39.9243) (39.9023, 39.9133) (39.9133, 39.9243) 1
(39.9133, 39.9243) (39.9133, 39.9188) (39.9188, 39.9243) 1
(39.9188, 39.9243) (39.9188, 39.9215) (39.9215, 39.9243) 1

经度也用同样的算法,对 (-180, 180) 依次细分。

得到经度的编码为 1101 0010 1100 0100 0100。

经度范围 区间(0) 区间(1) 区间
(-180, 180) (-180, 0.0) (0.0, 180) 1
(0.0, 180) (0.0, 90.0) (90.0, 180) 1
(90.0, 180) (90.0, 135.0) (135.0, 180) 0
(90.0, 135.0) (90.0, 112.5) (112.5, 135.0) 1
(112.5, 135.0) (112.5, 123.75) (123.75, 135.0) 0
(112.5, 123.75) (112.5, 118.125) (118.125, 123.75) 0
(112.5, 118.125) (112.5, 115.312) (115.312, 118.125) 1
(115.312, 118.125) (115.312, 116.718) (116.718, 118.125) 0
(115.312, 116.718) (115.312, 116.015) (116.015, 116.718) 1
(116.015, 116.718) (116.015, 116.367) (116.367, 116.718) 1
(116.367, 116.718) (116.367, 116.542) (116.542, 116.718) 0
(116.367, 116.542) (116.367, 116.455) (116.455, 116.542) 0
(116.367, 116.455) (116.367, 116.411) (116.411, 116.455) 0
(116.367, 116.411) (116.367, 116.389) (116.389, 116.411) 1
(116.389, 116.411) (116.389, 116.400) (116.400, 116.411) 0
(116.389, 116.400) (116.389, 116.394) (116.394, 116.400) 0

接下来将经度和纬度的编码合并,奇数位是纬度,偶数位是经度。

得到编码 11100 11101 00100 01111 00000 01101 01011 00001。

最后,用0-9、b-z(去掉a, i, l, o)这32个字母进行base32编码。

得到 (39.92324, 116.3906) 的编码为 wx4g0ec1。

十进制 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

解码算法与编码算法相反,先进行base32解码,然后分离出经纬度。

最后根据二进制编码对经纬度范围进行细分即可。

程序处理

在经度和纬度入库的时候,数据库新增一个字段geohash,记录此点的geohash值。

在查询附近的时候,利用SQL中 like ‘wx4g0e%’ 进行查询。

查询出来的结果,根据距离大小进行排序。

geohash 字段可以使用索引。

//[PHP Code] 生成GeoHashCode编码

$longitude = ''; //经度

$latitude = '';  //纬度

$objGeoHash = new Geohash(); //文末有该类的下载方式

$strGeoHashCode = $objGeoHash->encode($latitude, $longitude);

//在采集数据的时候,这个值保存到数据中即可。
/**
 * [PHP Code] 根据经纬度计算两点之间的记录
 * @param $lat1 纬度1
 * @param $lng1 经度1
 * @param $lat2 纬度2
 * @param $lng2 经度2
 * @return float 单位(米)
 */
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);
}

备注

请了解,百度坐标与GPS坐标互转。

请了解,谷歌坐标与GPS坐标互转。

请了解,腾讯坐标与GPS坐标互转。

百度拾取坐标地址:

http://api.map.baidu.com/lbsapi/getpoint/index.html

GeoHash 编码精度为6位时,大概为附近1千米。

在纬度相等的情况下:

经度每隔0.00001度,距离相差约1米;

每隔0.0001度,距离相差约10米;

每隔0.001度,距离相差约100米;

每隔0.01度,距离相差约1000米;

每隔0.1度,距离相差约10000米。

在经度相等的情况下:

纬度每隔0.00001度,距离相差约1.1米;

每隔0.0001度,距离相差约11米;

每隔0.001度,距离相差约111米;

每隔0.01度,距离相差约1113米;

每隔0.1度,距离相差约11132米。

实际情况据需求而定,可在此基础上进行扩展。

如果大家需要下载 PHP GeoHash 类库。

可以私信我~


Thanks ~

发表评论