APP中 “附近的人” 原理和4种算法实现方式

引言

昨天一位粉丝和我讨论了一道面试题,个人觉得比较有意义,这里整理了一下分享给大家,愿小伙伴们面试路上少踩坑。面试题目比较简单:“让你实现一个附近的人功能,你有什么方案?”,这道题其实主要还是考察大家对于技术的广度,本文介绍几种方案,给大家一点思路,避免在面试过程中语塞而影响面试结果,如有不严谨之处,还望亲人们温柔指正!

“附近的人” 功能生活中是比较常用的,像外卖app附近的餐厅,共享单车app里附近的车辆。既然常用面试被问的概率就很大,所以下边依次来分析基于mysql数据库、Redis、 MongoDB实现的 “附近的人” 功能。

1

科普:世界上标识一个位置,通用的做法就使用经、纬度。经度的范围在 (-180, 180],纬度的范围 在(-90, 90],纬度正负以赤道为界,北正南负,经度正负以本初子午线 (英国格林尼治天文台) 为界,东正西负。比如:望京摩托罗拉大厦的经、纬度(116.49141,40.01229)全是正数,就是因为我国位于东北半球。

一、“附近的人”原理

“附近的人” 也就是常说的 LBS (Location Based Services,基于位置服务),它围绕用户当前地理位置数据而展开的服务,为用户提供精准的增值服务。

“附近的人” 核心思想如下:

1.以 “我” 为中心,搜索附近的用户

2.以 “我” 当前的地理位置为准,计算出别人和 “我” 之间的距离

3.按 “我” 与别人距离的远近排序,筛选出离我最近的用户或者商店等

2

二、什么是GeoHash算法?

在说 “附近的人” 功能的具体实现之前,先来认识一下GeoHash 算法,因为后边会一直和它打交道。定位一个位置最好的办法就是用经、纬度标识,但经、纬度它是二维的,在进行位置计算的时候还是很麻烦,如果能通过某种方法将二维的经、纬度数据转换成一维的数据,那么比较起来就要容易的多,因此GeoHash算法应运而生。

GeoHash算法将二维的经、纬度转换成一个字符串,例如:下图中9个GeoHash字符串代表了9个区域,每一个字符串代表了一矩形区域。而这个矩形区域内其他的点(经、纬度)都用同一个GeoHash字符串表示。

3

比如:WX4ER区域内的用户搜索附近的餐厅数据,由于这区域内用户的GeoHash字符串都是WX4ER,故可以把WX4ER当作key,餐厅信息作为value进行缓存;而如果不使用GeoHash算法,区域内的用户请求餐厅数据,用户传来的经、纬度都是不同的,这样缓存不仅麻烦且数据量巨大。

GeoHash字符串越长,表示的位置越精确,字符串长度越长代表在距离上的误差越小。下图geohash码精度表:

4

而且字符串越相似表示距离越相近,字符串前缀匹配越多的距离越近。比如:下边的经、纬度就代表了三家距离相近的餐厅。

5

让大家简单了解什么是GeoHash算法,方便后边内容展开,GeoHash算法内容比较高深,感兴趣的小伙伴自行深耕一下,这里不占用过多篇幅(其实是我懂得太肤浅,哭唧唧~)。

三、基于Mysql

此种方式是纯基于mysql实现的,未使用GeoHash算法。

1、设计思路

以用户为中心,假设给定一个500米的距离作为半径画一个圆,这个圆型区域内的所有用户就是符合用户要求的 “附近的人”。但有一个问题是圆形有弧度啊,直接搜索圆形区域难度太大,根本无法用经、纬度直接搜索。

但如果在圆形外套上一个正方形,通过获取用户经、纬度的最大最小值(经、纬度 + 距离),再根据最大最小值作为筛选条件,就很容易将正方形内的用户信息搜索出来。

那么问题又来了,多出来一些面积肿么办?

我们来分析一下,多出来的这部分区域内的用户,到圆点的距离一定比圆的半径要大,那么我们就计算用户中心点与正方形内所有用户的距离,筛选出所有距离小于等于半径的用户,圆形区域内的所用户即符合要求的“附近的人”。

6

2、利弊分析

纯基于 mysql 实现 “附近的人”,优点显而易见就是简单,只要建一张表存下用户的经、纬度信息即可。缺点也很明显,需要大量的计算两个点之间的距离,非常影响性能。

3、实现

创建一个简单的表用来存放用户的经、纬度属性。

8

计算两个点之间的距离,用了一个三方的类库,毕竟自己造的轮子不是特别圆,还有可能是方的,啊哈哈哈~

9

获取到外接正方形后,以正方形的最大最小经、纬度值搜索正方形区域内的用户,再剔除超过指定距离的用户,就是最终的附近的人。

 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<User> 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) <= distance)
21            .collect(Collectors.toList());
22        return JSON.toJSONString(users);
23    }
24
25    private Rectangle getRectangle(double distance, double userLng, double userLat) {
26        return spatialContext.getDistCalc()
27            .calcBoxByDistFromPt(spatialContext.makePoint(userLng, userLat), 
28                                 distance * DistanceUtils.KM_TO_DEG, spatialContext, null);
29    }

由于用户间距离的排序是在业务代码中实现的,可以看到SQL语句也非常的简单。

2        SELECT * FROM user
3        WHERE 1=1
4        and (longitude BETWEEN ${minlng} AND ${maxlng})
5        and (latitude BETWEEN ${minlat} AND ${maxlat})
6    </select>
7

四、Mysql + GeoHash

1、设计思路

这种方式的设计思路更简单,在存用户位置信息时,根据用户经、纬度属性计算出相应的geohash字符串。注意:在计算geohash字符串时,需要指定geohash字符串的精度,也就是geohash字符串的长度,参考上边的geohash精度表。

当需要获取附近的人,只需用当前用户geohash字符串,数据库通过WHERE geohash Like 'geocode%' 来查询geohash字符串相似的用户,然后计算当前用户与搜索出的用户距离,筛选出所有距离小于等于指定距离(附近500米)的,即附近的人。

2、利弊分析

利用GeoHash算法实现“附近的人”有一个问题,由于geohash算法将地图分为一个个矩形,对每个矩形进行编码,得到geohash字符串。可我当前的点与邻近的点很近,但恰好我们分别在两个区域,明明就在眼前的点偏偏搜不到,实实在在的灯下黑。

如何解决这一问题?

为了避免类似邻近两点在不同区域内,我们就需要同时获取当前点(WX4G0)所在区域附近 8个区域的geohash码,一并进行筛选比较。

7

3、实现

同样要设计一张表存用户的经、纬度信息,但区别是要多一个geo_code字段,存放geohash字符串,此字段通过用户经、纬度属性计算出。使用频繁的字段建议加上索引。

10

首先根据用户经、纬度信息,在指定精度后计算用户坐标的geoHash码,再获取到用户周边8个方位的geoHash码在数据库中搜索用户,最后过滤掉超出给定距离(500米内)的用户。

 2
 3    /***
 4     * 添加用户
 5     * @return
 6     */
 7    @PostMapping("/addUser")
 8    public boolean add(@RequestBody UserGeohash user) {
 9        //默认精度12位
10        String geoHashCode = GeohashUtils.encodeLatLon(user.getLatitude(),user.getLongitude());
11        return userGeohashService.save(user.setGeoCode(geoHashCode).setCreateTime(LocalDateTime.now()));
12    }
13
14
15/**
16     * 获取附近指定范围的人
17     *
18     * @param distance 距离范围(附近多远的用户) 单位km
19     * @param len      geoHash的精度(几位的字符串)
20     * @param userLng  当前用户的经度
21     * @param userLat  当前用户的纬度
22     * @return json
23     */
24    @GetMapping("/nearby")
25    public String nearBySearch(@RequestParam("distance") double distance,
26                               @RequestParam("len") int len,
27                               @RequestParam("userLng") double userLng,
28                               @RequestParam("userLat") double userLat) {
29
30
31        //1.根据要求的范围,确定geoHash码的精度,获取到当前用户坐标的geoHash码
32        GeoHash geoHash = GeoHash.withCharacterPrecision(userLat, userLng, len);
33        //2.获取到用户周边8个方位的geoHash码
34        GeoHash[] adjacent = geoHash.getAdjacent();
35
36        QueryWrapper<UserGeohash> queryWrapper = new QueryWrapper<UserGeohash>()
37            .likeRight("geo_code",geoHash.toBase32());
38        Stream.of(adjacent).forEach(a -> queryWrapper.or().likeRight("geo_code",a.toBase32()));
39
40        //3.匹配指定精度的geoHash码
41        List<UserGeohash> users = userGeohashService.list(queryWrapper);
42        //4.过滤超出距离的
43        users = users.stream()
44                .filter(a ->getDistance(a.getLongitude(),a.getLatitude(),userLng,userLat)<= distance)
45                .collect(Collectors.toList());
46        return JSON.toJSONString(users);
47    }
48
49
50    /***
51     * 球面中,两点间的距离
52     * @param longitude 经度1
53     * @param latitude  纬度1
54     * @param userLng   经度2
55     * @param userLat   纬度2
56     * @return 返回距离,单位km
57     */
58    private double getDistance(Double longitude, Double latitude, double userLng, double userLat) {
59        return spatialContext.calcDistance(spatialContext.makePoint(userLng, userLat),
60                spatialContext.makePoint(longitude, latitude)) * DistanceUtils.DEG_TO_KM;
61    }

五、Redis + GeoHash

Redis 3.2版本以后,基于geohash和数据结构Zset提供了地理位置相关功能。通过上边两种mysql的实现方式发现,附近的人功能是明显的读多写少场景,所以用redis性能更会有很大的提升。

1、设计思路

redis 实现附近的人功能主要通过Geo模块的六个命令。

GEOADD:将给定的位置对象(纬度、经度、名字)添加到指定的key;

GEOPOS:从key里面返回所有给定位置对象的位置(经度和纬度);

GEODIST:返回两个给定位置之间的距离;

GEOHASH:返回一个或多个位置对象的Geohash表示;

GEORADIUS:以给定的经纬度为中心,返回目标集合中与中心的距离不超过给定最大距离的所有位置对象;

GEORADIUSBYMEMBER:以给定的位置对象为中心,返回与其距离不超过给定最大距离的所有位置对象。

以GEOADD 命令和GEORADIUS 命令简单举例:

其中,key为集合名称,member为该经纬度所对应的对象。

GEOADD 添加多个商户“火锅店”位置信息:

GEORADIUS 根据给定的经纬度为中心,获取目标集合中与中心的距离不超过给定最大距离(500米内)的所有位置对象,也就是“附近的人”。

  • 范围单位:m | km | ft | mi --> 米 | 千米 | 英尺 | 英里。
  • 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<String, Object> 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<User> users = new ArrayList<>();
24        // 1.GEORADIUS获取附近范围内的信息
25        GeoResults<RedisGeoCommands.GeoLocation<Object>> 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<GeoResult<RedisGeoCommands.GeoLocation<Object>>> 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发表,未经许可,不得转载。

如有侵权,请联系nowjava@qq.com删除。

编辑于

关注时代Java

关注时代Java