Google App Engine 地理哈希

Question

我正在使用 GWT 和 App Engine 编写一个 Web 应用程序。我的应用程序需要根据纬度、经度发布和查询项目。

由于谷歌的分布式数据库设计，你不能简单地查询一组不等式。相反，他们建议进行地理哈希。本页描述了该方法。

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

本质上，您预先计算一个边界框，以便您可以查询已用该边界框标记的项目。

这个过程中有一部分我不明白。 “切片”属性是什么意思？

感谢您的帮助！

Answer 1

有关 Geomodel 的完整 Java 移植，请参阅 http://code.google.com/p/javageomodel/ 。

有一个演示课程可以向您解释如何使用它。

Answer 2

您可能对 GeoModel 开源项目感兴趣，而不是自己实现 geohash，该项目实现了Google App Engine 上类似 geohash 的系统。您无需了解所有细节，只需导入该库并进行诸如 proximity_fetch() 和 bounding_box_fetch() 之类的调用即可。

这篇最新文章介绍了它的工作原理并提供了使用它的示例。

Answer 3

您可以使用框西北角的坐标以及两个参数来定义边界框，而不是使用 4 个坐标（最小和最大纬度、最小和最大经度）来定义边界框：分辨率和切片。
分辨率定义了框的比例，它被实现为小数点以下的位数。
切片是盒子的宽度和高度，使用最低有效数字作为单位。

geobox.py 中的注释对此进行了更多解释详细信息，有很好的例子：

为了查询边界框的成员，我们从一些输入坐标开始
如 lat=37.78452 long=-122.39532 （均为分辨率 5）。然后我们将这些
上下坐标到最近的“切片”以生成地理框。一个“片”
是在 geobox 中划分每个分辨率级别的精细程度。最低
切片大小为 1，最大值没有限制，因为较大的切片会
只是溢出到较低的分辨率（希望示例能够解释）。

一些例子：

分辨率=5，切片=2，纬度=37.78452 长=-122.39532：
“37.78452|-122.39532|37.78450|-122.39530”

分辨率=5，切片=10，纬度=37.78452 长=-122.39532：
“37.78460|-122.39540|37.78450|-122.39530”

分辨率=5，切片=25，纬度=37.78452 长=-122.39532：
“37.78475|-122.39550|37.78450|-122.39525”

Answer 4

我正在开发一个 GWT/GAE 项目，并且遇到了同样的问题。我的解决方案是使用 Geohash 类，我对其进行了稍微修改以使其适合 GWT。这非常适合我的邻近搜索需求。

如果您从未见过 Geohashes 的实际应用，请查看 Dave Troy 的 JS 演示页面。

Answer 5

在 App Engine 中进行地理空间搜索的另一种方法是搜索 Api。您无需担心地理散列或实施细节，并且您将能够搜索靠近地理点的元素。

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

Answer 6

我正在使用 geohashing 开发一个 GAE 项目，这个 python 库为我解决了这个问题： http:// /mappinghacks.com/code/geohash.py.txt

Answer 7

我还需要 Java 版本的 GeoModel。我之前使用过 Geohash，它允许我获取给定边界框中的位置。但是在排序方面存在相当大的限制：为了让 BigTable 接受像 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 8

抱歉回复晚了，但我有一段时间没有返回此页面了。使用 Geobox 方法的 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);
    }

}