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
-~----------~----~----~----~------~----~------~--~---
