How to encode latitude/longitude for box search?

Question

I'm developing an application on Google App Engine and needs to find all the points that are in a box.

A basic SQL search would be:

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

But, this request is both inefficient and forbidden (you cannot use inequality on 2 different fields) on Google App Engine.

So, I encoded latitude/longitude with hierarchical order http://en.wikipedia.org/wiki/Geohash.

But using Geohash has some issues: Yes, it will find all your points that are in the box, but it will also find points out-of the box.

Let’s take an example:
A box with a lower-left corner of (1, 1) -> geohash1 = s00twy01mtw0
and a upper right corner (10, 10) -> geohash2 = s1z0gs3y0zh7
will accept point P like (2, 11) -> geohashP = s0rg6k1fye42
because geohash1 < geohashP < geohash2
even if P is not in the box.

Any idea about an efficient way to get all the points that are in the box (and only them)?
I'm now thinking about post-processing the additional wrong points after the request.

Answer 1

You can theoretical use Cantor pairing function to map the four coordinates of your rectangle to a single value but I am not sure if it is (easily) possible to perform inclusion test on such values.

Answer 2

Don't reinvent the wheel! Spatial queries are a tough problem, but one that's already been solved by several third-party libraries. The best of those is probably the geomodel library.

Answer 3

Geomodel does the job.

I ported the python library into java.

For those who are interested in, check: http://code.google.com/p/javageomodel/