Hi Ben ("readyassist"... I hate the way they truncate my email address!) :-)
You're definitively right. The probelm is : What is the problem ? Problem is to find neighboor points ? Problem is to find points in a MBR ? aka Minimum Bounding Rectangle Those 2 problems are different and implies 2 different answers. First one can be approach by your smart heuristic second one implies "exact" data that could be achieved other spatial algorith such as R-tree.(IMHO) Question is : Do we have enough tools to implement some kind of ("more precise than geohash algorithm") algorithm to solve MBR with google app engine ? Kind regards, Pierre On Sep 9, 10:13 pm, "[EMAIL PROTECTED]" <[EMAIL PROTECTED]> wrote: > Sure; I don't see why you couldn't conceivably have multiple lists to > get varying distances. I just talked about having one 3x3 grid of > squares, each being 0.1 deg x 0.1 deg, but you could also have > something larger, either with more squares (5x5, 10x10), or with > larger squares (0.15 degrees each direction) > > The idea is that when you figure out what box you're in, you also want > to now what your neighboring boxes are, because if you only search in > your box, and if you're near one of the boundaries of that box (i.e. > your search point is on the southwest corner), then results from the > far end (say, the northeast corner) may be less relevant than other > results which are just over the boundary in the next box. So when you > store a point, you store its own box (B1), and you also say, "all > these boxes are neighbors (N1-Nx)", so you end up with something like > this overlaid on a map: > > [N1][N2][N3] > [N4][B1][N5] > [N6][N7][N8] > > When someone does a search, the point they are searching from is > normalized, and if it turns out that the new point is in any of those > boxes--either the originally-stored point's box or any of it's > neighbors--then that originally-stored point comes up in the query. > > There's no reason you couldn't get more creative.. > [N9] > [N1][N2][N3] > [N12][N4][B1][N5][N10] > [N6][N7][N8] > [N11] > > And so-on... > > -B > > On Sep 9, 9:23 am, Pierre <[EMAIL PROTECTED]> wrote: > > > Hi readyassist, > > > Thank you for your post. > > Trying to understant your algorithm, It seems to me that given a > > bounding box defined by to points SW and NE, your heuristic can also > > retrieve points outside the box, ? > > If I understand what you say, you defined a sort of "grid" surrounding > > each recorded points. Then, with inclusion process of lists, you can > > tell whether a grid of a point is located in the grid of another > > point ? > > > With this process you cannot deal with overlapping grids of points > > which could be "relatively" far from each other, can you ? > > > Or I might be copletely wrong also ;-) > > > Regards, > > > Pierre > > > On Sep 9, 8:58 am, "[EMAIL PROTECTED]" <[EMAIL PROTECTED]> > > wrote: > > > > I've got a better solution than geohashing. > > > > I break down the grid into sub-degree squares by truncating after the > > > first decimal point, and then when I save something that I need to > > > find on the map later, I save metadata with that point indicating the > > > surrounding grid squares. > > > > So if I have a point with long -122.123123123 and lat 35.56565, that's > > > in a grid square called -122.1x35.5, and it's surrounded as follows: > > > > [-122.2x35.6][-122.1x35.6][-122.0x35.6] > > > [-122.2x35.5][-122.1x35.5][-122.0x35.5] > > > [-122.2x35.4][-122.1x35.4][-122.0x35.4] > > > > Those are all represented in my object as a list > > > (db.StringListProperty, so you have to do the right permutations to > > > make them into strings), and because of the way lists work, if a point > > > that you're searching on is in any of the grid squares associated with > > > a saved point, that saved point will come up. > > > > To wit, if you have saved that above point, and someone comes in > > > searching on an address that corresponds to LONG -122.0857 LAT > > > 35.69999, that corresponds to grid square '-122.0x35.6', which is in > > > your upper right hand corner. Thus, if you search for something like: > > > > square = '-122.0x35.6' > > > points = (SELECT * FROM Locations WHERE gridList=:1", square) > > > > ...you'll find that the original point we saved above will return. > > > > It's all about metadata. Don't think in terms of inequalities and > > > boundary conditions, think in terms of inclusive ranges. > > > > Best, > > > > On Sep 3, 1:23 pm, Pierre <[EMAIL PROTECTED]> wrote: > > > > > Hi, > > > > > I need to find points (lat/lng) within a certain bounding box. To do > > > > so, I triedGeohashpython implementation (http://mappinghacks.com/ > > > > code/geohash.py.txt). > > > > > Problem's data is : > > > > - I have 2 points (South west SW corner / North east NE corner) > > > > describing a geographic Bounding box > > > > - I have a model (let's call it 'Poi') having a field "geohash" of > > > > type Db.StringProperty + Lat and Lng field (Float) > > > > > Question is : How on earth (lol :-) ) can I find all Poi within my > > > > bounding box ? > > > > > I've already tried something like : > > > > > CreateGeohashfor SW, createGeohashfor NE and do something like : > > > > > "SELECT * FROM Poi WHEREgeohash>:1 andgeohash<= > > > > :2,geohash(SW),geohash(NE)" > > > > > Also tried with geoindex, at different depth but all this fails and > > > > still give points not located within Bounding box. > > > > Also tried like describe in "http://labs.metacarta.com/blog/27.entry/ > > > > geographic-queries-on-google-app-engine/" to create a small > > > > surrounding box for each Poi and then create ageohashfor this > > > > specific bounding box to be in between my SW->NE bounding box.... > > > > > Nothing is working even with "not worst case" (I mean equatorial > > > > problem...) case/ > > > > > Any help will be greatly appreciated. > > > > > Thanks all, > > > > > Pierre --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Google App Engine" group. To post to this group, send email to google-appengine@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/google-appengine?hl=en -~----------~----~----~----~------~----~------~--~---