APP中 “附近的人” 原理和4种算法实现方式 |
您所在的位置:网站首页 › 搜索附近的安卓手机店铺有哪些 › APP中 “附近的人” 原理和4种算法实现方式 |
在这篇文章中:
引言 昨天一位粉丝和我讨论了一道面试题,个人觉得比较有意义,这里整理了一下分享给大家,愿小伙伴们面试路上少踩坑。面试题目比较简单:“让你实现一个附近的人功能,你有什么方案?”,这道题其实主要还是考察大家对于技术的广度,本文介绍几种方案,给大家一点思路,避免在面试过程中语塞而影响面试结果,如有不严谨之处,还望亲人们温柔指正! “附近的人” 功能生活中是比较常用的,像外卖app附近的餐厅,共享单车app里附近的车辆。既然常用面试被问的概率就很大,所以下边依次来分析基于mysql数据库、Redis、 MongoDB实现的 “附近的人” 功能。 科普:世界上标识一个位置,通用的做法就使用经、纬度。经度的范围在 (-180, 180],纬度的范围 在(-90, 90],纬度正负以赤道为界,北正南负,经度正负以本初子午线 (英国格林尼治天文台) 为界,东正西负。比如:望京摩托罗拉大厦的经、纬度(116.49141,40.01229)全是正数,就是因为我国位于东北半球。 一、“附近的人”原理 “附近的人” 也就是常说的 LBS (Location Based Services,基于位置服务),它围绕用户当前地理位置数据而展开的服务,为用户提供精准的增值服务。 “附近的人” 核心思想如下: 1.以 “我” 为中心,搜索附近的用户 2.以 “我” 当前的地理位置为准,计算出别人和 “我” 之间的距离 3.按 “我” 与别人距离的远近排序,筛选出离我最近的用户或者商店等 二、什么是GeoHash算法? 在说 “附近的人” 功能的具体实现之前,先来认识一下GeoHash 算法,因为后边会一直和它打交道。定位一个位置最好的办法就是用经、纬度标识,但经、纬度它是二维的,在进行位置计算的时候还是很麻烦,如果能通过某种方法将二维的经、纬度数据转换成一维的数据,那么比较起来就要容易的多,因此GeoHash算法应运而生。 GeoHash算法将二维的经、纬度转换成一个字符串,例如:下图中9个GeoHash字符串代表了9个区域,每一个字符串代表了一矩形区域。而这个矩形区域内其他的点(经、纬度)都用同一个GeoHash字符串表示。 比如:WX4ER区域内的用户搜索附近的餐厅数据,由于这区域内用户的GeoHash字符串都是WX4ER,故可以把WX4ER当作key,餐厅信息作为value进行缓存;而如果不使用GeoHash算法,区域内的用户请求餐厅数据,用户传来的经、纬度都是不同的,这样缓存不仅麻烦且数据量巨大。 GeoHash字符串越长,表示的位置越精确,字符串长度越长代表在距离上的误差越小。下图geohash码精度表: 而且字符串越相似表示距离越相近,字符串前缀匹配越多的距离越近。比如:下边的经、纬度就代表了三家距离相近的餐厅。 让大家简单了解什么是GeoHash算法,方便后边内容展开,GeoHash算法内容比较高深,感兴趣的小伙伴自行深耕一下,这里不占用过多篇幅(其实是我懂得太肤浅,哭唧唧~)。 三、基于Mysql 此种方式是纯基于mysql实现的,未使用GeoHash算法。 1、设计思路 以用户为中心,假设给定一个500米的距离作为半径画一个圆,这个圆型区域内的所有用户就是符合用户要求的 “附近的人”。但有一个问题是圆形有弧度啊,直接搜索圆形区域难度太大,根本无法用经、纬度直接搜索。 但如果在圆形外套上一个正方形,通过获取用户经、纬度的最大最小值(经、纬度 + 距离),再根据最大最小值作为筛选条件,就很容易将正方形内的用户信息搜索出来。 那么问题又来了,多出来一些面积肿么办? 我们来分析一下,多出来的这部分区域内的用户,到圆点的距离一定比圆的半径要大,那么我们就计算用户中心点与正方形内所有用户的距离,筛选出所有距离小于等于半径的用户,圆形区域内的所用户即符合要求的“附近的人”。 2、利弊分析 纯基于 mysql 实现 “附近的人”,优点显而易见就是简单,只要建一张表存下用户的经、纬度信息即可。缺点也很明显,需要大量的计算两个点之间的距离,非常影响性能。 3、实现 创建一个简单的表用来存放用户的经、纬度属性。 计算两个点之间的距离,用了一个三方的类库,毕竟自己造的轮子不是特别圆,还有可能是方的,啊哈哈哈~ 获取到外接正方形后,以正方形的最大最小经、纬度值搜索正方形区域内的用户,再剔除超过指定距离的用户,就是最终的附近的人。 2 3 /** 4 * 获取附近 x 米的人 5 * 6 * @param distance 搜索距离范围 单位km 7 * @param userLng 当前用户的经度 8 * @param userLat 当前用户的纬度 9 */ 10 @GetMapping("/nearby") 11 public String nearBySearch(@RequestParam("distance") double distance, 12 @RequestParam("userLng") double userLng, 13 @RequestParam("userLat") double userLat) { 14 //1.获取外接正方形 15 Rectangle rectangle = getRectangle(distance, userLng, userLat); 16 //2.获取位置在正方形内的所有用户 17 List users = userMapper.selectUser(rectangle.getMinX(), rectangle.getMaxX(), rectangle.getMinY(), rectangle.getMaxY()); 18 //3.剔除半径超过指定距离的多余用户 19 users = users.stream() 20 .filter(a -> getDistance(a.getLongitude(), a.getLatitude(), userLng, userLat) queryWrapper.or().likeRight("geo_code",a.toBase32())); 39 40 //3.匹配指定精度的geoHash码 41 List users = userGeohashService.list(queryWrapper); 42 //4.过滤超出距离的 43 users = users.stream() 44 .filter(a ->getDistance(a.getLongitude(),a.getLatitude(),userLng,userLat) 米 | 千米 | 英尺 | 英里。WITHDIST:在返回位置对象的同时,将位置对象与中心之间的距离也一并返回。距离的单位和用户给定的范围单位保持一致。WITHCOORD:将位置对象的经度和维度也一并返回。WITHHASH:以 52 位有符号整数的形式,返回位置对象经过原始 geohash 编码的有序集合分值。这个选项主要用于底层应用或者调试,实际中的作用并不大。ASC | DESC:从近到远返回位置对象元素 | 从远到近返回位置对象元素。COUNT count:选取前N个匹配位置对象元素。(不设置则返回所有元素)STORE key:将返回结果的地理位置信息保存到指定key。STORedisT key:将返回结果离中心点的距离保存到指定key。例如下边命令:获取当前位置周边500米内的所有饭店。 Redis内部使用有序集合(zset)保存用户的位置信息,zset中每个元素都是一个带位置的对象,元素的score值为通过经、纬度计算出的52位geohash值。 2、利弊分析 redis实现附近的人效率比较高,集成也比较简单,而且还支持对距离排序。不过,结果存在一定的误差,要想让结果更加精确,还需要手动将用户中心位置与其他用户位置计算距离后,再一次进行筛选。 3、实现 以下就是Java redis实现版本,代码非常的简洁。 2 private RedisTemplate redisTemplate; 3 4 //GEO相关命令用到的KEY 5 private final static String KEY = "user_info"; 6 7 public boolean save(User user) { 8 Long flag = redisTemplate.opsForGeo().add(KEY, new RedisGeoCommands.GeoLocation( 9 user.getName(), 10 new Point(user.getLongitude(), user.getLatitude())) 11 ); 12 return flag != null && flag > 0; 13 } 14 15 /** 16 * 根据当前位置获取附近指定范围内的用户 17 * @param distance 指定范围 单位km ,可根据{@link org.springframework.data.geo.Metrics} 进行设置 18 * @param userLng 用户经度 19 * @param userLat 用户纬度 20 * @return 21 */ 22 public String nearBySearch(double distance, double userLng, double userLat) { 23 List users = new ArrayList(); 24 // 1.GEORADIUS获取附近范围内的信息 25 GeoResults reslut = 26 redisTemplate.opsForGeo().radius(KEY, 27 new Circle(new Point(userLng, userLat), new Distance(distance, Metrics.KILOMETERS)), 28 RedisGeoCommands.GeoRadiusCommandArgs.newGeoRadiusArgs() 29 .includeDistance() 30 .includeCoordinates().sortAscending()); 31 //2.收集信息,存入list 32 List content = reslut.getContent(); 33 //3.过滤掉超过距离的数据 34 content.forEach(a-> users.add( 35 new User().setDistance(a.getDistance().getValue()) 36 .setLatitude(a.getContent().getPoint().getX()) 37 .setLongitude(a.getContent().getPoint().getY()))); 38 return JSON.toJSONString(users); 39 }六、MongoDB + 2d索引 1、设计思路 MongoDB实现附近的人,主要是通过它的两种地理空间索引 2dsphere 和 2d。两种索引的底层依然是基于Geohash来进行构建的。但与国际通用的Geohash还有一些不同,具体参考官方文档。 2dsphere 索引仅支持球形表面的几何形状查询。 2d 索引支持平面几何形状和一些球形查询。虽然2d 索引支持某些球形查询,但 2d 索引对这些球形查询时,可能会出错。所以球形查询尽量选择 2dsphere索引。 尽管两种索引的方式不同,但只要坐标跨度不太大,这两个索引计算出的距离相差几乎可以忽略不计。 2、实现 首先插入一批位置数据到MongoDB, collection为起名 hotel,相当于MySQL的表名。两个字段name名称,location 为经、纬度数据对。 展开阅读全文本文系作者在时代Java发表,未经许可,不得转载。 如有侵权,请联系[email protected]删除。 编辑于 2020-04-22 14:33:192020-04-22 14:33:19 举报 分享分享文章到朋友圈 分享文章到 QQ 分享文章到微博 复制文章链接到剪贴板关注时代Java |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |