Searching a database of coordinate-bound data for an arbitrary polygonal area

Question

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).

Answer 1

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

Answer 2

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.

Answer 3

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