| 4种“附近的人”实现方式 | 您所在的位置：网站首页 › 微信如何查找附近的人我打过招呼的 › 4种“附近的人”实现方式 |
4种“附近的人”实现方式
|
“附近的人” 功能生活中是比较常用的，像外卖app附近的餐厅，共享单车app里附近的车辆。既然常用面试被问的概率就很大，所以下边依次来分析基于MySQL数据库、Redis、 MongoDB实现的 “附近的人” 功能。 科普：世界上标识一个位置，通用的做法就使用经、纬度。经度的范围在 (-180, 180]，纬度的范围 在(-90, 90]，纬度正负以赤道为界，北正南负，经度正负以本初子午线 (英国格林尼治天文台) 为界，东正西负。比如：望京摩托罗拉大厦的经、纬度(116.49141，40.01229)全是正数，就是因为我国位于东北半球。 一、“附近的人”原理“附近的人” 也就是常说的 LBS (Location Based Services，基于位置服务)，它围绕用户当前地理位置数据而展开的服务，为用户提供精准的增值服务。 “附近的人” 核心思想如下： 以 “我” 为中心，搜索附近的用户以 “我” 当前的地理位置为准，计算出别人和 “我” 之间的距离按 “我” 与别人距离的远近排序，筛选出离我最近的用户或者商店等
二、什么是GeoHash算法?
在说 “附近的人” 功能的具体实现之前，先来认识一下GeoHash 算法，因为后边会一直和它打交道。定位一个位置最好的办法就是用经、纬度标识，但经、纬度它是二维的，在进行位置计算的时候还是很麻烦，如果能通过某种方法将二维的经、纬度数据转换成一维的数据，那么比较起来就要容易的多，因此GeoHash算法应运而生。 GeoHash算法将二维的经、纬度转换成一个字符串，例如：下图中9个GeoHash字符串代表了9个区域，每一个字符串代表了一矩形区域。而这个矩形区域内其他的点(经、纬度)都用同一个GeoHash字符串表示。
GeoHash字符串越长，表示的位置越精确，字符串长度越长代表在距离上的误差越小。下图geohash码精度表： geohash码长度宽度高度15,009.4km21,252.3km624.1km3156.5km156km439.1km19.5km54.9km4.9km61.2km609.4m7152.9m152.4m838.2m19m94.8m4.8m101.2m59.5cm1114.9cm14.9cm123.7cm1.9cm而且字符串越相似表示距离越相近，字符串前缀匹配越多的距离越近。比如：下边的经、纬度就代表了三家距离相近的餐厅。 商户经纬度Geohash字符串串串香116.402843,39.999375wx4er9v火锅116.3967,39.99932wx4ertk烤肉116.40382,39.918118wx4erfe 三、基于MySQL此种方式是纯基于mysql实现的，未使用GeoHash算法。 1、设计思路 以用户为中心，假设给定一个500米的距离作为半径画一个圆，这个圆型区域内的所有用户就是符合用户要求的 “附近的人”。但有一个问题是圆形有弧度啊，直接搜索圆形区域难度太大，根本无法用经、纬度直接搜索。 但如果在圆形外套上一个正方形，通过获取用户经、纬度的最大最小值(经、纬度 + 距离)，再根据最大最小值作为筛选条件，就很容易将正方形内的用户信息搜索出来。 那么问题又来了，多出来一些面积肿么办? 我们来分析一下，多出来的这部分区域内的用户，到圆点的距离一定比圆的半径要大，那么我们就计算用户中心点与正方形内所有用户的距离，筛选出所有距离小于等于半径的用户，圆形区域内的所用户即符合要求的“附近的人”。 纯基于 MySQL 实现 “附近的人”，优点显而易见就是简单，只要建一张表存下用户的经、纬度信息即可。缺点也很明显，需要大量的计算两个点之间的距离，非常影响性能。 3、实现 创建一个简单的表用来存放用户的经、纬度属性。 CREATE TABLE `nearby_user` ( `id` int(11) NOT NULL AUTO_INCREMENT, `name` varchar(255) DEFAULT NULL COMMENT '名称', `longitude` double DEFAULT NULL COMMENT '经度', `latitude` double DEFAULT NULL COMMENT '纬度', `create_time` datetime DEFAULT NULL ON UPDATE CURRENT_TIMESTAMP COMMENT '创建时间', PRIMARY KEY (`id`) ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;计算两个点之间的距离，用了一个三方的类库 com.spatial4j spatial4j 0.5获取到外接正方形后，以正方形的最大最小经、纬度值搜索正方形区域内的用户，再剔除超过指定距离的用户，就是最终的附近的人。 private SpatialContext spatialContext = SpatialContext.GEO; /** * 获取附近 x 米的人 * * @param distance 搜索距离范围 单位km * @param userLng 当前用户的经度 * @param userLat 当前用户的纬度 */ @GetMapping("/nearby") public String nearBySearch(@RequestParam("distance") double distance, @RequestParam("userLng") double userLng, @RequestParam("userLat") double userLat) { //1.获取外接正方形 Rectangle rectangle = getRectangle(distance, userLng, userLat); //2.获取位置在正方形内的所有用户 List users = userMapper.selectUser(rectangle.getMinX(), rectangle.getMaxX(), rectangle.getMinY(), rectangle.getMaxY()); //3.剔除半径超过指定距离的多余用户 users = users.stream() .filter(a -> getDistance(a.getLongitude(), a.getLatitude(), userLng, userLat) //默认精度12位 String geoHashCode = GeohashUtils.encodeLatLon(user.getLatitude(),user.getLongitude()); return userGeohashService.save(user.setGeoCode(geoHashCode).setCreateTime(LocalDateTime.now())); } /** * 获取附近指定范围的人 * * @param distance 距离范围（附近多远的用户） 单位km * @param len geoHash的精度（几位的字符串） * @param userLng 当前用户的经度 * @param userLat 当前用户的纬度 * @return json */ @GetMapping("/nearby") public String nearBySearch(@RequestParam("distance") double distance, @RequestParam("len") int len, @RequestParam("userLng") double userLng, @RequestParam("userLat") double userLat) { //1.根据要求的范围，确定geoHash码的精度，获取到当前用户坐标的geoHash码 GeoHash geoHash = GeoHash.withCharacterPrecision(userLat, userLng, len); //2.获取到用户周边8个方位的geoHash码 GeoHash[] adjacent = geoHash.getAdjacent(); QueryWrapper queryWrapper = new QueryWrapper() .likeRight("geo_code",geoHash.toBase32()); Stream.of(adjacent).forEach(a -> queryWrapper.or().likeRight("geo_code",a.toBase32())); //3.匹配指定精度的geoHash码 List users = userGeohashService.list(queryWrapper); //4.过滤超出距离的 users = users.stream() .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米内的所有饭店。 GEORADIUS hotel 119.98866180732716 30.27465803229662 500 m WITHCOORDRedis内部使用有序集合(zset)保存用户的位置信息，zset中每个元素都是一个带位置的对象，元素的score值为通过经、纬度计算出的52位geohash值。 2、利弊分析 Redis实现附近的人效率比较高，集成也比较简单，而且还支持对距离排序。不过，结果存在一定的误差，要想让结果更加精确，还需要手动将用户中心位置与其他用户位置计算距离后，再一次进行筛选 3、实现 以下就是Java Redis实现版本，代码非常的简洁。 @Autowired private RedisTemplate redisTemplate; //GEO相关命令用到的KEY private final static String KEY = "user_info"; public boolean save(User user) { Long flag = redisTemplate.opsForGeo().add(KEY, new RedisGeoCommands.GeoLocation( user.getName(), new Point(user.getLongitude(), user.getLatitude())) ); return flag != null && flag > 0; } /** * 根据当前位置获取附近指定范围内的用户 * @param distance 指定范围 单位km ，可根据{@link org.springframework.data.geo.Metrics} 进行设置 * @param userLng 用户经度 * @param userLat 用户纬度 * @return */ public String nearBySearch(double distance, double userLng, double userLat) { List users = new ArrayList(); // 1.GEORADIUS获取附近范围内的信息 GeoResults reslut = redisTemplate.opsForGeo().radius(KEY, new Circle(new Point(userLng, userLat), new Distance(distance, Metrics.KILOMETERS)), RedisGeoCommands.GeoRadiusCommandArgs.newGeoRadiusArgs() .includeDistance() .includeCoordinates().sortAscending()); //2.收集信息，存入list List content = reslut.getContent(); //3.过滤掉超过距离的数据 content.forEach(a-> users.add( new User().setDistance(a.getDistance().getValue()) .setLatitude(a.getContent().getPoint().getX()) .setLongitude(a.getContent().getPoint().getY()))); return JSON.toJSONString(users); } 六、MongoDB + 2d索引1、设计思路 MongoDB实现附近的人，主要是通过它的两种地理空间索引 2dsphere 和 2d。两种索引的底层依然是基于GeoHash来进行构建的。但与国际通用的GeoHash还有一些不同，具体参考官方文档。 2dsphere 索引仅支持球形表面的几何形状查询。 2d 索引支持平面几何形状和一些球形查询。虽然2d 索引支持某些球形查询，但 2d 索引对这些球形查询时，可能会出错。所以球形查询尽量选择 2dsphere索引。 尽管两种索引的方式不同，但只要坐标跨度不太大，这两个索引计算出的距离相差几乎可以忽略不计。 2、实现 首先插入一批位置数据到MongoDB， collection为起名 hotel，相当于MySQL的表名。两个字段name名称，location 为经、纬度数据对 db.hotel.insertMany([ {'name':'hotel1', location:[115.993121,28.676436]}, {'name':'hotel2', location:[116.000093,28.679402]}, {'name':'hotel3', location:[115.999967,28.679743]}, {'name':'hotel4', location:[115.995593,28.681632]}, {'name':'hotel5', location:[115.975543,28.679509]}, {'name':'hotel6', location:[115.968428,28.669368]}, {'name':'hotel7', location:[116.035262,28.677037]}, {'name':'hotel8', location:[116.024770,28.68667]}, {'name':'hotel9', location:[116.002384,28.683865]}, {'name':'hotel10', location:[116.000821,28.68129]}, ])接下来我们给 location 字段创建一个2d索引，索引的精度通过bits来指定，bits越大，索引的精度就越高。 db.coll.createIndex({'location':"2d"}, {"bits":11111})用geoNear命令测试一下， near 当前坐标(经、纬度)，spherical 是否计算球面距离，distanceMultiplier地球半径，单位是米，默认6378137， maxDistance 过滤条件(指定距离内的用户)，开启弧度需除distanceMultiplier，distanceField 计算出的两点间距离，字段别名(随意取名)。 db.hotel.aggregate({ $geoNear:{ near: [115.999567,28.681813], // 当前坐标 spherical: true, // 计算球面距离 distanceMultiplier: 6378137, // 地球半径,单位是米,那么的除的记录也是米 maxDistance: 2000/6378137, // 过滤条件2000米内，需要弧度 distanceField: "distance" // 距离字段别名 } })看到结果中有符合条件的数据，还多出一个字段distance 刚才设置的别名，代表两点间的距离。 { "_id" : ObjectId("5e96a5c91b8d4ce765381e58"), "name" : "hotel10", "location" : [ 116.000821, 28.68129 ], "distance" : 135.60095397487655 } { "_id" : ObjectId("5e96a5c91b8d4ce765381e51"), "name" : "hotel3", "location" : [ 115.999967, 28.679743 ], "distance" : 233.71915803517447 } { "_id" : ObjectId("5e96a5c91b8d4ce765381e50"), "name" : "hotel2", "location" : [ 116.000093, 28.679402 ], "distance" : 273.26317035334176 } { "_id" : ObjectId("5e96a5c91b8d4ce765381e57"), "name" : "hotel9", "location" : [ 116.002384, 28.683865 ], "distance" : 357.5791936927476 } { "_id" : ObjectId("5e96a5c91b8d4ce765381e52"), "name" : "hotel4", "location" : [ 115.995593, 28.681632 ], "distance" : 388.62555058249967 } { "_id" : ObjectId("5e96a5c91b8d4ce765381e4f"), "name" : "hotel1", "location" : [ 115.993121, 28.676436 ], "distance" : 868.6740526419927 } |
比如：WX4ER区域内的用户搜索附近的餐厅数据，由于这区域内用户的GeoHash字符串都是WX4ER，故可以把WX4ER当作key，餐厅信息作为value进行缓存;而如果不使用GeoHash算法，区域内的用户请求餐厅数据，用户传来的经、纬度都是不同的，这样缓存不仅麻烦且数据量巨大。
2、利弊分析【本文地址】