check if a point exists in given area containing 4 vertices

Question

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.

Answer 1

Simple enough:

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

Answer 2

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.

Answer 3

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.

Answer 4

The method proposed by D. Patrik only works for rectangles (obviously)
Under special circumstances:
The line segment crossing method is nice if you dont need to bother the computation time of actually finding out if inside or outside. If you need fast lookups and have enough memory you can always build a table with points that are either inside or outside and then do a lookup which should be faster

Answer 5

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.