URGENT: Which Polygons Contain a Single Point

[Big G]

Hello

Looking for a bit of help.

I have a DB of encoded polygons.  I want to allow a user to add a single marker to a map and return the names of which of the polygons contain that point.  There are plenty of examples of drawing a polygon and returning the points within that polygon but that is not what i'm looking for.  Im after which polygons contain the specified point.

All the functionality is already developed to allow the user to save the point but I need help with the algorithm which will return all the names of the polygons containing it.  I don't actually need to display the polygons which contain the point just the name associated with the polygons in the DB.

Hope this makes sense.

thanks in advance.

Cheers,

Big G

[Barry Hunter]

This is a question for your server side database.

You need some sort of solution that can query the database. If by
'encoded' you mean something like the Maps encodeding system, you are
probably going to have to decode the data to run spatial queries on
it.

Perhaps you need to run a batch process, to decode the lines, and
store a bounding rectangle in the database. It trival then to find
points in those rectangles.

But this all depends on your database, and its capablities.

> --
> You received this message because you are subscribed to the Google Groups
> "Google Maps JavaScript API v3" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/google-maps-js-api-v3/-/un-nuHSYT8UJ.
> To post to this group, send email to google-map...@googlegroups.com.
> To unsubscribe from this group, send email to
> google-maps-js-a...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/google-maps-js-api-v3?hl=en.

[Big G]

I'm using MySQL and the polygons are encoded using google.maps.geometry.encoding.encodePath

I'm just wondering if there is a better way of finding which polygons contain the point rather than using foreach loop on all the polygons as eventually there could be up to 20,000 polygons in the DB.

any ideas/help would be much appreciated

[Barry Hunter]

You could reencode the lines into a MySQL spatial column
http://dev.mysql.com/doc/refman/5.0/en/spatial-extensions.html
then can directly query that. (for the most part tho, mysql just does
MBR checks with spatial indexing)

... the whole basis is you need to build some sort of 'spatial index'.
Could use the mysql functions, or your own homegrown system - like
noted in last reply.

Most spatial indexes involve duplicating the data into some easily
queryable format.

Because these probably just work on bounding rectangles -rather than
the detailed polygone, maybe you will still need to do a proper
point-in-polygone check, to be sure.

> --
> You received this message because you are subscribed to the Google Groups
> "Google Maps JavaScript API v3" group.
> To view this discussion on the web visit

> https://groups.google.com/d/msg/google-maps-js-api-v3/-/_rRXJwFwbJsJ.

[Andrew Leach]

I have that many, and I don't have spatial extensions in MySQL.

I have a table containing all the boundary points of each polygon, and
another table containing the bounds of each polygon (a rectangle). I
use this denormalised data to determine a subset of possible polygons
for the point, and then test each polygon in that subset to find the
one(s) containing the point. I don't use encoded polygons server-side,
although I do encode the polygon in the server and send that
compressed data to the client to display the polygon.

It is fast: try it at http://www.acny.org.uk/parishfinder.php .
Although the map is a Version 2 map, all the expensive processing is
server-side so that doesn't matter. Just click anywhere in England;
using Firebug or something similar will allow you to see how each
server interaction works -- it's getparish_new.php which finds the
right polygon and encodes the boundary and that's generally around
350ms, occasionally up to 750ms, which isn't bad to find and draw a
polygon.

I don't know how this would compare to upgrading to a
spatially-equipped version of MySQL. I suspect that I gain with the
denormalised bounding rectangles and lose slightly on the
point-in-polygon analysis; but to encode the boundary it's necessary
to have actual coordinates, and I don't have to decode those from
spatial data before using them. It's probably fairly similar.