浅谈附近地点搜索

褰辩话发布于2019-07-01 14:19 / 2260人阅读

摘要：编码的前缀可以表示更大的区域，查找附近的，非常方便。百度拾取坐标地址编码精度为位时，大概为附近千米。在经度相等的情况下纬度每隔度，距离相差约米每隔度，距离相差约米每隔度，距离相差约米每隔度，距离相差约米每隔度，距离相差约米。

随着移动端的普及，很多 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/lbsa...

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 类库。

可以关注微信公众号，回复 “geohash”，即可获取。

推荐阅读

系统的讲解 - SSO 单点登录

系统的讲解 - PHP WEB 安全防御

系统的讲解 - PHP 缓存技术

系统的讲解 - PHP 接口签名验证

系统的讲解 - PHP 浮点数高精度运算

GPU云服务器云服务器设计浅谈浅谈javascript 浅谈sdwan解决方案浅谈正则表达式

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/31965.html

从拿到班车手册.xls到搜索附近班车地点

摘要：辗转流传出班车手册后发现搜索实在是太不方便了，于是有了一个主义，想做一个可以搜索房子地址，找出附近班车点类似大众点评的定位搜索附近餐馆的功能。起因七月份要去某厂报道了，异地租房的时候发现想租一个有公司班车的地方，却不知道哪里有班车。辗转流传出班车手册后发现搜索实在是太不方便了，于是有了一个主义，想做一个可以搜索房子地址，找出附近班车点（类似大众点评的定位搜索附近餐馆的功能）。现在做...

jhhfft 2019-08-22 17:31 评论0 收藏0
php资料集

摘要：简单字符串缓存实战完整实战种设计模式设计模式是面向对象的最佳实践成为专业程序员路上用到的各种优秀资料神器及框架成为一名专业程序员的道路上，需要坚持练习学习与积累，技术方面既要有一定的广度，更要有自己的深度。微型新闻系统的开发（PHP 5.4 + MySQL 5.5）微型新闻系统的开发（PHP 5.4 + MySQL 5.5）九个很有用的 PHP 代码 php 代码国内值得关注的...

RobinQu 2019-06-28 14:30 评论0 收藏0
年终总结 - 成长

摘要：有欢笑有感动有甜蜜有收获。整理相关文章半年时间的成果掘金关注数微信公众号关注数简书关注数关于读书核心技术与最佳实践大型网站技术架构未来边缘明朝那些事儿三体在读，未读完。漫漫人生路，积极复出和奉献才能有美好的回报。人生天地之间，若白驹之过隙，忽然而已。——《庄子·知北游》 2016年时间过得很快。有欢笑、有感动、有甜蜜、有收获。关于工作承蒙领导一直以来的关照，对我信任。工...

Honwhy 2019-06-27 15:11 评论0 收藏0