附近的人功能实现及原理

2020-08-06 本文已影响0人 TiaNa_na

如何查找当前点（118.818747°E，32.074497°N）附近500米的人？

这一类功能很常见（如微信附近的人、共享单车附近的车辆、美团附近的商家），那在java中是如何实现的呢？

1 实现方式

目前普遍的实现方式有三种，下面将依次展开讨论：

Mysql+外接正方形
Mysql+geohash
Redis+geohash

2 Mysql+外接正方形

2.1 实现思路

查找附近500米的人，就是以当前坐标点为圆心，以500米为半径画圆，找出圆内的人。
理论上可以直接计算数据库所有点与圆心的距离，与500米比较。但计算地球上两点距离公式复杂，一旦数据库数据过多，计算起来就更麻烦了。
我们可以通过外接正方形的方式来解决这个问题。这样一来，计算量骤减。[注：设定下图圆心在北半球，东半球]

外接正方形
于是：实现附近的人功能实现分为：
① 计算外切正方形最大最小经纬度
② 查询在正方形范围内的数据
③ 过滤得到圆周内的点，即用正方形范围内的点-黄色区域的点（距离超过给定范围500米）

2.2 数据库准备

数据库表结构

2.3 代码实现

获取外切正方形最大最小经纬度有两种方法，可以自己实现，也可用开源库实现。
①自己实现getGpsRange方法
此方法用到了半矢量公式，以下计算推导过程可参考https://www.jianshu.com/p/ed6ea376911e

/**
     * 获取附近x米的人
     *
     * @param distance 距离范围 单位km
     * @param userLng  当前经度
     * @param userLat  当前纬度
     * @return
     */
public List<User> nearBySearch1(double distance, double userLng, double userLat) {
        //1 获取外切正方形最大最小经纬度
        double[] point = getGpsRange(userLng, userLat, distance);
        //2 获取位置在正方形内的所有用户
        // 查询数据库操作，这里用mybatis plus实现
        List<User> users = list(Wrappers.<User>lambdaQuery().ge(User::getUserLongitude, point[0]).lt(User::getUserLongitude, point[1]).ge(User::getUserLatitude, point[2]).lt(User::getUserLatitude, point[3]));
        //3 过滤掉超过指定距离的用户
        users = users.stream().filter(a -> getDistance(a.getUserLongitude(), a.getUserLatitude(), userLng, userLat) <= distance)
                .collect(Collectors.toList());
        return users;
    }

/**
     * 查询出某个范围内的最大经纬度和最小经纬度
     * 自己计算
     *
     * @param longitude 当前位置经度
     * @param latitude  当前位置纬度
     * @param rangeDis  距离范围，单位km
     * @return
     */
    public static double[] getGpsRange(double longitude, double latitude, double rangeDis) {
        //半矢量公式，与圆心在同纬度上，且在圆周上的点到圆点的经度差
        double dlng = 2 * Math.asin(Math.sin(rangeDis / (2 * EARTH_RADIUS)) / Math.cos(latitude * Math.PI / 180));
        //弧度转为角度
        dlng = dlng * 180 / Math.PI;

        //半矢量公式，与圆心在同经度上，且在圆周上的点到圆点的纬度差
        //弧度转为角度
        double dlat = rangeDis / EARTH_RADIUS;
        dlat = dlat * 180 / Math.PI;

        double minlng = longitude - dlng;
        double maxlng = longitude + dlng;
        double minlat = latitude - dlat;
        double maxlat = latitude + dlat;
        return new double[]{minlng, maxlng, minlat, maxlat};
    }

/**
     * 根据地球上任意两点的经纬度计算两点间的距离（半矢量公式）,返回距离单位：km
     *
     * @param longitude1 坐标1 经度
     * @param latitude1  坐标1 纬度
     * @param longitude2 坐标2 经度
     * @param latitude2  坐标2 纬度
     * @return 返回km
     */
    public static double getDistance(double longitude1, double latitude1, double longitude2, double latitude2) {
        double radLat1 = Math.toDegrees(latitude1);
        double radLat2 = Math.toDegrees(latitude2);
        double a = radLat1 - radLat2;
        double b = Math.toDegrees(longitude1) - Math.toDegrees(longitude2);
        double distance = 2 * Math.asin(Math.sqrt(Math.pow(Math.sin(a / 2), 2) +
                Math.cos(radLat1) * Math.cos(radLat2) * Math.pow(Math.sin(b / 2), 2)));
        distance = distance * EARTH_RADIUS;
        distance = Math.round(distance * 10000) / 10000.0;
        return distance;
    }

②也可用开运库计算外接正方形坐标范围

     <dependency>
            <groupId>com.spatial4j</groupId>
            <artifactId>spatial4j</artifactId>
            <version>0.5</version>
        </dependency>

private SpatialContext spatialContext = SpatialContext.GEO;    

/**
     * 获取附近x米的人
     *
     * @param distance 距离范围 单位km
     * @param userLng  当前经度
     * @param userLat  当前纬度
     * @return
     */
public List<User> nearBySearch(double distance, double userLng, double userLat) {
        //1 获取外切正方形最大最小经纬度
       Rectangle rectangle = getRectangle(distance, userLng, userLat);
        //2.获取位置在正方形内的所有用户
        // 查询数据库操作，这里用mybatis plus实现
        List<User> users = list(Wrappers.<User>lambdaQuery().ge(User::getUserLongitude, rectangle.getMinX()).lt(User::getUserLongitude, rectangle.getMaxX()).ge(User::getUserLatitude, rectangle.getMinY()).lt(User::getUserLatitude, rectangle.getMaxY()));
        //3.剔除半径超过指定距离的多余用户
        users = users.stream().filter(a -> getDistance(a.getUserLongitude(), a.getUserLatitude(), userLng, userLat) <= distance)
                .collect(Collectors.toList());
        return users;
    }

    /**
     * 利用开源库计算外接正方形坐标
     *
     * @param distance
     * @param userLng  当前经度
     * @param userLat  当前纬度
     * @return
     */
    private Rectangle getRectangle(double distance, double userLng, double userLat) {
        return spatialContext.getDistCalc()
                .calcBoxByDistFromPt(spatialContext.makePoint(userLng, userLat),
                        distance * DistanceUtils.KM_TO_DEG, spatialContext, null);
    }

/***
     * 球面中，两点间的距离（第三方库方法）
     *
     * @param longitude 经度1
     * @param latitude  纬度1
     * @param userLng   经度2
     * @param userLat   纬度2
     * @return 返回距离，单位km
     */
    public double getDistance(Double longitude, Double latitude, double userLng, double userLat) {
        return spatialContext.calcDistance(spatialContext.makePoint(userLng, userLat),
                spatialContext.makePoint(longitude, latitude)) * DistanceUtils.DEG_TO_KM;
    }

3 Mysql+geohash

第二种实现方式引入了geohash。

GeoHash是一种地址编码方法。他能够把二维的空间经纬度数据编码成一个字符串。

3.1 geohash算法

3.1.1 geohash算法思想

将地球球面沿着180°经线分开，平铺到平面上。

0°经线和0°纬线将此平面划分为四部分。设定西经为负，南纬为负，地球上的经度范围就是[-180°,180°]，纬度范围就是[-90°,90°]。

如果纬度范围[-90°, 0°)用二进制0代表，（0°, 90°]用二进制1代表，经度范围[-180°, 0°)用二进制0代表，（0°, 180°]用二进制1代表，那么划分出的四部分用二进制表示为：

如果再对此递归对半划分呢？

geohash算法就是基于这种思想，划分的次数越多，区域越多，区域面积越小。

3.1.2 geohash算法编码经纬度

geohash算法将经纬度编码分为三步：
①将经纬度变成二进制

以点（118.818747，32.074497）为例。

纬度的范围是（-90，90），以其中间值0将此范围划分为两个区间（-90,0）和(0,90)，若给定的纬度在左区间（-90,0），则为0；若给定的纬度在右区间(0,90)，则为1；纬度32.074497在右区间，因此为1。

再将（0,90）这个区间以中间值划分为左右区间，按照以上方法判定为1还是0。

依此方法，可得到纬度的二进制表示，如下表：

纬度范围	划分的左区间	划分的右区间	纬度32.074497的二进制表示
（-90，90）	（-90，0）	（0，90）	1
（0，90）	（0，45）	（45，90）	0
（0，45）	（0，22.5）	（22.5，45）	1
（22.5，45）	（22.5，33.75）	（33.75，45）	0
（22.5，33.75）	（22.5，28.125）	（28.125，33.75）	1
……	……	……	……

划分10次后，得到的纬度二进制表示为10101 10110

同样的方法，可得到划分9次后经度二进制表示为110101

②将经纬度合并

合并方法： 经度占偶数位，纬度占奇数位

经纬度合并结果为 11100 11001 11000 10110

③按照Base32进行编码

将②的结果用Base32编码得到字符串wtsq。也就是说点（118.818747，32.074497）可用wtsq表示。

GeoHash字符串越长，表示的位置越精确，字符串长度越长代表在距离上的误差越小。具体的不同精度的距离误差可参考下表：

不同精度的距离误差

GeoHash值表示的并不是一个点，而是一个矩形区域。

Geohash比直接用经纬度的高效很多，而且使用者可以发布地址编码，既能表明自己所在区域，又不至于暴露自己的精确坐标，有助于隐私保护。

距离越近的坐标，转换后的geohash字符串越相似,例如：

3.2 实现思路

以上详细介绍了geohash算法，那么如何利用Mysql+geohash实现附近的人功能呢？

添加新用户时计算该用户的geohash字符串，并存储到用户表中。
当要查询某个点附近指定距离的用户信息时，通过比对geohash误差表确定需要的geohash字符串精度。
计算获得当前坐标的geohash字符串，并查询与当前字符串前缀相同的数据。
如果geohash字符串的精度远大于给定的距离范围时，查询出的结果集中必然存在在范围之外的数据。
计算两点之间距离，对于超出距离的数据进行剔除。

3.3 数据库准备

数据库表结构

3.4 代码实现

       <dependency>
            <groupId>com.spatial4j</groupId>
            <artifactId>spatial4j</artifactId>
            <version>0.5</version>
        </dependency>

private SpatialContext spatialContext = SpatialContext.GEO;

 /**
     * 获取附近指定范围的人
     *
     * @param distance 距离范围 单位km
     * @param len      geoHash的精度
     * @param userLng  当前用户的经度
     * @param userLat  当前用户的纬度
     * @return
     */
 public List<User> nearBySearch2(double distance, int len, double userLng, double userLat) {
        //1.根据要求的范围，确定geoHash码的精度，获取到当前用户坐标的geoHash码
        String geoHashCode = GeohashUtils.encodeLatLon(userLat, userLng, len);
        //2.匹配指定精度的geoHash码  
        //查询数据库操作 mybatis plus实现
        List<User> users = list(Wrappers.<User>lambdaQuery().likeRight(User::getGeohash, geoHashCode));
        //3.过滤超出距离的
        users = users.stream()
                .filter(a -> getDistance1(a.getUserLongitude(), a.getUserLatitude(), userLng, userLat) <= distance)
                .collect(Collectors.toList());
        return users;
    }

 /***
     * 球面中，两点间的距离（第三方库方法）
     *
     * @param longitude 经度1
     * @param latitude  纬度1
     * @param userLng   经度2
     * @param userLat   纬度2
     * @return 返回距离，单位km
     */
    public double getDistance(Double longitude, Double latitude, double userLng, double userLat) {
        return spatialContext.calcDistance(spatialContext.makePoint(userLng, userLat),
                spatialContext.makePoint(longitude, latitude)) * DistanceUtils.DEG_TO_KM;
    }

     /**
     * 向数据库添加数据
     * 
     * @param user 用户对象 
     * @return 
     */
public boolean save(User user) {
        //默认精度12位
        String geoHashCode = GeohashUtils.encodeLatLon(user.getUserLatitude(), user.getUserLongitude());
     //插入数据库操作 mybatis plus实现
        super.save(user.setGeohash(geoHashCode));
    }

3.5 边界问题优化

geohash算法提高了效率，但在实际应用场景中存在一些问题。首先就是边界问题。

如图，如果当前在红点位置，区域内还有一个黄点。相邻区域内的绿点明显离红点更近。但因为黄点的编码和红点一样，最终找到的将是黄点。这就有问题了。

要解决这个问题，除了要找到当前区域内的点，还要要再查找周边8个区域内的点，看哪个离自己更近。

这里提供了求解当前区域周围8个区域的思路：Geohash求当前区域周围8个区域编码的一种思路

由此优化代码为：

        <dependency>
            <groupId>com.spatial4j</groupId>
            <artifactId>spatial4j</artifactId>
            <version>0.5</version>
        </dependency>

        <dependency>
            <groupId>ch.hsr</groupId>
            <artifactId>geohash</artifactId>
            <version>1.0.10</version>
        </dependency>

private SpatialContext spatialContext = SpatialContext.GEO;
    /**
     * 获取附近x米的人,geohash区域+8个周围区域
     *
     * @param distance 距离范围 单位km
     * @param len      geoHash的精度
     * @param userLng  当前经度
     * @param userLat  当前纬度
     * @return json
     */
 public List<User> nearBySearch4(double distance, int len, double userLng, double userLat) {

        //1 根据要求的范围，确定geoHash码的精度，获取到当前用户坐标的geoHash码
        GeoHash geoHash = GeoHash.withCharacterPrecision(userLat, userLng, len);
        //2 获取到用户周边8个方位的geoHash码
        GeoHash[] adjacent = geoHash.getAdjacent();
        //查询数据库操作 mybatis plus实现
        QueryWrapper<User> queryWrapper = new QueryWrapper<User>().likeRight("user_geohash", geoHash.toBase32());
        Stream.of(adjacent).forEach(a -> queryWrapper.or().likeRight("user_geohash", a.toBase32()));
        //匹配指定精度的geoHash码
        List<User> users = list(queryWrapper);
        //3 过滤超出距离的
        users = users.stream()
                .filter(a -> getDistance(a.getUserLongitude(), a.getUserLatitude(), userLng, userLat) <= distance)
                .collect(Collectors.toList());
        return users;
    }

/***
     * 球面中，两点间的距离（第三方库方法）
     *
     * @param longitude 经度1
     * @param latitude  纬度1
     * @param userLng   经度2
     * @param userLat   纬度2
     * @return 返回距离，单位km
     */
    public double getDistance(Double longitude, Double latitude, double userLng, double userLat) {
        return spatialContext.calcDistance(spatialContext.makePoint(userLng, userLat),
                spatialContext.makePoint(longitude, latitude)) * DistanceUtils.DEG_TO_KM;
    }

4 Redis+geohash

基于前两种方案，我们可以发现此功能属于读多写少的情况，如果使用redis来实现附近的人，想必效率会大大提高。

自Redis 3.2开始，Redis基于geohash和有序集合Zset提供了地理位置相关功能。

关于Redis提供的geohash操作命令介绍可移步：Redis 到底是怎么实现“附近的人”这个功能的呢？

4.1 实现思路

用GEOADD方法添加用户坐标信息到redis，redis会将经纬度参数值转换为52位的geohash码，
Redis以geohash码为score，将其他信息以Zset有序集合存入key中
通过调用GEORADIUS命令，获取指定坐标点某一范围内的数据
因geohash存在精度误差，剔除超过指定距离的数据

4.2 代码实现

    @Autowired
    private RedisTemplate redisTemplate;

    //GEO相关命令用到的KEY
    private final static String KEY = "user_info";
    /**
     * 根据当前位置获取附近指定范围内的用户
     *
     * @param distance 指定范围 单位km ，可根据{@link Metrics} 进行设置
     * @param userLng  用户经度
     * @param userLat  用户纬度
     * @return
     */
    public List<User> nearBySearch3(double distance, double userLng, double userLat) {
        List<User> users = new ArrayList<>();
        //GEORADIUS获取附近范围内的信息
        GeoResults<RedisGeoCommands.GeoLocation<Object>> reslut =
                redisTemplate.opsForGeo().radius(KEY,
                        new Circle(new Point(userLng, userLat), new Distance(distance, Metrics.KILOMETERS)),
                        RedisGeoCommands.GeoRadiusCommandArgs.newGeoRadiusArgs()
                                .includeDistance()
                                .includeCoordinates().sortAscending());
        //存入list
        List<GeoResult<RedisGeoCommands.GeoLocation<Object>>> content = reslut.getContent();
        //过滤掉超过距离的数据
        content.forEach(a -> users.add(
                new User().setDistance(a.getDistance().getValue())
                        .setUserLatitude(a.getContent().getPoint().getX())
                        .setUserLongitude(a.getContent().getPoint().getY())));
        return users;
    }

  /**
     * 用户信息存入Redis
     * 
     * @param user 用户对象 
     * @return 
     */
    public boolean save(User user) {
        Long flag = redisTemplate.opsForGeo().add(KEY, new RedisGeoCommands.GeoLocation<>(
                user.getUserAccount(),
                new Point(user.getUserLatitude(), user.getUserLatitude()))
        );
        return flag != null && flag > 0;
    }

5 总结

本文参考 Java中“附近的人”实现方案讨论及代码实现