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