5

refering to http://www.weather.gov/directives/sym/pd01008006curr.pdf, page 8, we are given an area with four vertices in geographic coordinate system(lat and long system). I want to check if a point with particular lat and long exists within that area.

Jason S
  • 184,598
  • 164
  • 608
  • 970

4 Answers4

5

The way to test whether or not a point is within an arbitrary polygon (any number of sides, concave allowed as well) is to choose a point that you know is OUTSIDE the polygon; if a line segment between the point you are testing and the point that is outside the polygon crosses an ODD number of the polygon segments, the point is within the polygon.

Paul Sonier
  • 38,903
  • 3
  • 77
  • 117
  • That's a correlary of the Jordan Curve Theorem. http://en.wikipedia.org/wiki/Jordan_curve_theorem – Jason S Jun 03 '09 at 15:55
  • @JasonS: interesting; I just learned it as "the way to test for whether a point is in an arbitrary polygon". The source I learned it from might have gotten it from that theorem, though. – Paul Sonier Jun 03 '09 at 15:57
  • Clarify whether this works on a sphere, or is relevant only on a plane (or some broader class of non-spherical surfaces). – erickson May 11 '22 at 19:56
4

This is a point-in-polygon problem on a sphere with a coordinate system, which has several subtleties that make it harder than the "regular" point-in-polygon problem in the X-Y plane:

1) what's inside and outside? (e.g. if I have a small "square" 1 miles on a side, does it enclose the 1 square mile, or the remainder of the earth's surface? This is a trivial example but for very large polygons it may be unclear which should be inside and which should be outside, unless specified explicitly)

2) are the segments of the polygons great-circle segments? If so, then those do not represent straight lines in a lat-long coordinate system unless they are meridian lines or the equator -- and you need to deal with curves rather than lines in your geometry. Spherical geometry is the way to go.

3) "edges" of the coordinate system (international date line and the poles) -- the "square" delimited by longitudes +179.9 degrees, -179.9 degrees, and latitudes +0.1degree, -0.1degree would not usually be considered to contain the point 0 N, 0 W, and would be considered to contain the point 0 N, 180 W. But if you naively check inequalities with lat/long points, you'll get the opposite answer.

So I don't have an answer but those are subtle issues to consider. (read this as "make sure you include them as test cases"!)

edit: I found the spheres package which has the method SphericalPolygon.contains that may do what you are looking for. However I have not personally used this package, and it's GPL, not LGPL, so it will "contaminate" the rest of your source if you wish to use this in a proprietary product.

jameshfisher
  • 34,029
  • 31
  • 121
  • 167
Jason S
  • 184,598
  • 164
  • 608
  • 970
  • The other issue is can the edges of the polygon cross one another. A 4 vertex polygon can be a simple solid thing or a thing composed of two triangles. – jmucchiello Jun 03 '09 at 16:10
  • If your vertices are given in order, the inside is the right side. – MSalters Jun 03 '09 at 16:11
  • well that's true as well. :) I had dismissed that situation because although it's possible, it's not sensible data from a GIS database. – Jason S Jun 03 '09 at 16:11
  • @MSalters: that requires agreement via well-known convention. (why not the left side?) But I concur, that's how GIS systems handle it & handle holes. – Jason S Jun 03 '09 at 16:12
  • Hello Jason, yes the sphere packages you suggested as reference cant be used because of GPL, can you please give some other good solution. looking forward, –  Jun 09 '09 at 11:10
1

Do you mean programmatically or mathematically? Programmatically is easy if you understand it mathematically. Basically, the vertices define lines. You just have to know which side of the lines constitutes "inside." Then, turn your vertices into equations but use less than or greater than rather than equals.

Id est, assume you have the rectangle defined by the following equations: x=1, x=3, y=1, y=3

If you want to know if (2,2) is inside that area, just evaluate each equation: x > 1, x < 3, y > 1, y < 3.

If all four are true, the point is inside the area.

D. Patrick
  • 2,894
  • 26
  • 37
  • And what if it's not a rectangle perfectly aligned with the latitude and longitude lines (ie, tilted)? – Steve Kuo Jun 03 '09 at 15:53
  • Yeah, this is a good technique for triangles, but it's not great for arbitrary polygons, because if they're concave, you can get invalid results. It works really nicely though if your polygons are convex. – Paul Sonier Jun 03 '09 at 15:55
  • I don't see how it can be concave or convex with 4 vertices and it works for more than just rectangles. I don't care how many vertices you have, all you have to do is evaluate each line and compare < or > . . . period. The trick is to know whether your point is supposed to be < or > than the line. I don't see why this is so difficult? – D. Patrick Jun 05 '09 at 16:58
  • Hello D.Patrick, you mean the code http://pietschsoft.com/post/2008/07/Virtual-Earth-Polygon-Search-Is-Point-Within-Polygon.aspx should work for areas given in below file page 7-9: http://www.weather.gov/directives/sym/pd01008006curr.pdf –  Jun 09 '09 at 11:07
-1

Simple enough:

http://pietschsoft.com/post/2008/07/Virtual-Earth-Polygon-Search-Is-Point-Within-Polygon.aspx

Jerod Venema
  • 44,124
  • 5
  • 66
  • 109
  • Hello Jvenema! will the the code suggested by you in above link work for areas given in below file page 7-9: http://www.weather.gov/directives/sym/pd01008006curr.pdf –  Jun 09 '09 at 11:14