Google App Engine Geohashing

Question

Estoy escribiendo una aplicación web usando GWT y App Engine. Mi aplicación necesitará publicar y consultar elementos en función de su latitud y longitud.

Como resultado del diseño de la base de datos distribuida de Google, no se puede hacer una simple consulta de un conjunto de desigualdades. En cambio, sugieren hacer geohashing. El método se describe en esta página.

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

Esencialmente pre calcular un cuadro delimitador para que pueda consultar los artículos que han sido etiquetados con ese cuadro delimitador.

Hay una parte del proceso que no entiendo. ¿Qué significa el atributo "slice"?

Gracias por su ayuda!

Answer 1

Para una Portage java completa de GeoModel, por favor ver http://code.google.com/p/javageomodel/.

Hay una clase de demostración para explicarte cómo usarla.

Answer 2

En lugar de definir un cuadro delimitador con 4 coordenadas (latitud mínima y máxima, longitud mínima y máxima), puede definirlo con las coordenadas de la esquina noroeste del cuadro y dos parámetros: resolución y división. La resolución define la escala del cuadro, se implementa como el número de figuras debajo del punto decimal. El corte es el ancho y alto de la caja, usando la figura menos significativa como su unidad.

Los comentarios en esta geobox.py explican con más detalle, con buenos ejemplos:

para consultar los miembros de un cuadro delimitador, comenzamos con alguna entrada coordenadas como lat = 37.78452 largo = -122,39532 (tanto resolución 5). Luego redondeamos estas coordenadas hacia arriba y hacia abajo al "sector" más cercano para generar un geobox. Una "porción" es la forma fina de dividir cada nivel de resolución en el geobox. El tamaño de corte mínimo de es 1, el máximo no tiene límite, ya que las rebanadas más grandes se se derraman en resoluciones más bajas (con suerte los ejemplos explicarán).

Algunos ejemplos:

resolución = 5, rebanada = 2, y = lat 37.78452 largo = -122,39532: "37.78452 | -122,39532 | 37.78450 | -122,39530"

resolución = 5, = rebanada 10, y lat = 37.78452 largo = -122,39532: "37.78460 | -122,39540 | 37.78450 | -122,39530"

resolución = 5, rebanada = 25, y = lat 37.78452 largo = -122,39532: "37.78475 | -122,39550 | 37.78450 | -122.39525 "

Answer 3

En lugar de implementar el geohash usted mismo, puede interesarle el proyecto de código abierto GeoModel que implementa un sistema parecido a geohash en Google App Engine. En lugar de entender todos los detalles, puede importar esta biblioteca y hacer llamadas como proximity_fetch() y bounding_box_fetch().

This more recent article describe cómo funciona y proporciona un ejemplo que lo usa.

Answer 4

Estoy trabajando en un GWT/GAE project y tuve el mismo problema. Mi solución fue utilizar una clase Geohash que modifiqué ligeramente para que fuera compatible con GWT. Es ideal para mis necesidades de búsquedas de proximidad.

Si nunca ha visto Geohashes en acción, consulte la página de demostración de Dave Troy's JS.

Answer 5

También necesitaba una versión Java de GeoModel. Estuve trabajando con Geohash antes, lo que me permitió buscar ubicaciones en un cuadro delimitador dado. Pero hay limitaciones considerables a la hora de clasificar: para que BigTable acepte un filtro como geohash > '" + bottomLeft + "' && geohash < '" + topRight + "'", también debe ordenar la lista por geohash, lo que hace que sea imposible ordenarla por otros criterios (especialmente si quiero usar la paginación). Al mismo tiempo, no puedo pensar en una solución para ordenar los resultados por distancia (desde una posición de usuario determinada, es decir, el centro del cuadro delimitador), salvo en el código Java. Nuevamente, esto no funcionará si necesita paginación.

Debido a estos problemas, tuve que utilizar un enfoque diferente, y GeoModel/Geoboxes parecía ser el camino. Por lo tanto, porté el código de Python a Java y está funcionando bien. Aquí está el resultado:

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

yo estaba trabajando en un proyecto con GAE geohashing y esto bibliotecas de Python hizo el truco para mí: http://mappinghacks.com/code/geohash.py.txt

Answer 7

lo siento por el retraso en la respuesta, pero no volvería a este página por algún tiempo. Una aplicación GeoDao utilizando el enfoque GEObox podría tener este aspecto:

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

Una alternativa para realizar búsquedas geoespaciales en App Engine es Search Api. No tendrá que preocuparse por los detalles de geoinformación o implementación, y podrá buscar elementos cercanos al punto geográfico.

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