基于GeoHash算法的四大经纬度计算方案

雨点打透心脏的1/2处 2021-11-09 20:31 260阅读 0赞

# 背景 #

前天下班前，有两个同事在讨论到关于一个接口的性能，是关于经纬度的计算，需求是：返回指定经纬度、20公里以内的、按距离排序的前100个站点。  
        因为之前关于距离的计算是使用公式计算的，然后大家关于性能的讨论是：如果一万个站点就要计算一万次，而且如果同时有一万个用户在访问，那么接口的性能就不行了。因为APP主要是由我来重新架构：由WebService转到SpringCloud架构，而且有些业务比较繁重的接口的Sql我是没有大改动的，主要还是将存储过程里面的SQL抽出来。所以说，之后关于性能方面的提升，我责无旁贷。

# 主题来了：GeoHash算法 #

对于经纬度的计算，最出名的该有GeoHash算法，至于算法的思想是怎么滴，大家可以看看这篇文章，写得非常的详细清晰了，必须读一遍就能理解算法的原理。[<<GeoHash核心原理分析>>][GeoHash]

# 准备数据： #

1、首先我们创建表，我们要注意一下，如果你的mysql是5.7以前的，那么是不支持使用st\_geohash函数的：

create table `user_gis`(
        `id` BIGINT unsigned NOT NULL AUTO_INCREMENT comment '主键',
        `name` varchar(30) not null comment '姓名',
        `lng` DOUBLE comment '经度',
        `lat` DOUBLE comment '纬度',
        `gis` geometry not null comment '空间位置信息',
        `geohash` varchar(50) GENERATED ALWAYS AS (st_geohash(`gis`,8)) VIRTUAL comment 'getHash',
        PRIMARY KEY (`id`),
        SPATIAL KEY `idx_gis` (`gis`),
        KEY `idx_geohash` (`geohash`)
    ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COMMENT='用户空间位置信息';

2、准备数据：我这里是非常的简单了，使用for循环来创建数据,一共十万条

for (int i = 0; i < 100000; i++) {
        // 随机获取经纬度
        Double lng = RandomUtils.nextDouble(103.9999,133.99999);
        Double lat = RandomUtils.nextDouble(21.9999,39.9999);
        StringBuilder sb = new StringBuilder();
        // 拼接point，为geometry类型字段准备
        sb.append("point(").append(lng).append(" ").append(lat).append(")");
        UserGis userGis = new UserGis();
        String name = "测试充电站"+i;
        userGis.setName(name);
        userGis.setLng(lng.toString());
        userGis.setLat(lat.toString());
        userGis.setGis(sb.toString());
        // 插入数据
        this.userGisMapper.insertUserGis(userGis);
    }

@Insert("insert into user_gis(name,lng,lat,gis)values(#{name},#{lng},#{lat},geomfromtext(#{gis}))")
    void insertUserGis(UserGis userGis);

# 下面我们看一下使用公式、Mysql-R树索引、Mysql-GeoHash和Redis-geohash结构怎么完成需求： #

指定经纬度：113.37660 23.0896  指定范围：20公里 指定个数：100  
**1、公式（是网上弄过来了，经过测试，计算的准确度还是阔以的）。**

SELECT 
        id,name,
        ROUND(6378.138 * 2 * ASIN(SQRT(POW(SIN( ( 23.0896 * PI( ) / 180 - lat * PI( ) / 180 ) / 2 ),2) + COS( 23.0896 * PI( ) / 180 ) * COS( lat * PI( ) / 180 ) * POW(SIN( ( 113.37660 * PI( ) / 180 - lng * PI( ) / 180 ) / 2 ),2))) * 1000) AS distance,
        ST_AsText(gis) gis
    FROM user_gis
    WHERE lng BETWEEN 113.37660-(0.009091*20) AND 113.37660+(0.009091*20)
    AND lat BETWEEN 23.0896-(0.009091*20) AND 23.0896+(0.009091*20)
    ORDER BY distance limit 100;

**下面的两个方式是利用Mysql提供的GIS特性，这里需要简单的介绍一下：**  
首先我们得先了解一下MySql的GIS特性，区别主要在5.7前后。  
5.7前：  
    只有MyISAM引擎支持空间数据；  
    只有MyISAM支持R树查询；  
    地理空间类型性能比较一般；  
    地理空间函数支持度有限；  
    不支持GeoHash以及GeoJson；

5.7后：  
    InnoDB引擎原生支持地理空间数据类型  
    InnoDB引擎新增R树索引支持地理空间查询  
    新增很多通用的GIS函数，例如我们需要的球面距离计算函数：ST\_Distance\_Sphere

**2、那么我们看一下使用Mysql-R树索引查询：**

SELECT 
        id,name,
        (ST_Distance (point (113.37660,23.0896),point(lng,lat) ) / 0.0111) AS distance, 
        ST_AsText(gis) gis
    FROM user_gis
    WHERE ST_Contains( ST_MakeEnvelope(
        Point((113.37660+(20/111)), (23.0896+(20/111))),
        Point((113.37660-(20/111)), (23.0896-(20/111)))
    ), gis )
    ORDER BY distance limit 100;

**3、接下来使用geohash**  
利用GeohashUtils根据经纬度和范围求出geohash，然后sql再模糊查询，值越是接近证明距离越近。  
GeohashUtils的Maven依赖是

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

计算geohash：首先是根据范围获取geocode，然户再调用GeohashUtils工具类获取geohash：

Integer geoCode = GeoCode.INSTANCE.getGeoCode(query.getRange());
    String geoHash = GeohashUtils.encodeLatLon(Double.parseDouble(query.getLat()), Double.parseDouble(query.getLng()),geoCode);

GeoCode是我根据网上'范围-geocode对应表'自己封装的一个类：

package com.hyf.lnglat.utils;
    
    import java.util.LinkedHashMap;
    import java.util.Map;
    import java.util.Set;
    
    /**
     * @author Howinfun
     * @desc
     * @date 2019/7/31
     */
    public class GeoCode {
        public static final GeoCode INSTANCE = new GeoCode();
        private static Map<Integer,double[]> geoHash;
        private GeoCode(){
            geoHash = new LinkedHashMap<>();
            geoHash.put(12,new double[]{0.000037,0.000019});
            geoHash.put(11,new double[]{0.000149,0.000149});
            geoHash.put(10,new double[]{0.0012,0.000595});
            geoHash.put(9,new double[]{0.0048,0.0048});
            geoHash.put(8,new double[]{0.0382,0.019});
            geoHash.put(7,new double[]{0.1529,0.1524});
            geoHash.put(6,new double[]{1.2,0.6094});
            geoHash.put(5,new double[]{4.9,4.9});
            geoHash.put(4,new double[]{39.1,19.5});
            geoHash.put(3,new double[]{156.5,156});
            geoHash.put(2,new double[]{1252.3,624.1});
            geoHash.put(1,new double[]{5009.4,4992.6});
        }
    
        /**
         * 获取GeoCode
         * @param range 范围，单位为km
         * @return
         */
        public Integer getGeoCode(Integer range){
            Integer geoCode = 1;
            Set<Integer> keys = geoHash.keySet();
            for (Integer key : keys) {
                double[] value = geoHash.get(key);
                if (value[1]> range && value[0] > range){
                    geoCode = key;
                    break;
                }
            }
    
            return geoCode;
        }
    }

得到geohash值后就可以进行模糊查询了：

SELECT 
        id,name,
        ST_Distance_Sphere(Point(113.37660,23.0896), gis) as distance, 
        ST_AsText(gis) gis,
            geohash
    FROM user_gis
    WHERE geohash like CONCAT('ws0','%')
    ORDER BY distance limit 100;

**4、利用Redis的geohash结构**

准备Redis数据：SpringBoot启动类实现CommandLineRunner接口，然后再run方法里面搞定：

// 先清除缓存，再添加缓存
    lettuceConnectionFactory.getConnection().flushDb();
    List<UserGis> userGisList = userGisMapper.getAll();
    for (UserGis userGis : userGisList) {
        redisTemplate.opsForGeo().add("USER_GIS",new Point(Double.parseDouble(userGis.getLng()),Double.parseDouble(userGis.getLat())),userGis.getId());
    }

利用Redis的geohash结构，然后使用georadius指令求出范围中的数据，然后再到mysql里查询  
        指令：georadius cityGeo lng lat 100 km WITHDIST WITHCOORD ASC COUNT 100

/**
             * 根据指定经纬度，返回半径不超过指定距离的元素
             * distance:指定距离
             * point:指定经纬度
             */
            Distance distance = new Distance(query.getRange(),Metrics.KILOMETERS);
            Point point = new Point(Double.parseDouble(query.getLng()),Double.parseDouble(query.getLat()));
            Circle circle = new Circle(point,distance);
            /**
             * includeDistance: 返回距离
             * includeCoordinates：返回坐标
             * sortAscending：升序
             * limit：只返回一百个
             */
            RedisGeoCommands.GeoRadiusCommandArgs args = RedisGeoCommands.GeoRadiusCommandArgs.newGeoRadiusArgs().includeDistance().includeCoordinates().sortAscending().limit(100);
            GeoResults<RedisGeoCommands.GeoLocation> geoResults = redisTemplate.opsForGeo().radius(USER_GIS,circle,args);
            List<Integer> ids = new ArrayList<>(100);
            for (GeoResult<RedisGeoCommands.GeoLocation> geoResult : geoResults) {
                ids.add((Integer)geoResult.getContent().getName());
            }
            query.setIds(ids);
            List<UserGis> userGisList = userGisMapper.getRangeByRedis(query);

<select id="getRangeByRedis" resultType="com.hyf.lnglat.entity.UserGis">
            SELECT
            id,
            name,
            ST_Distance_Sphere(Point(#{lng},#{lat}), gis) as distance,
            ST_AsText(gis) gis,
            geohash
            FROM user_gis
            WHERE id IN
            <foreach collection="ids" index="index" item="item"
                     open="(" separator="," close=")">
                #{item}
            </foreach>
            ORDER BY distance;
        </select>

最后就是性能测试了：经过测试，R树索引和GeoHash是性能最好的，然后公式的性能是最差的，果然，还是不能用公式来搞这个需求啊。。。

如果同学们对此感兴趣，可到GitHub上拉项目下来试试：[<<lnglat>>][lnglat]

[GeoHash]: https://www.cnblogs.com/gaopeng527/p/5066983.html
[lnglat]: https://github.com/Howinfun/lnglat.git