Get polygons close to a lat,long in MySQL

Question

Does anyone know of a way to fetch all polygons in a MySQL db within a given distance from a point? The actual distance is not that important since it's calculated for each found polygon later, but it would be a huge optimization to just do that calculation for the polygons that are "close".

I've looked at the MBR and contains functions but the problem is that some of the polygons are not contained within a bounding box drawn around the point since they are very big, but some of their vertices are still close.

Any suggestions?

Answer 1

A slow version (without spatial indexes):

SELECT  *
FROM    mytable
WHERE   MBRIntersects(mypolygon, LineString(Point(@X - @distance, @Y - @distance), Point(@X + @distance, @Y + @distance))

To make use of the spatial indexes, you need to denormalize your table so that each polygon vertex is stored in its own record.

Then create the SPATIAL INDEX on the field which contains the coordinates of the vertices and just issue this query:

SELECT  DISTINCT polygon_id
FROM    vertices
WHERE   MBRContains(vertex, LineString(Point(@X - @distance, @Y - @distance), Point(@X + @distance, @Y + @distance))

The things will be much more easy if you store UTM coordinates in your database rather than latitude and longitude.

Answer 2

I don't think there's a single answer to this. It's generally a question of how to organize your data so that it makes use of the spacial locality inherent to your problem.

The first idea that pops into my head would be to use a grid, assign each point to a square, and check select the square the point is in, and those around it. If we're talking infinite grids, then use a hash-value of the square, this would give you more points than needed (where you have collisions), but will still reduce the amount by a bunch. Of course this isn't immediately applicable to polygons, it's just a brainstorm. A possible approach that might yield too many collisions would be to OR all hashed values together and select all entries where the hashes ANDed with that value is non-zero (not sure if this is possible in MySQL), you might want to use a large amount of bits though.

The problem with this approach is, assuming we're talking spherical coordinates (lat, long generally does) are the singularities, as the grid 'squares' grow narrower as you approach the poles. The easy approach to this is... don't put any points close to the poles... :)