algorithm - 如何为框搜索编码纬度/经度？

Question

我正在 Google App Engine 上开发一个应用程序，需要找到一个盒子里的所有点。

基本的 SQL 搜索是:

minlatitude < latitude AND maxlatitude > latitude AND minlongitude < longitude AND maxlongitude > longitude

但是，此请求在 Google App Engine 上既低效又被禁止(您不能在 2 个不同的字段上使用不等式)。

因此，我使用层级顺序对纬度/经度进行编码 http://en.wikipedia.org/wiki/Geohash .

但是使用 Geohash 有一些问题:是的，它会找到你在盒子里的所有点，但它也会找到盒子外的点。

举个例子:
左下角为 (1, 1) 的框 -> geohash1 = s00twy01mtw0
和右上角 (10, 10) -> geohash2 = s1z0gs3y0zh7
将接受点 P，如 (2, 11) -> geohashP = s0rg6k1fye42
因为 geohash1 < geohashP < geohash2
即使 P 不在盒子里。

关于获取框中所有点(并且只有它们)的有效方法有什么想法吗？
我现在正在考虑在请求之后对额外的错误点进行后处理。

Answer 1

不要重新发明轮子!空间查询是一个棘手的问题，但几个第三方库已经解决了这个问题。其中最好的可能是 geomodel library .