JAVA實(shí)現(xiàn)空間索引編碼——GeoHash的示例

更新時(shí)間：2016年10月25日 09:54:56 作者：xiaojimanman

本篇文章主要介紹了JAVA實(shí)現(xiàn)空間索引編碼——GeoHash的示例，如何從眾多的位置信息中查找到離自己最近的位置，有興趣的朋友可以了解一下

之前自己在做基于Lucene的內(nèi)容檢索過程中，了解到Lucene可以實(shí)現(xiàn)對(duì)文本信息，數(shù)值信息的內(nèi)容檢索，對(duì)于空間距離好像并為為源碼中實(shí)現(xiàn)；最近半年自己接觸到Solr，里面有一個(gè)空間距離檢索（經(jīng)緯度），最近對(duì)其中的實(shí)現(xiàn)做了下學(xué)習(xí)，了解到在實(shí)現(xiàn)空間距離檢索的有一個(gè)比較常用的技術(shù)——GeoHash，下面就介紹下GeoHash。

GeoHash特點(diǎn)

GeoHash用一個(gè)字符串表示經(jīng)度和緯度兩個(gè)坐標(biāo)，比如我現(xiàn)在所在位置的GeoHash值為 wx4sv61q；
GeoHash標(biāo)識(shí)的并不是一個(gè)點(diǎn)，而是一個(gè)區(qū)域，比如 wx4sv61q 對(duì)應(yīng)的就是一個(gè)矩形區(qū)域；
編碼的前綴可以標(biāo)識(shí)更大的區(qū)域，比如 wx4sv61 編碼代表的區(qū)域要大于 wx4sv61q 代表的區(qū)域，但是 wx4sv61q 代表的區(qū)域一定在 wx4sv61 代表的區(qū)域內(nèi)。

因此我們?cè)偃プ鼍嚯x檢索的時(shí)候，只需要對(duì)GeoHash進(jìn)行前綴匹配即可，具體的原因在后面內(nèi)容進(jìn)行介紹。

GeoHash原理

GeoHash最簡單的解釋就是將一個(gè)位置信息轉(zhuǎn)化成一個(gè)可以排序、可以比較的字符串編碼。下面就詳細(xì)介紹以下其實(shí)現(xiàn)過程：

首先我們將緯度(-90, 90)平均分成兩個(gè)區(qū)間(-90, 0)、(0, 90)，如果坐標(biāo)位置的緯度值在第一區(qū)間，則編碼是0，否則編碼為1。我們用 40.222012 舉例，由于40.222012 屬于 (0, 90)，所以編碼為1，然后我們繼續(xù)將(0, 90)分成(0, 45)、(45, 90)兩個(gè)區(qū)間，而40.222012 位于(0, 45)，所以編碼是0，依次類推，我們進(jìn)行20次拆分，最后計(jì)算40.222012 的編碼是 10111001001101000110。

對(duì)于經(jīng)度采用同樣的的方法，得到 116.248283 的編碼是 11010010101010100101。

接下來我們對(duì)經(jīng)緯度的編碼合并，奇數(shù)為是緯度，偶數(shù)為是經(jīng)度，得到的編碼是 1110011101001001100011011001100000110110（這里需要特別注意，這里說的奇數(shù)、偶數(shù)是值數(shù)組的下標(biāo)，從0開始的）；

最后用base32編碼，二進(jìn)制串對(duì)應(yīng)的十進(jìn)制分別為 28, 29, 4, 24, 27, 6, 1, 22，轉(zhuǎn)化為base32是wx4sv61q，因此就得到(40.222012, 116.248283) 的編碼為 wx4sv61q。（下圖介紹了base32的對(duì)應(yīng)關(guān)系）

編碼 wx4sv61q 在地圖上對(duì)應(yīng)的位置如下圖：

這里我們GeoHash的編碼長度為8，這時(shí)精度在19米，下表列出了不同的編碼長度對(duì)應(yīng)的精度：

由上面的精度可知，如果要選取和我(40.222012, 116.248283)相距2km內(nèi)的物品，我們只需要查找物品坐標(biāo)對(duì)應(yīng)的GeoHash以wx4sv為前綴的即可。

GeoHash延伸

到目前為止我們對(duì)空間索引有了一定的了解，但是上面介紹的內(nèi)容對(duì)下面的一種情況就無法實(shí)現(xiàn)：

我們從圖中可以看出，紅點(diǎn)與上方的綠點(diǎn)距離較近，與下方的綠點(diǎn)距離較遠(yuǎn)，但是紅點(diǎn)與下方的綠點(diǎn)的編碼字符串一樣，都是wx4g0。對(duì)于GeoHash這種邊界問題解決思路也十分簡單，我們?cè)谧鰴z索或者查詢的時(shí)候，對(duì)周圍的八個(gè)區(qū)域進(jìn)行匹配，這樣就很好的解決了邊界問題。下面我們就對(duì)GeoHash用Java進(jìn)行實(shí)現(xiàn)。

JAVA實(shí)現(xiàn)

在實(shí)現(xiàn)之前，我們首先定義一個(gè)LocationBean，用它來表示經(jīng)緯度信息：

 /**  
 *@Description: 存儲(chǔ)經(jīng)緯度信息  
 */  
package com.lulei.geo.bean;  
  
public class LocationBean { 
  public static final double MINLAT = -90; 
  public static final double MAXLAT = 90; 
  public static final double MINLNG = -180; 
  public static final double MAXLNG = 180; 
  private double lat;//緯度[-90,90] 
  private double lng;//經(jīng)度[-180,180] 
   
  public LocationBean(double lat, double lng) { 
    this.lat = lat; 
    this.lng = lng; 
  } 
  public double getLat() { 
    return lat; 
  } 
  public void setLat(double lat) { 
    this.lat = lat; 
  } 
  public double getLng() { 
    return lng; 
  } 
  public void setLng(double lng) { 
    this.lng = lng; 
  } 
}

然后我們編寫一個(gè)類，來實(shí)現(xiàn)GeoHash，在實(shí)現(xiàn)GeoHash的過程中，我們需要用定義一些常量以及經(jīng)緯度信息，具體如下：

public class GeoHash { 
  private LocationBean location; 
  /** 
   * 1 2500km;2 630km;3 78km;4 30km 
   * 5 2.4km; 6 610m; 7 76m; 8 19m 
   */ 
  private int hashLength = 8; //經(jīng)緯度轉(zhuǎn)化為geohash長度 
  private int latLength = 20; //緯度轉(zhuǎn)化為二進(jìn)制長度 
  private int lngLength = 20; //經(jīng)度轉(zhuǎn)化為二進(jìn)制長度 
   
  private double minLat;//每格緯度的單位大小 
  private double minLng;//每個(gè)經(jīng)度的倒下 
  private static final char[] CHARS = {'0', '1', '2', '3', '4', '5', '6', '7',  
        '8', '9', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm', 'n',  
        'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'}; 
}

在GeoHash實(shí)例化時(shí)，我們需要對(duì)一些屬性進(jìn)行賦值：

public GeoHash(double lat, double lng) { 
  location = new LocationBean(lat, lng); 
  setMinLatLng(); 
} 
 
public int gethashLength() { 
  return hashLength; 
} 
 
/** 
 * @Author:lulei  
 * @Description: 設(shè)置經(jīng)緯度的最小單位 
 */ 
private void setMinLatLng() { 
  minLat = LocationBean.MAXLAT - LocationBean.MINLAT; 
  for (int i = 0; i < latLength; i++) { 
    minLat /= 2.0; 
  } 
  minLng = LocationBean.MAXLNG - LocationBean.MINLNG; 
  for (int i = 0; i < lngLength; i++) { 
    minLng /= 2.0; 
  } 
}

我們?cè)谑褂肎eoHash的時(shí)候，需要設(shè)置最終編碼的長度，因此編寫一個(gè)方法實(shí)現(xiàn)對(duì)GeoHash長度的設(shè)置

public boolean sethashLength(int length) { 
  if (length < 1) { 
    return false; 
  } 
  hashLength = length; 
  latLength = (length * 5) / 2; 
  if (length % 2 == 0) { 
    lngLength = latLength; 
  } else { 
    lngLength = latLength + 1; 
  } 
  setMinLatLng(); 
  return true; 
}

有了這些設(shè)置之后，我們需要將經(jīng)度、緯度轉(zhuǎn)化為對(duì)應(yīng)的二進(jìn)制編碼

private boolean[] getHashArray(double value, double min, double max, int length) { 
  if (value < min || value > max) { 
    return null; 
  } 
  if (length < 1) { 
    return null; 
  } 
  boolean[] result = new boolean[length]; 
  for (int i = 0; i < length; i++) { 
    double mid = (min + max) / 2.0; 
    if (value > mid) { 
      result[i] = true; 
      min = mid; 
    } else { 
      result[i] = false; 
      max = mid; 
    } 
  } 
  return result; 
}

分別獲取經(jīng)緯度的二進(jìn)制編碼后，我們需要將兩個(gè)二進(jìn)制字符串合并成一個(gè)

private boolean[] merge(boolean[] latArray, boolean[] lngArray) { 
  if (latArray == null || lngArray == null) { 
    return null; 
  } 
  boolean[] result = new boolean[lngArray.length + latArray.length]; 
  Arrays.fill(result, false); 
  for (int i = 0; i < lngArray.length; i++) { 
    result[2 * i] = lngArray[i]; 
  } 
  for (int i = 0; i < latArray.length; i++) { 
    result[2 * i + 1] = latArray[i]; 
  } 
  return result; 
}

最后我們需要將獲得的二進(jìn)制轉(zhuǎn)進(jìn)行base32轉(zhuǎn)化

/** 
 * @param lat 
 * @param lng 
 * @return 
 * @Author:lulei  
 * @Description: 獲取經(jīng)緯度的base32字符串 
 */ 
private String getGeoHashBase32(double lat, double lng) { 
  boolean[] bools = getGeoBinary(lat, lng); 
  if (bools == null) { 
    return null; 
  } 
  StringBuffer sb = new StringBuffer(); 
  for (int i = 0; i < bools.length; i = i + 5) { 
    boolean[] base32 = new boolean[5]; 
    for (int j = 0; j < 5; j++) { 
      base32[j] = bools[i + j]; 
    } 
    char cha = getBase32Char(base32); 
    if (' ' == cha) { 
      return null; 
    } 
    sb.append(cha); 
  } 
  return sb.toString(); 
} 
 
/** 
 * @param base32 
 * @return 
 * @Author:lulei  
 * @Description: 將五位二進(jìn)制轉(zhuǎn)化為base32 
 */ 
private char getBase32Char(boolean[] base32) { 
  if (base32 == null || base32.length != 5) { 
    return ' '; 
  } 
  int num = 0; 
  for (boolean bool : base32) { 
    num <<= 1; 
    if (bool) { 
      num += 1; 
    } 
  } 
  return CHARS[num % CHARS.length]; 
}

對(duì)于如何獲取周圍八個(gè)區(qū)域的GeoHash值這個(gè)問題我們可以做如下轉(zhuǎn)化，我們已經(jīng)知道當(dāng)前點(diǎn)的經(jīng)緯度值，我們也知道每一個(gè)區(qū)域內(nèi)的經(jīng)度、緯度的寬度，如果經(jīng)度加上或減去這個(gè)寬度，我們就可以位于該區(qū)域左側(cè)和右側(cè)區(qū)域的經(jīng)度，如果緯度加上或減去這個(gè)寬度，我們就可以獲取該區(qū)域上部和下部的緯度，這樣我們就可以分別獲取到該區(qū)域周圍八個(gè)區(qū)域內(nèi)的一個(gè)點(diǎn)的坐標(biāo)，我們分別計(jì)算這八個(gè)點(diǎn)的坐標(biāo)，也就是八個(gè)區(qū)域?qū)?yīng)的GeoHash編碼。

public List<String> getGeoHashBase32For9() { 
  double leftLat = location.getLat() - minLat; 
  double rightLat = location.getLat() + minLat; 
  double upLng = location.getLng() - minLng; 
  double downLng = location.getLng() + minLng; 
  List<String> base32For9 = new ArrayList<String>(); 
  //左側(cè)從上到下 3個(gè) 
  String leftUp = getGeoHashBase32(leftLat, upLng); 
  if (!(leftUp == null || "".equals(leftUp))) { 
    base32For9.add(leftUp); 
  } 
  String leftMid = getGeoHashBase32(leftLat, location.getLng()); 
  if (!(leftMid == null || "".equals(leftMid))) { 
    base32For9.add(leftMid); 
  } 
  String leftDown = getGeoHashBase32(leftLat, downLng); 
  if (!(leftDown == null || "".equals(leftDown))) { 
    base32For9.add(leftDown); 
  } 
  //中間從上到下 3個(gè) 
  String midUp = getGeoHashBase32(location.getLat(), upLng); 
  if (!(midUp == null || "".equals(midUp))) { 
    base32For9.add(midUp); 
  } 
  String midMid = getGeoHashBase32(location.getLat(), location.getLng()); 
  if (!(midMid == null || "".equals(midMid))) { 
    base32For9.add(midMid); 
  } 
  String midDown = getGeoHashBase32(location.getLat(), downLng); 
  if (!(midDown == null || "".equals(midDown))) { 
    base32For9.add(midDown); 
  } 
  //右側(cè)從上到下 3個(gè) 
  String rightUp = getGeoHashBase32(rightLat, upLng); 
  if (!(rightUp == null || "".equals(rightUp))) { 
    base32For9.add(rightUp); 
  } 
  String rightMid = getGeoHashBase32(rightLat, location.getLng()); 
  if (!(rightMid == null || "".equals(rightMid))) { 
    base32For9.add(rightMid); 
  } 
  String rightDown = getGeoHashBase32(rightLat, downLng); 
  if (!(rightDown == null || "".equals(rightDown))) { 
    base32For9.add(rightDown); 
  } 
  return base32For9; 
}

運(yùn)行結(jié)果

完整代碼

上面的博客中已經(jīng)有完整的LoacationBean代碼，這里就不再寫了。

/**  
 *@Description: GeoHash實(shí)現(xiàn)經(jīng)緯度的轉(zhuǎn)化 
 */  
package com.lulei.geo;  
 
import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.List; 
 
import com.lulei.geo.bean.LocationBean; 
import com.lulei.util.JsonUtil; 
  
public class GeoHash { 
  private LocationBean location; 
  /** 
   * 1 2500km;2 630km;3 78km;4 30km 
   * 5 2.4km; 6 610m; 7 76m; 8 19m 
   */ 
  private int hashLength = 8; //經(jīng)緯度轉(zhuǎn)化為geohash長度 
  private int latLength = 20; //緯度轉(zhuǎn)化為二進(jìn)制長度 
  private int lngLength = 20; //經(jīng)度轉(zhuǎn)化為二進(jìn)制長度 
   
  private double minLat;//每格緯度的單位大小 
  private double minLng;//每個(gè)經(jīng)度的倒下 
  private static final char[] CHARS = {'0', '1', '2', '3', '4', '5', '6', '7',  
        '8', '9', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm', 'n',  
        'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'}; 
   
  public GeoHash(double lat, double lng) { 
    location = new LocationBean(lat, lng); 
    setMinLatLng(); 
  } 
   
  public int gethashLength() { 
    return hashLength; 
  } 
   
  /** 
   * @Author:lulei  
   * @Description: 設(shè)置經(jīng)緯度的最小單位 
   */ 
  private void setMinLatLng() { 
    minLat = LocationBean.MAXLAT - LocationBean.MINLAT; 
    for (int i = 0; i < latLength; i++) { 
      minLat /= 2.0; 
    } 
    minLng = LocationBean.MAXLNG - LocationBean.MINLNG; 
    for (int i = 0; i < lngLength; i++) { 
      minLng /= 2.0; 
    } 
  } 
   
  /** 
   * @return 
   * @Author:lulei  
   * @Description: 求所在坐標(biāo)點(diǎn)及周圍點(diǎn)組成的九個(gè) 
   */ 
  public List<String> getGeoHashBase32For9() { 
    double leftLat = location.getLat() - minLat; 
    double rightLat = location.getLat() + minLat; 
    double upLng = location.getLng() - minLng; 
    double downLng = location.getLng() + minLng; 
    List<String> base32For9 = new ArrayList<String>(); 
    //左側(cè)從上到下 3個(gè) 
    String leftUp = getGeoHashBase32(leftLat, upLng); 
    if (!(leftUp == null || "".equals(leftUp))) { 
      base32For9.add(leftUp); 
    } 
    String leftMid = getGeoHashBase32(leftLat, location.getLng()); 
    if (!(leftMid == null || "".equals(leftMid))) { 
      base32For9.add(leftMid); 
    } 
    String leftDown = getGeoHashBase32(leftLat, downLng); 
    if (!(leftDown == null || "".equals(leftDown))) { 
      base32For9.add(leftDown); 
    } 
    //中間從上到下 3個(gè) 
    String midUp = getGeoHashBase32(location.getLat(), upLng); 
    if (!(midUp == null || "".equals(midUp))) { 
      base32For9.add(midUp); 
    } 
    String midMid = getGeoHashBase32(location.getLat(), location.getLng()); 
    if (!(midMid == null || "".equals(midMid))) { 
      base32For9.add(midMid); 
    } 
    String midDown = getGeoHashBase32(location.getLat(), downLng); 
    if (!(midDown == null || "".equals(midDown))) { 
      base32For9.add(midDown); 
    } 
    //右側(cè)從上到下 3個(gè) 
    String rightUp = getGeoHashBase32(rightLat, upLng); 
    if (!(rightUp == null || "".equals(rightUp))) { 
      base32For9.add(rightUp); 
    } 
    String rightMid = getGeoHashBase32(rightLat, location.getLng()); 
    if (!(rightMid == null || "".equals(rightMid))) { 
      base32For9.add(rightMid); 
    } 
    String rightDown = getGeoHashBase32(rightLat, downLng); 
    if (!(rightDown == null || "".equals(rightDown))) { 
      base32For9.add(rightDown); 
    } 
    return base32For9; 
  } 
 
  /** 
   * @param length 
   * @return 
   * @Author:lulei  
   * @Description: 設(shè)置經(jīng)緯度轉(zhuǎn)化為geohash長度 
   */ 
  public boolean sethashLength(int length) { 
    if (length < 1) { 
      return false; 
    } 
    hashLength = length; 
    latLength = (length * 5) / 2; 
    if (length % 2 == 0) { 
      lngLength = latLength; 
    } else { 
      lngLength = latLength + 1; 
    } 
    setMinLatLng(); 
    return true; 
  } 
   
  /** 
   * @return 
   * @Author:lulei  
   * @Description: 獲取經(jīng)緯度的base32字符串 
   */ 
  public String getGeoHashBase32() { 
    return getGeoHashBase32(location.getLat(), location.getLng()); 
  } 
   
  /** 
   * @param lat 
   * @param lng 
   * @return 
   * @Author:lulei  
   * @Description: 獲取經(jīng)緯度的base32字符串 
   */ 
  private String getGeoHashBase32(double lat, double lng) { 
    boolean[] bools = getGeoBinary(lat, lng); 
    if (bools == null) { 
      return null; 
    } 
    StringBuffer sb = new StringBuffer(); 
    for (int i = 0; i < bools.length; i = i + 5) { 
      boolean[] base32 = new boolean[5]; 
      for (int j = 0; j < 5; j++) { 
        base32[j] = bools[i + j]; 
      } 
      char cha = getBase32Char(base32); 
      if (' ' == cha) { 
        return null; 
      } 
      sb.append(cha); 
    } 
    return sb.toString(); 
  } 
   
  /** 
   * @param base32 
   * @return 
   * @Author:lulei  
   * @Description: 將五位二進(jìn)制轉(zhuǎn)化為base32 
   */ 
  private char getBase32Char(boolean[] base32) { 
    if (base32 == null || base32.length != 5) { 
      return ' '; 
    } 
    int num = 0; 
    for (boolean bool : base32) { 
      num <<= 1; 
      if (bool) { 
        num += 1; 
      } 
    } 
    return CHARS[num % CHARS.length]; 
  } 
   
  /** 
   * @param lat 
   * @param lng 
   * @return 
   * @Author:lulei  
   * @Description: 獲取坐標(biāo)的geo二進(jìn)制字符串 
   */ 
  private boolean[] getGeoBinary(double lat, double lng) { 
    boolean[] latArray = getHashArray(lat, LocationBean.MINLAT, LocationBean.MAXLAT, latLength); 
    boolean[] lngArray = getHashArray(lng, LocationBean.MINLNG, LocationBean.MAXLNG, lngLength); 
    return merge(latArray, lngArray); 
  } 
   
  /** 
   * @param latArray 
   * @param lngArray 
   * @return 
   * @Author:lulei  
   * @Description: 合并經(jīng)緯度二進(jìn)制 
   */ 
  private boolean[] merge(boolean[] latArray, boolean[] lngArray) { 
    if (latArray == null || lngArray == null) { 
      return null; 
    } 
    boolean[] result = new boolean[lngArray.length + latArray.length]; 
    Arrays.fill(result, false); 
    for (int i = 0; i < lngArray.length; i++) { 
      result[2 * i] = lngArray[i]; 
    } 
    for (int i = 0; i < latArray.length; i++) { 
      result[2 * i + 1] = latArray[i]; 
    } 
    return result; 
  } 
   
  /** 
   * @param value 
   * @param min 
   * @param max 
   * @return 
   * @Author:lulei  
   * @Description: 將數(shù)字轉(zhuǎn)化為geohash二進(jìn)制字符串 
   */ 
  private boolean[] getHashArray(double value, double min, double max, int length) { 
    if (value < min || value > max) { 
      return null; 
    } 
    if (length < 1) { 
      return null; 
    } 
    boolean[] result = new boolean[length]; 
    for (int i = 0; i < length; i++) { 
      double mid = (min + max) / 2.0; 
      if (value > mid) { 
        result[i] = true; 
        min = mid; 
      } else { 
        result[i] = false; 
        max = mid; 
      } 
    } 
    return result; 
  } 
   
 
  public static void main(String[] args) { 
    // TODO Auto-generated method stub  
    GeoHash g = new GeoHash(40.222012, 116.248283); 
    System.out.println(g.getGeoHashBase32()); 
    System.out.println(JsonUtil.parseJson(g.getGeoHashBase32For9())); 
  } 
 
}

以上就是本文的全部內(nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: