views:

99

answers:

3

I have a relational database where each entry is marked as a dot with latitude/longitude coordinates. I give the user the ability to mark an arbitrary polygon on a map, and want to return all entries that are within the polygonal shape.

What would be the best way to achieve this?

Also, it might be worth to point out that small errors are ok (ie. if there is an effective way to turn the polygon into a set of rectangles, then that is fine).

A: 

An old hack:

Count the number of times a line connecting <point far away> to <point in question> crosses any of the bounding segments of the polygon.

  • Even numbers mean the point is outside the polygon
  • Odd numbers mean it is inside the polygon
dmckee
yeah, but how do you do that in a SQL query?
Jason Cohen
I haven't a clue.
dmckee
Which is to say: if you're reduced to this, you may have to do it in your own code. In that event, Jason's idea *can* be implemented in SQL, and allows you to suck in a reduced data set...
dmckee
+2  A: 

Use spatial extensions, most databases have this. In MySql you can only use them with MyISAM tables which are not transactional.

http://dev.mysql.com/doc/refman/5.0/en/spatial-extensions.html

flybywire
Using built in support?!? That's gotta be cheating! +1
dmckee
+2  A: 

One way to quickly cut down on the number of points to consider is to compute the bounding rectangle for the polygon (i.e. just min-x, min-y, max-x, max-y of the points in the polygon), and then select for points within the bounding rectangle (i.e. where x is between min-x and max-x and same for y).

Of course not all these points are necessarily inside the polygon, but now you can hone it with code.

Jason Cohen