Which polygon is the coordinate in?

Question

In a MySQL database, assume I have pairs of lat/lng points that create tens of thousands of polygons on a map. Given a single pair of lat/lng points, how would I find out which polygon(s) it is in?

This seems to show how to tell if a single pair of lat/lng coordinates is within a polygon: MySQL: Spatial Query to find whether a latitude/longitude point is located within a given boundary. That's great if I only need to check the lat/lng pair against one polygon, but I have a lot of polygons.

My feeling is that I cannot do this on the fly (I'm assuming the SQL query would be so large that I would exceed some limit that MySQL has in terms of number of characters). Maybe I need to loop through each polygon and test it against the lat/lng pair -- then store some sort of boolean flag to indicate whether or not the pair is within the polygon. This seems very inefficient to me.

Suggestions?

Answer 1

I assume the pairs have also a corresponding value by which to group them into polygons. If you gave each group two pairs of coordinates that escribed a "rectangle" around the polygon, you could significantly limit the search with a simple SQL comparison.

The latter computation of whether or not the point is included in the actual polygon seems not practically possible with just SQL.

That's one suggestion.

Answer 2

How fast do your polygons change? If they are reasonably static you could use an actual GIS application to make a map of your tens of thousands of polygons. Then you can do essentially a lookup of polygon id by coordinate and turn it into a O(1) problem. Sometimes the database is not the only hammer in your toolbox.

Answer 3

You can do this with one query but you first need to store your polygons as proper geometries in mysql.

Instead of having your long list of points, write a script that will take your points and make polygons.

CREATE TABLE mypolys (polyid INTEGER, g GEOMETRY);

assuming your points table has some sort of polyid, you can iterate through them and assemble your points (using code of your choice). Somewhere in your code, you'll have sql like:

INSERT INTO mypolys (polyid, g)
VALUES(pid, PolygonFromText('POLYGON((
  x1 y1,
  x2 y2,
  x3 y3,
  x4 y4
  ))')
);

once you've done that for all your polygons, querying whether a point is in a polygon(and which one) is something like this:

SELECT polyid FROM mypolys 
WHERE ST_CONTAINS(mypolys.g, Point(point_lon, point_lat))

Whereby taking advantage of the spatial indexes that the 'geometry' type will give you.