文章版權(quán)由作者李曉暉和博客園共有，若轉(zhuǎn)載請(qǐng)于明顯處標(biāo)明出處：http://www.cnblogs.com/naaoveGIS/

1.背景

多個(gè)項(xiàng)目中實(shí)現(xiàn)范圍（圓）搜索的方案為：依賴庫表中的X和Y字段構(gòu)造一個(gè)矩形查詢范圍，再通過幾何計(jì)算范圍中的數(shù)據(jù)到指定坐標(biāo)的距離是否在閾值半徑中，最后返回閾值中的數(shù)據(jù)。
該方案有幾個(gè)優(yōu)點(diǎn)：

• 無需對(duì)數(shù)據(jù)預(yù)處理，僅通過sql就可以實(shí)現(xiàn)，實(shí)現(xiàn)方式簡單。
• 數(shù)據(jù)庫環(huán)境中，通過數(shù)字搜索比通過字符串搜索效率更高，占用的CPU更少。

但是，該方案在表數(shù)據(jù)量龐大的情況下，通過X和Y兩個(gè)字段，并且有四個(gè)查詢條件，對(duì)性能有一定損耗。
在之前我寫過一篇關(guān)于Geohash編碼研究的文章WebGIS中GeoHash編碼的研究和擴(kuò)展,這里提到了一種將X和Y以哈夫曼原理編碼成一維字符串的方案。那么這里如果我們使用geohash編碼方案來優(yōu)化查詢效率是否有用？

2.基于GeoHash編碼的范圍查詢

2.1需要解決的點(diǎn)

• 基于GeoHash編碼原理，將編碼對(duì)象從經(jīng)緯度數(shù)據(jù)擴(kuò)展到也支持平面坐標(biāo)數(shù)據(jù)
• 由于編碼值對(duì)應(yīng)的是一個(gè)范圍，如果查詢坐標(biāo)落入在范圍的角落，僅通過相同字符串匹配可能導(dǎo)致查詢結(jié)果不全，這里需要重構(gòu)查詢范圍
• 根據(jù)查詢的容差范圍，可以計(jì)算出該范圍所對(duì)應(yīng)的geohash字符串位數(shù)

2.2解決思路

• 針對(duì)平面坐標(biāo)：將編碼范圍改變成該地圖平面坐標(biāo)真實(shí)范圍，基于哈夫曼編碼規(guī)則進(jìn)行計(jì)算，最后使用base32編碼成字符串。
• 針對(duì)查詢范圍：以查詢點(diǎn)為中心通過查詢范圍構(gòu)造出查詢范圍矩形，利用目前查詢范圍所對(duì)應(yīng)的hash編碼長度所對(duì)應(yīng)的精度，利用該精度將矩形進(jìn)行切割，然后對(duì)格網(wǎng)分別編碼。
• geohash長度所對(duì)應(yīng)的真實(shí)精度：基于編碼規(guī)律，經(jīng)度的bit長度可以為奇偶，但是緯度的bit長度必須是偶數(shù)，反算出經(jīng)度和緯度的bit長度。然后根據(jù)經(jīng)緯對(duì)范圍，結(jié)合各方向的二分法次數(shù)（bit長度），即可算出經(jīng)緯度此時(shí)的精度。

2.3方案實(shí)現(xiàn)

這里重點(diǎn)給出查詢搜索代碼，即通過hash長度對(duì)應(yīng)的精度、查詢范圍參數(shù)，進(jìn)行網(wǎng)格切分和編碼。

/***
      * 通過傳入指定范圍、指定坐標(biāo)、查詢范圍和geohash長度，返回查詢范圍中對(duì)應(yīng)的所有g(shù)eohash編碼
      * @param minX
      * @param minY
      * @param maxX
      * @param maxY
      * @param X
      * @param Y
      * @param geohashLength geohash字符串編碼長度
      * @param searchRange  查詢范圍，如果是平面坐標(biāo)系100M則傳入100,經(jīng)緯度坐標(biāo)系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優(yōu)缺點(diǎn)探討

2.4.1優(yōu)點(diǎn)

• geohash編碼通過不斷的二分，如果有必要可以直接將精度編碼至厘米或毫米級(jí)別，并且對(duì)應(yīng)的編碼長度不會(huì)特別長。比如，當(dāng)經(jīng)緯度坐標(biāo)系下，即使坐標(biāo)范圍用全球范圍（-90到90，-180到180），其厘米級(jí)的編碼長度也不長。以下是此時(shí)的長度精確表： 

2.4.2缺點(diǎn)

• 高精度編碼沒法使用：雖然精度到厘米編碼長度也不長，但是當(dāng)查詢范圍是1Km例如，此時(shí)編碼長度只需要到2位，而查詢卻必須使用like去匹配，此時(shí)查詢效率反而太低。
• 不同編碼長度間跨越的精度太大：比如，查詢1000M和查詢2000M范圍所對(duì)應(yīng)的編碼長度可能都是2，這樣導(dǎo)致查詢的結(jié)果的個(gè)數(shù)（格網(wǎng)切分）可能特別多。那么此時(shí)即使對(duì)編碼字段做了索引，也不一定會(huì)產(chǎn)生實(shí)際效果（如果使用In則索引無效,而使用OR，查詢條件又過多影響sql解析等)。
• 編碼為字符串影響查詢效率:geohash編碼的結(jié)果是基于Base32規(guī)范進(jìn)行結(jié)果編碼，為字符串，影響數(shù)據(jù)庫查詢效率。

2.5 換一種思路

geohash編碼由于隨著地圖范圍不同各編碼長度精度無法確定、編碼只能以字符串存儲(chǔ)等問題，在我們的業(yè)務(wù)場景上無法使用。那么，如果我們讓編碼精度確定、編碼可以用數(shù)字替代，是否就可以達(dá)到業(yè)務(wù)場景的需要呢？

3.基于格網(wǎng)編碼的范圍查詢

3.1算法介紹

格網(wǎng)劃分算是GIS算法中的萬金油。以前博客中寫過的空間索引、地理插值、影像金字塔、矢量切片等等均可以基于格網(wǎng)的思路去探索。這里，同樣可以利用格網(wǎng)算法來進(jìn)行編碼。

3.1.1基本算法

• 將地圖的左上角坐標(biāo)當(dāng)做原點(diǎn)，設(shè)定好格網(wǎng)的長度（X方向和Y方向）
• 傳入坐標(biāo)，計(jì)算坐標(biāo)分別在X方向和Y方向離坐標(biāo)原點(diǎn)的格網(wǎng)個(gè)數(shù)，分別為xNum、yNum

/***
 * 通過傳入地圖起始點(diǎn)，待編碼坐標(biāo)，編碼的X和Y方向精確度，獲取網(wǎng)格編碼字符串
 * @param minX 地圖起始點(diǎn)X坐標(biāo)
 * @param minY 地圖起始點(diǎn)Y坐標(biāo)
 * @param X
 * @param Y
 * @param gridXSize X方向精確度。平面坐標(biāo)為M，經(jīng)緯度坐標(biāo)為度
 * @param gridYSize Y方向精確度。平面坐標(biāo)為M，經(jīng)緯度坐標(biāo)為度
 * @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編碼優(yōu)化

如果我們需要將編碼轉(zhuǎn)換成數(shù)字編碼，那么我們同樣需要設(shè)定一種規(guī)則。這里，我規(guī)定xNum和yNum都必須是八個(gè)字符串長度，不足的在前綴以0補(bǔ)充，最后再合并轉(zhuǎn)換成整數(shù)。（注意，這里我設(shè)計(jì)以0作為前綴而不是后綴補(bǔ)充，是為了及時(shí)轉(zhuǎn)換成數(shù)字后，以后可以通過數(shù)字將編碼反轉(zhuǎn)換為空間范圍）

/***
  * 以8位數(shù)和8位數(shù)分別將col和row填充組合成一個(gè)整數(shù)
  */
 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;
 }
 
 /***
 * 獲取網(wǎng)格編碼所對(duì)應(yīng)的真實(shí)地理范圍
 * @param minX
 * @param minY
 * @param value 編碼值
 * @param gridXSize X方向精確度。平面坐標(biāo)為M，經(jīng)緯度坐標(biāo)為度
 * @param gridYSize Y方向精確度。平面坐標(biāo)為M，經(jīng)緯度坐標(biāo)為度
 * @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查詢時(shí)一樣的情況:

• 查詢XY落在網(wǎng)格的邊角上
• 查詢范圍閾值大于網(wǎng)格大小 解決思路與之前相同：

/***
 * 通過傳入地圖起始點(diǎn)、網(wǎng)格X和Y方向精確度、查詢范圍和查詢點(diǎn)，返回對(duì)應(yīng)查詢范圍內(nèi)所有網(wǎng)格編碼
 * @param minX
 * @param minY
 * @param X
 * @param Y
 * @param gridXSize X方向精確度。平面坐標(biāo)為M，經(jīng)緯度坐標(biāo)為度
 * @param gridYSize Y方向精確度。平面坐標(biāo)為M，經(jīng)緯度坐標(biāo)為度
 * @param range 查詢范圍,平面坐標(biāo)為M，經(jīng)緯度坐標(biāo)為度 
 * @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格網(wǎng)劃分的一點(diǎn)建議

• 格網(wǎng)不宜劃分太小，建議劃分的比查詢范圍大，這樣保證范圍過濾查詢時(shí)返回的匹配格網(wǎng)編碼少。比如，格網(wǎng)大小500M，查詢范圍100M，查詢時(shí)，在多數(shù)情況下將只返回一個(gè)編碼。當(dāng)然，此時(shí)基于該編碼去數(shù)據(jù)庫中查詢，將得到更多的數(shù)據(jù)點(diǎn)，于是需要我們做精確的范圍計(jì)算量變大。但是：將數(shù)據(jù)庫壓力適當(dāng)轉(zhuǎn)移到服務(wù)器計(jì)算是一種更劃算的策略。當(dāng)然，格網(wǎng)劃的太大，也會(huì)適得其反，建議通用查詢范圍一兩倍即可。

4.后續(xù)方案描述

• 坐標(biāo)存入時(shí)，將坐標(biāo)基于格網(wǎng)編碼并同步存入到指定字段，對(duì)該字段建立索引（此時(shí)字段為長度大于16的長整型)。
• 查詢時(shí)，調(diào)用編碼查詢接口，獲取到該XY以及查詢范圍下，對(duì)應(yīng)的網(wǎng)格編碼。在數(shù)據(jù)庫中利用這些編碼做匹配查詢（粗過濾)。對(duì)返回的結(jié)果進(jìn)一步做精確范圍匹配(精過濾可做可不做，視需求規(guī)格而定)。

　　　　　　　　　　　　　　　　　　　　　　    -----歡迎轉(zhuǎn)載，但保留版權(quán)，請(qǐng)于明顯處標(biāo)明出處：http://www.cnblogs.com/naaoveGIS/

                                                                      　　　　  如果您覺得本文確實(shí)幫助了您，可以微信掃一掃，進(jìn)行小額的打賞和鼓勵(lì)，謝謝 ^_^