Comment encoder la latitude/longitude pour la recherche de boîte?

Question

Je développe une application sur Google App Engine et j'ai besoin de trouver tous les points qui se trouvent dans une boîte.

Une recherche SQL de base serait:

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

Mais, cette demande est à la fois inefficace et interdit (vous ne pouvez pas utiliser l'inégalité sur 2 champs différents) sur Google App Engine. Donc, j'ai codé la latitude/longitude avec l'ordre hiérarchique http://en.wikipedia.org/wiki/Geohash.

Mais utiliser Geohash a quelques problèmes: Oui, il trouvera tous vos points qui sont dans la boîte, mais il trouvera également des points de sortie de la boîte.

Prenons un exemple:
Une boîte avec un coin inférieur gauche de (1, 1) - > geohash1 = s00twy01mtw0
et un coin supérieur droit (10, 10) - > geohash2 = s1z0gs3y0zh7
sera accepter le point P comme (2, 11) - > geohashP = s0rg6k1fye42
parce geohash1 < geohashP < geohash2
même si P est pas dans la boîte.

Une idée sur un moyen efficace d'obtenir tous les points qui sont dans la boîte (et seulement eux)?
Je pense maintenant à post-traiter les mauvais points supplémentaires après la demande.

Answer 1

Vous pouvez utiliser théoriquement Cantor pairing function pour mapper les quatre coordonnées de votre rectangle à une seule valeur mais je ne suis pas sûr s'il est (facilement) possible d'effectuer un test d'inclusion sur ces valeurs.

Answer 2

Ne pas réinventer la roue! Les requêtes spatiales sont un problème difficile, mais qui a déjà été résolu par plusieurs bibliothèques tierces. Le meilleur de ceux-ci est probablement le geomodel library.

Answer 3

Geomodel fait le travail.

J'ai porté la bibliothèque python dans java.

Pour ceux qui sont intéressés, consultez: http://code.google.com/p/javageomodel/