Google App Engine Geohashing

Question

我正在使用GWT和App Engine編寫一個Web應用程序。我的應用程序需要根據緯度，經度來發布和查詢項目。

由於谷歌的分佈式數據庫設計，你不能簡單地查詢一組不平等。相反，他們建議做geohashing。該方法在此頁面上進行了描述。

http://code.google.com/appengine/articles/geosearch.html

基本上你預先計算出一個邊框，這樣就可以查詢已經標記與邊框的項目。

有一部分過程我不明白。 「切片」屬性意味着什麼？

感謝您的幫助！

Answer 1

對於地質模型的完整的Java搬運，請參閱http://code.google.com/p/javageomodel/。

有一個演示類來解釋你如何使用它。

Answer 2

除了用4個座標（最小和最大緯度，最小和最大經度）定義邊界框外，還可以使用框的西北角座標和兩個參數：分辨率和切片來定義它。 分辨率定義了盒子的比例，它是以小數點以下的數字數量實現的。 切片是盒子的寬度和高度，以最低有效數字爲單位。

在geobox.py的意見更詳細解釋這一點，有很好的例子：

要查詢的邊界框的成員，我們先從一些輸入座標 像緯度= 37.78452長= -122.39532（包括決議5）。然後，我們將這些座標向上和向下四捨五入成最接近的「切片」來生成一個geobox。 「切片」 是如何精細地劃分地理框中的每個分辨率級別。最小的 切片大小爲1，最大值沒有限制，因爲較大的切片將 只是溢出到較低的分辨率（希望這些示例將解釋）。

一些例子：

分辨率= 5，切片= 2，和LAT = 37.78452長= -122.39532： 「37.78452 | -122.39532 | 37.78450 | -122.39530」

分辨率= 5，切片= 10，和LAT = 37.78452長= -122.39532： 「37.78460 | -122.39540 | 37.78450 | -122.39530」

分辨率= 5，切片= 25，和LAT = 37.78452長= -122.39532： 「37.78475 | -122.39550 | 37.78450 | -122.39525「

Answer 3

您可能會對GeoModel開源項目感興趣，而不是自己實施geohash，它在Google App Engine上實現了類似geohash的系統。您可以導入此庫並撥打電話proximity_fetch()和bounding_box_fetch()，而不是理解所有的細節。

This more recent article描述了它是如何工作的，並提供了一個使用它的例子。

Answer 4

我正在GWT/GAE project並且有同樣的問題。我的解決方案是使用一個我稍微修改過的GWT友好型的Geohash類。這對我的鄰近搜索需求非常好。

如果你從未見過Geohashes在行動，請查看Dave Troy's JS演示頁面。

Answer 5

我還需要Java版本的GeoModel。之前我和Geohash一起工作過，它允許我在給定的邊界框中獲取位置。但是在排序時存在相當大的侷限性：爲了讓BigTable接受像geohash > '" + bottomLeft + "' && geohash < '" + topRight + "'"這樣的過濾器，您還必須訂購geohash的列表，這使得無法按其他條件對其進行排序（特別是如果您想要使用分頁）。與此同時，我只是想不出一個解決方案，按照距離（從給定的用戶位置，即邊界框的中心）對結果進行排序，而不是使用Java代碼。再一次，如果你需要分頁，這是行不通的。

由於這些問題，我不得不使用不同的方法，GeoModel/Geoboxes似乎是這樣。所以，我將Python代碼移植到了Java，並且它工作的很好！下面是結果：

public class Geobox { 

    private static double roundSlicedown(double coord, double slice) { 
     double remainder = coord % slice; 
     if (remainder == Double.NaN) { 
      return coord; 
     } 
     if (coord > 0) { 
      return coord - remainder + slice; 
     } else { 
      return coord - remainder; 
     } 
    } 

    private static double[] computeTuple(double lat, double lng, 
      int resolution, double slice) { 
     slice = slice * Math.pow(10, -resolution); 
     double adjustedLat = roundSlicedown(lat, slice); 
     double adjustedLng = roundSlicedown(lng, slice); 
     return new double[] { adjustedLat, adjustedLng - slice, 
       adjustedLat - slice, adjustedLng }; 
    } 

    private static String formatTuple(double[] values, int resolution) { 
     StringBuffer s = new StringBuffer(); 
     String format = String.format("%%.%df", resolution); 
     for (int i = 0; i < values.length; i++) { 
      s.append(String.format(format, values[i]).replace(',','.')); 
      if (i < values.length - 1) { 
       s.append("|"); 
      } 
     } 
     return s.toString(); 
    } 

    public static String compute(double lat, double lng, int resolution, 
      int slice) { 
     return formatTuple(computeTuple(lat, lng, resolution, slice), 
       resolution); 
    } 

    public static List<String> computeSet(double lat, double lng, 
      int resolution, double slice) { 
     double[] primaryBox = computeTuple(lat, lng, resolution, slice); 
     slice = slice * Math.pow(10, -resolution); 
     List<String> set = new ArrayList<String>(); 
     for (int i = -1; i < 2; i++) { 
      double latDelta = slice * i; 
      for (int j = -1; j < 2; j++) { 
       double lngDelta = slice * j; 
       double[] adjustedBox = new double[] { primaryBox[0] + latDelta, 
         primaryBox[1] + lngDelta, primaryBox[2] + latDelta, 
         primaryBox[3] + lngDelta }; 
       set.add(formatTuple(adjustedBox, resolution)); 
      } 
     } 
     return set; 
    } 
} 

Answer 6

我正在用geohashing一個GAE項目，這條巨蟒圖書館爲我做的伎倆：http://mappinghacks.com/code/geohash.py.txt

Answer 7

遺憾的答案晚了，但我沒有回到這個頁面一段時間。使用地理方塊的方式可能看起來像這樣的GeoDao實現：

public class GeoDaoImpl extends DaoImpl<T extends GeoModel> { 

    // geobox configs are: resolution, slice, use set (1 = true) 
    private final static int[][] GEOBOX_CONFIGS = 
     { { 4, 5, 1 }, 
      { 3, 2, 1 }, 
      { 3, 8, 0 }, 
      { 3, 16, 0 }, 
      { 2, 5, 0 } }; 

    public GeoDaoImpl(Class<T> persistentClass) { 
     super(persistentClass); 
    } 

    public List<T> findInGeobox(double lat, double lng, int predefinedBox, String filter, String ordering, int offset, int limit) { 
     return findInGeobox(lat, lng, GEOBOX_CONFIGS[predefinedBox][0], GEOBOX_CONFIGS[predefinedBox][1], filter, ordering, offset, limit);  
    } 

    public List<T> findInGeobox(double lat, double lng, int resolution, int slice, String filter, String ordering, int offset, int limit) { 
     String box = Geobox.compute(lat, lng, resolution, slice); 
     if (filter == null) { 
      filter = ""; 
     } else { 
      filter += " && "; 
     } 
     filter += "geoboxes=='" + box + "'";   
     return super.find(persistentClass, filter, ordering, offset, limit); 
    } 

    public List<T> findNearest(final double lat, final double lng, String filter, String ordering, int offset, int limit) { 
     LinkedHashMap<String, T> uniqueList = new LinkedHashMap<String, T>(); 
     int length = offset + limit; 
     for (int i = 0; i < GEOBOX_CONFIGS.length; i++) {  
      List<T> subList = findInGeobox(lat, lng, i, filter, ordering, 0, limit); 
      for (T model : subList) { 
       uniqueList.put(model.getId(), model); 
      } 
      if (uniqueList.size() >= length) { 
       break; 
      } 
     } 

     List<T> list = new ArrayList<T>(); 
     int i = 0; 
     for (String key : uniqueList.keySet()) { 
      if (i >= offset && i <= length) { 
       list.add(uniqueList.get(key)); 
      } 
      i++; 
     } 

     Collections.sort(list, new Comparator<T>() { 
      public int compare(T model1, T model2) {     
       double distance1 = Geoutils.distFrom(model1.getLatitude(), model1.getLongitude(), lat, lng); 
       double distance2 = Geoutils.distFrom(model2.getLatitude(), model2.getLongitude(), lat, lng); 
       return Double.compare(distance1, distance2); 
      } 
     }); 

     return list; 
    } 

    @Override 
    public void save(T model) { 
     preStore(model); 
     super.save(model); 
    } 

    private void preStore(T model) { 
     // geoboxes are needed to find the nearest entities and sort them by distance 
     List<String> geoboxes = new ArrayList<String>(); 
     for (int[] geobox : GEOBOX_CONFIGS) { 
      // use set 
      if (geobox[2] == 1) { 
       geoboxes.addAll(Geobox.computeSet(model.getLatitude(), model.getLongitude(), geobox[0], geobox[1])); 
      } else { 
       geoboxes.add(Geobox.compute(model.getLatitude(), model.getLongitude(), geobox[0], geobox[1])); 
      } 
     } 
     model.setGeoboxes(geoboxes); 
    } 

} 

Answer 8

在App Engine中執行地理空間搜索的替代方法是Search Api。您不必擔心地理散亂或實施細節，並且您可以搜索接近地理點的元素。

https://developers.google.com/appengine/docs/python/search/overview#Performing_Location-Based_Searches