空间搜索(圆范围)中Geohash编码方案和网格编码方案对比探讨

产品说明书 2018-04-20

文章版权由作者李晓晖和安科网共有,若转载请于明显处标明出处:http://www.cnblogs.com/naaoveGIS/

1.背景

多个项目中实现范围(圆)搜索的方案为:依赖库表中的X和Y字段构造一个矩形查询范围,再通过几何计算范围中的数据到指定坐标的距离是否在阈值半径中,最后返回阈值中的数据。
该方案有几个优点:

  • 无需对数据预处理,仅通过sql就可以实现,实现方式简单。
  • 数据库环境中,通过数字搜索比通过字符串搜索效率更高,占用的CPU更少。

但是,该方案在表数据量庞大的情况下,通过X和Y两个字段,并且有四个查询条件,对性能有一定损耗。
在之前我写过一篇关于Geohash编码研究的文章WebGIS中GeoHash编码的研究和扩展,这里提到了一种将X和Y以哈夫曼原理编码成一维字符串的方案。那么这里如果我们使用geohash编码方案来优化查询效率是否有用?

2.基于GeoHash编码的范围查询

2.1需要解决的点

空间搜索(圆范围)中Geohash编码方案和网格编码方案对比探讨空间搜索(圆范围)中Geohash编码方案和网格编码方案对比探讨
  • 基于GeoHash编码原理,将编码对象从经纬度数据扩展到也支持平面坐标数据
  • 由于编码值对应的是一个范围,如果查询坐标落入在范围的角落,仅通过相同字符串匹配可能导致查询结果不全,这里需要重构查询范围
  • 根据查询的容差范围,可以计算出该范围所对应的geohash字符串位数

2.2解决思路

  • 针对平面坐标:将编码范围改变成该地图平面坐标真实范围,基于哈夫曼编码规则进行计算,最后使用base32编码成字符串。
  • 针对查询范围:以查询点为中心通过查询范围构造出查询范围矩形,利用目前查询范围所对应的hash编码长度所对应的精度,利用该精度将矩形进行切割,然后对格网分别编码。
  • geohash长度所对应的真实精度:基于编码规律,经度的bit长度可以为奇偶,但是纬度的bit长度必须是偶数,反算出经度和纬度的bit长度。然后根据经纬对范围,结合各方向的二分法次数(bit长度),即可算出经纬度此时的精度。

2.3方案实现

这里重点给出查询搜索代码,即通过hash长度对应的精度、查询范围参数,进行网格切分和编码。

/***
      * 通过传入指定范围、指定坐标、查询范围和geohash长度,返回查询范围中对应的所有geohash编码
      * @param minX
      * @param minY
      * @param maxX
      * @param maxY
      * @param X
      * @param Y
      * @param geohashLength geohash字符串编码长度
      * @param searchRange  查询范围,如果是平面坐标系100M则传入100,经纬度坐标系0.0001度则传入0.0001
      * @return
      */
     public static List<String> GeoHashSearch(double minX, double minY, double maxX, double maxY, 
    		 double X, double Y, int geohashLength,double searchRange){
         List<Integer> latLngLength = SetHashLength(geohashLength);
         double boundMinX = X - searchRange;
         double boundMaxX = X + searchRange;
         double boundMinY = Y - searchRange;
         double boundMaxY = Y + searchRange;
         List<Double> range = GetGoeHashRange(minX, minY, maxX, maxY, latLngLength.get(0), latLngLength.get(1));
         List<String>  searchResult= new ArrayList<String>();
         double xrange = range.get(0);
         double yrange = range.get(1);
         double value = 0.5;
         for (int i = 0; boundMinX + (i - value) * xrange <= boundMaxX; i++) {
             for (int j = 0; boundMinY + (j - value) * yrange <= boundMaxY; j++) {
                 String geohashCode = Encode(minX, minY, maxX, maxY,
                     boundMinX + i* xrange, boundMinY + j * yrange, geohashLength);
                 if (!searchResult.contains(geohashCode)) {
                     searchResult.add(geohashCode);
                 }                   
             }
         }
         return searchResult;
     }

2.4优缺点探讨

2.4.1优点

  • geohash编码通过不断的二分,如果有必要可以直接将精度编码至厘米或毫米级别,并且对应的编码长度不会特别长。比如,当经纬度坐标系下,即使坐标范围用全球范围(-90到90,-180到180),其厘米级的编码长度也不长。以下是此时的长度精确表:空间搜索(圆范围)中Geohash编码方案和网格编码方案对比探讨空间搜索(圆范围)中Geohash编码方案和网格编码方案对比探讨

2.4.2缺点

  • 高精度编码没法使用:虽然精度到厘米编码长度也不长,但是当查询范围是1Km例如,此时编码长度只需要到2位,而查询却必须使用like去匹配,此时查询效率反而太低。
  • 不同编码长度间跨越的精度太大:比如,查询1000M和查询2000M范围所对应的编码长度可能都是2,这样导致查询的结果的个数(格网切分)可能特别多。那么此时即使对编码字段做了索引,也不一定会产生实际效果(如果使用In则索引无效,而使用OR,查询条件又过多影响sql解析等)。
  • 编码为字符串影响查询效率:geohash编码的结果是基于Base32规范进行结果编码,为字符串,影响数据库查询效率。

2.5 换一种思路

geohash编码由于随着地图范围不同各编码长度精度无法确定、编码只能以字符串存储等问题,在我们的业务场景上无法使用。那么,如果我们让编码精度确定、编码可以用数字替代,是否就可以达到业务场景的需要呢?

3.基于格网编码的范围查询

3.1算法介绍

格网划分算是GIS算法中的万金油。以前博客中写过的空间索引、地理插值、影像金字塔、矢量切片等等均可以基于格网的思路去探索。这里,同样可以利用格网算法来进行编码。

3.1.1基本算法

  • 将地图的左上角坐标当做原点,设定好格网的长度(X方向和Y方向)
  • 传入坐标,计算坐标分别在X方向和Y方向离坐标原点的格网个数,分别为xNum、yNum
/***
	 * 通过传入地图起始点,待编码坐标,编码的X和Y方向精确度,获取网格编码字符串
	 * @param minX 地图起始点X坐标
	 * @param minY 地图起始点Y坐标
	 * @param X
	 * @param Y
	 * @param gridXSize X方向精确度。平面坐标为M,经纬度坐标为度
	 * @param gridYSize Y方向精确度。平面坐标为M,经纬度坐标为度
	 * @return
	 */
	public static long GetGridCode(double minX, double minY, double X, double Y, double gridXSize,double gridYSize){
        if (X < minX || Y < minY){
            return -1;
        }
        int xNum = (int)Math.ceil(Math.abs(X - minX) / gridXSize);
        int yNum = (int)Math.ceil(Math.abs(Y - minY) / gridYSize);
        return CreateLongCode(xNum,yNum);
    }

3.1.2编码优化

如果我们需要将编码转换成数字编码,那么我们同样需要设定一种规则。这里,我规定xNum和yNum都必须是八个字符串长度,不足的在前缀以0补充,最后再合并转换成整数。(注意,这里我设计以0作为前缀而不是后缀补充,是为了及时转换成数字后,以后可以通过数字将编码反转换为空间范围)

/***
	  * 以8位数和8位数分别将col和row填充组合成一个整数
	  */
	 private static long  CreateLongCode(int x,int y){
		 String sx=String.valueOf(y);
		 String sy=String.valueOf(y);
		 for(int i=sx.length();i<XLen;i++){
			 sx="0"+sx;
		 }
		 for(int j=sy.length();j<YLen;j++){
			 sy="0"+sy;
		 }
		 String scode=sx+sy;
		 long code=Long.parseLong(scode);
		 return code;
	 }
	 
	 /***
	 * 获取网格编码所对应的真实地理范围
	 * @param minX
	 * @param minY
	 * @param value 编码值
	 * @param gridXSize X方向精确度。平面坐标为M,经纬度坐标为度
	 * @param gridYSize Y方向精确度。平面坐标为M,经纬度坐标为度
	 * @return
	 */
	 public static List<Double> Decode(double minX, double minY, long value, double gridXSize,double gridYSize){
		 String svalue=String.valueOf(value);
		 String sx=svalue.substring(0,svalue.length()-YLen-1);
		 String sy=svalue.substring(svalue.length()-YLen);
         int xnum=Integer.parseInt(sx);
         int ynum=Integer.parseInt(sy);
         double boundMinX = minX + (xnum - 1) * gridXSize;
         double boundMaxX = boundMinX + gridXSize;
         double boundMinY = minY + (ynum - 1) * gridYSize;
         double boundMaxY = boundMinY + gridYSize;
         List<Double> bound = new ArrayList<Double>();
         bound.add(boundMinX);
         bound.add(boundMinY);
         bound.add(boundMaxX);
         bound.add(boundMaxY);
         return bound;
     }

3.2范围查询

同样,这里也需要考虑与geohash查询时一样的情况:

  • 查询XY落在网格的边角上
  • 查询范围阈值大于网格大小 解决思路与之前相同:
/***
	 * 通过传入地图起始点、网格X和Y方向精确度、查询范围和查询点,返回对应查询范围内所有网格编码
	 * @param minX
	 * @param minY
	 * @param X
	 * @param Y
	 * @param gridXSize X方向精确度。平面坐标为M,经纬度坐标为度
	 * @param gridYSize Y方向精确度。平面坐标为M,经纬度坐标为度
	 * @param range 查询范围,平面坐标为M,经纬度坐标为度 
	 * @return
	 */
	public static List<Long> GridCodeSearch(double minX, double minY, double X, double Y, double gridXSize, double gridYSize,double range){
        if (X < minX || Y < minY){
            return null;
        }
        double boundMinX = X - range;
        double boundMinY = Y - range;
        double boundMaxX = X + range;
        double boundMaxY = Y + range;
        double value=0.5;
        List<Long> searchResult = new ArrayList<Long>();
        for (int i = 0; boundMinX + (i - value) * gridXSize <= boundMaxX; i++){
            for (int j = 0; boundMinY + (j - value) * gridYSize <= boundMaxY; j++){
                long gridCode = GetGridCode(minX, minY, boundMinX + i * gridXSize, boundMinY + j * gridYSize, gridXSize, gridYSize);
                if (!searchResult.contains(gridCode)){
                    searchResult.add(gridCode);
                }
            }
        }
        return searchResult;
    }

3.3格网划分的一点建议

  • 格网不宜划分太小,建议划分的比查询范围大,这样保证范围过滤查询时返回的匹配格网编码少。比如,格网大小500M,查询范围100M,查询时,在多数情况下将只返回一个编码。当然,此时基于该编码去数据库中查询,将得到更多的数据点,于是需要我们做精确的范围计算量变大。但是:将数据库压力适当转移到服务器计算是一种更划算的策略。当然,格网划的太大,也会适得其反,建议通用查询范围一两倍即可。

4.后续方案描述

  • 坐标存入时,将坐标基于格网编码并同步存入到指定字段,对该字段建立索引(此时字段为长度大于16的长整型)。
  • 查询时,调用编码查询接口,获取到该XY以及查询范围下,对应的网格编码。在数据库中利用这些编码做匹配查询(粗过滤)。对返回的结果进一步做精确范围匹配(精过滤可做可不做,视需求规格而定)。

-----欢迎转载,但保留版权,请于明显处标明出处:http://www.cnblogs.com/naaoveGIS/

如果您觉得本文确实帮助了您,可以微信扫一扫,进行小额的打赏和鼓励,谢谢 ^_^

空间搜索(圆范围)中Geohash编码方案和网格编码方案对比探讨

相关推荐