美文网首页JavaJAVA架构
附近的人功能实现及原理

附近的人功能实现及原理

作者: TiaNa_na | 来源:发表于2020-08-06 10:27 被阅读0次

    如何查找当前点(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 代码实现

    /**
         * 获取附近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表示。

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


      不同精度的距离误差
    2. GeoHash值表示的并不是一个点,而是一个矩形区域
    3. Geohash比直接用经纬度的高效很多,而且使用者可以发布地址编码,既能表明自己所在区域,又不至于暴露自己的精确坐标,有助于隐私保护。
    4. 距离越近的坐标,转换后的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中“附近的人”实现方案讨论及代码实现

    相关文章

      网友评论

        本文标题:附近的人功能实现及原理

        本文链接:https://www.haomeiwen.com/subject/gzticktx.html