CODEWITHSUNDEEP
searchgeolocationpolygon
Jacob Hansson
Jacob Hansson

Reputation: 159

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

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

Upvotes: 0

Views: 381

Answers (3)

dmckee --- ex-moderator kitten
dmckee --- ex-moderator kitten

Reputation: 101299

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

Upvotes: -1

Jason Cohen
Jason Cohen

Reputation: 83111

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.

Upvotes: 2

flybywire
flybywire

Reputation: 274080

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

Upvotes: 2

Related Questions