1. 背景
多个项目中实现范围 (圆) 搜索的方案为: 依赖库表中的 X 和 Y 字段构造一个矩形查询范围, 再通过几何计算范围中的数据到指定坐标的距离是否在阈值半径中, 最后返回阈值中的数据.
该方案有几个优点:
无需对数据预处理, 仅通过 sql 就可以实现, 实现方式简单.
数据库环境中, 通过数字搜索比通过字符串搜索效率更高, 占用的 CPU 更少.
但是, 该方案在表数据量庞大的情况下, 通过 X 和 Y 两个字段, 并且有四个查询条件, 对性能有一定损耗.
在之前我写过一篇关于 Geohash 编码研究的文章 webGIS 中 GeoHash 编码的研究和扩展, 这里提到了一种将 X 和 Y 以哈夫曼原理编码成一维字符串的方案. 那么这里如果我们使用 geohash 编码方案来优化查询效率是否有用?
2. 基于 GeoHash 编码的范围查询
2.1 需要解决的点
基于 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), 其厘米级的编码长度也不长. 以下是此时的长度精确表:
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 以及查询范围下, 对应的网格编码. 在数据库中利用这些编码做匹配查询(粗过滤). 对返回的结果进一步做精确范围匹配(精过滤可做可不做, 视需求规格而定).
来源: https://www.cnblogs.com/naaoveGIS/p/8892464.html