[geodatastore commit] r23 - trunk
codesite...@google.com
Date: Mon Aug 25 08:38:21 2008
New Revision: 23
Added:
trunk/geohash.py (contents, props changed)
Modified:
trunk/geoserv.py
trunk/index.yaml
trunk/locator.py
Log:
Added geohash to point objects, locator.py queries now based on sorting
geohash (to mitigate running into the 1000 result limit of App Engine)
Added: trunk/geohash.py
==============================================================================
--- (empty file)
+++ trunk/geohash.py Mon Aug 25 08:38:21 2008
@@ -0,0 +1,209 @@
+#!/usr/bin/python
+"""
+ implementation of http://en.wikipedia.org/wiki/Geohash
+
+ This module was written in May 2008 by Schuyler Erle and is made
+ available in the public domain. Cheers to Christopher Schmidt for
+ suggesting it. Works in Python 2.3 and up. Run it on the command
+ line to try the doctests. Please send patches, comments, etc. to
+ schu...@geocoder.us.
+
+ You can instantiate a Geohash object with a (lon,lat) tuple, or with
+ a string. The bbox() and point() methods return the bounding box
+ and the center point of the area indicated by the geohash. Casting
+ the Geohash object to a string gives the hash itself.
+
+ Adding two Geohash objects together gives the Geohash of their
+ minimal bounding box.
+
+ The Geohash class inherits from a Geostring class, which provides an
+ identical API, but returns strings consisting of interleaved 0 and
+ 1 bits. Geostring is a less compact representation than the Geohash
+ class, but *much* more suitable for use when storing and comparing
+ bounding boxes in a B-Tree or similar index. If you are storing
+ bounding boxes in a database and space is not a major concern, you
+ should use the Geostring class instead of the Geohash.
+
+>>> hash = Geohash((-0.25, 51.5))
+>>> str(hash)
+'gcpufr3cnxf6q'
+>>> hash.bbox()
+(-0.25, 51.5, -0.25, 51.5)
+>>> hash.point()
+(-0.25, 51.5)
+>>> hash.bbox(4)
+(-0.35156300000000001, 51.328125, 0.0, 51.503906000000001)
+
+*** note, floating point representations are weird
+>>> -0.35156300000000001 == -0.351563
+True
+
+>>> hash = Geohash('9q8yykc03ycmh')
+>>> hash.bbox()
+(-122.41920399999999, 37.775196000000001, -122.41920399999999,
37.775196000000001)
+>>> hash.point()
+(-122.41920399999999, 37.775196000000001)
+>>> hash.bbox(3)
+(-123.75, 36.5625, -120.9375, 37.96875)
+>>> union = hash + Geohash('9q8yze443z')
+>>> str(union)
+'9q8y'
+
+*** see note above
+>>> -122.419204 == -122.41920399999999
+True
+
+A degenerate example, but at least it works lexically:
+
+>>> hash = Geoindex((-0.25,51.5),depth=8)
+>>> str(hash)
+'0222202022202022'
+>>> hash.bbox()
+(-1.40625, 51.328125, 0.0, 52.03125)
+>>> hash2 = Geoindex((0.25,52.5),depth=8)
+>>> str(hash2)
+'2202000002000200'
+>>> str(hash+hash2)
+'1111111111111111'
+>>> str(hash+hash2) > str(hash)
+True
+>>> str(hash+hash2) < str(hash2)
+True
+
+>>> hash = Geostring((-0.25,51.5),depth=8)
+>>> str(hash)
+'0111101011101011'
+>>> hash.bbox()
+(-1.40625, 51.328125, 0.0, 52.03125)
+
+Some degenerate cases:
+
+>>> west = Geostring("0")
+>>> west.bbox()
+(-180.0, -90.0, 0.0, 90.0)
+>>> east = Geostring("1")
+>>> east.bbox()
+(0.0, -90.0, 180.0, 90.0)
+>>> str(east+west)
+''
+>>> (east+west).bbox()
+(-180.0, -90.0, 180.0, 90.0)
+"""
+
+class Geostring (object):
+ def _to_bits (cls,f,depth=32):
+ f *= (1L << depth)
+ return [(long(f) >> (depth-i)) & 1 for i in range(1,depth+1)]
+ _to_bits = classmethod(_to_bits)
+
+ def bitstring (cls,(x,y),bound=(-180,-90,180,90),depth=32):
+ x = cls._to_bits((x-bound[0])/float(bound[2]-bound[0]),depth)
+ y = cls._to_bits((y-bound[1])/float(bound[3]-bound[1]),depth)
+ bits = reduce(lambda x,y:x+list(y), zip(x,y), [])
+ return "".join(map(str,bits))
+ bitstring = classmethod(bitstring)
+
+ def __init__ (self, data, bound=(-180,-90,180,90), depth=32):
+ self.bound = bound
+ self.depth = depth
+ self.origin = bound[0:2]
+ self.size = (bound[2]-bound[0], bound[3]-bound[1])
+ if isinstance(data,tuple) or isinstance(data,list):
+ self.hash = self.bitstring(data,bound,depth)
+ else:
+ self.hash = data
+
+ def __str__ (self):
+ return self.hash
+
+ def _to_bbox (self, bits):
+ depth = len(bits)/2
+ minx = miny = 0.0
+ maxx = maxy = 1.0
+ for i in range(depth+1):
+ try:
+ minx += float(bits[i*2])/(2L<<i)
+ miny += float(bits[i*2+1])/(2L<<i)
+ except IndexError:
+ pass
+ if depth:
+ maxx = minx + 1.0/(2L<<(depth-1))
+ maxy = miny + 1.0/(2L<<(depth-1))
+ elif len(bits) == 1:
+ # degenerate case
+ maxx = min(minx + .5, 1.0)
+ minx, maxx = [self.origin[0]+x*self.size[0] for x in (minx,maxx)]
+ miny, maxy = [self.origin[1]+y*self.size[1] for y in (miny,maxy)]
+ return tuple([round(x,6) for x in minx, miny, maxx, maxy])
+
+ def bbox (self, prefix=None):
+ if not prefix: prefix=len(self.hash)
+ return self._to_bbox(self.hash[:prefix])
+
+ def point (self,prefix=None):
+ minx, miny, maxx, maxy = self.bbox(prefix)
+ return (minx+maxx)/2.0, (miny+maxy)/2.0
+
+ def union (self,other):
+ other = str(other)
+ hash = self.hash
+ for i in range(min(len(self.hash),len(other))):
+ if self.hash[i] != other[i]:
+ hash = self.hash[:i]
+ break
+ return type(self)(hash,self.bound,self.depth)
+
+ __add__ = union
+
+class Geoindex (Geostring):
+ def bitstring (cls,coord,bound=(-180,-90,180,90),depth=32):
+ bits = Geostring.bitstring(coord,bound,depth)
+ bits = bits.replace("1","2")
+ bits += "1" * (depth*2 - len(bits))
+ return bits
+ bitstring = classmethod(bitstring)
+
+ def bbox (self, prefix=None):
+ bits = self.hash.replace("1","").replace("2","1")
+ if not prefix: prefix=len(bits)
+ return self._to_bbox(bits[:prefix])
+
+ def union (self,other):
+ other = str(other)
+ hash = self.hash
+ for i in range(min(len(self.hash),len(other))):
+ if self.hash[i] != other[i]:
+ hash = self.hash[:i] + ("1" * (self.depth*2-i))
+ break
+ return type(self)(hash,self.bound,self.depth)
+
+ __add__ = union
+
+class Geohash (Geostring):
+ BASE_32 = "0123456789bcdefghjkmnpqrstuvwxyz"
+
+ def bitstring (cls,coord,bound=(-180,-90,180,90),depth=32):
+ bits = Geostring.bitstring(coord,bound,depth)
+ hash = ""
+ for i in range(0,len(bits),5):
+ m = sum([int(n)<<(4-j) for j,n in enumerate(bits[i:i+5])])
+ hash += cls.BASE_32[m]
+ return hash
+ bitstring = classmethod(bitstring)
+
+ def bbox (self,prefix=None):
+ if not prefix: prefix=len(self.hash)
+ bits = [[n>>(4-i)&1 for i in range(5)]
+ for n in map(self.BASE_32.find, self.hash[:prefix])]
+ bits = reduce(lambda x,y:x+y, bits, [])
+ return self._to_bbox(bits)
+
+if __name__ == "__main__":
+ import sys
+ if len(sys.argv) == 1:
+ import doctest
+ doctest.testmod(verbose=True)
+ elif len(sys.argv) == 2:
+ print Geohash(sys.argv[1]).bbox()
+ else:
+ print Geohash(map(float, sys.argv[1:3]))
Modified: trunk/geoserv.py
==============================================================================
--- trunk/geoserv.py (original)
+++ trunk/geoserv.py Mon Aug 25 08:38:21 2008
@@ -1,6 +1,7 @@
import wsgiref.handlers
import xml.dom.minidom
from urllib import quote
+import geohash
import traceback
import sys
@@ -22,7 +23,7 @@
bboxWest = db.FloatProperty()
bboxSouth = db.FloatProperty()
bboxNorth = db.FloatProperty()
-
+ geohash = db.StringProperty()
def getCoordinates(gp):
@@ -221,10 +222,14 @@
altitudes.append(float(alt))
description = self.request.get('description')
type = self.request.get('type',default_value='point')
- gp = Geometry(name=name,description=description,type=type,
- coordinates=coords,altitudes=altitudes,
- tags=tags, bboxEast=east, bboxWest=west,
- bboxSouth=south, bboxNorth=north,userId=userid)
+ hash = None
+ if type == 'point':
+ hash = str(geohash.Geohash((float(lat[0]), float(lng[0]))))
+ gp = Geometry(name=name, description=description, type=type,
+ coordinates=coords, altitudes=altitudes,
+ tags=tags, bboxEast=east, bboxWest=west,
+ bboxSouth=south, bboxNorth=north, userId=userid,
+ geohash=hash)
gp.put()
gps = []
Modified: trunk/index.yaml
==============================================================================
--- trunk/index.yaml (original)
+++ trunk/index.yaml Mon Aug 25 08:38:21 2008
@@ -10,6 +10,19 @@
# automatically uploaded to the admin console when you next deploy
# your application using appcfg.py.
+# Used 5 times in query history.
+- kind: Geometry
+ properties:
+ - name: type
+ - name: geohash
+
+# Used 6 times in query history.
+- kind: Geometry
+ properties:
+ - name: type
+ - name: geohash
+ direction: desc
+
# Unused in query history -- copied from input.
- kind: ReviewList
properties:
Modified: trunk/locator.py
==============================================================================
--- trunk/locator.py (original)
+++ trunk/locator.py Mon Aug 25 08:38:21 2008
@@ -1,5 +1,6 @@
import wsgiref.handlers
from math import sin, cos, radians, sqrt, atan2
+import geohash
from google.appengine.ext import webapp
@@ -36,7 +37,7 @@
def get(self):
self.locate()
- def __getParameters(self):
+ def _getParameters(self):
lat = float(self.request.get('lat'))
lon = float(self.request.get('lon'))
if self.request.get('num'):
@@ -46,19 +47,31 @@
alt = self.request.get('alt')
callback = self.request.get('callback')
return lat, lon, num, alt, callback
+
+ def _getLocationsNear(self, lat, lon, count, less_than=True):
+ hash = str(geohash.Geohash((lat, lon)))
+ query = Geometry.all()
+ query.filter('type = ', 'point')
+ if less_than:
+ query.filter('geohash < ', hash)
+ query.order('-geohash')
+ else:
+ query.filter('geohash >= ', hash)
+ query.order('geohash')
+
+ locations = []
+ for geometry in query.fetch(count):
+ location = Location(geometry)
+ location.set_distance(lat, lon)
+ locations.append(location)
+ return locations
def locate(self):
try:
- lat, lon, num, alt, callback = self.__getParameters()
- geometry_query = Geometry.all()
- geometry_query.filter('type = ', 'point')
+ lat, lon, num, alt, callback = self._getParameters()
- locations = []
- for geometry in geometry_query:
- location = Location(geometry)
- location.set_distance(lat, lon)
- locations.append(location)
- locations.sort()
+ locations = self._getLocationsNear(lat, lon, num*10, True)
+ locations += self._getLocationsNear(lat, lon, num*10, False)
geometries = []
for location in locations[:num]: