Determining whether a coordinate exists inside of a polygon

Question

Hi all,

I'm working on an open source tracking and geofence software application and am having a bit of difficulty figuring out the math for the geofencing.

I need to determine whether or not a coordinate exists inside of a polygon. However, the tricky part is that the polygon has no set number of sides. I need to be able to calculate for fifty sides or for five sides.

My research says that the easiest way is to take my point (which I'll call x) and a point outside the polygon (call it y) and determine if line ((xx, xy), (yx, yy)) intersects with the polygon's boundaries. If it intersects an odd number of times, point x must be inside the polygon.

Knowing that, however, I cannot figure out how to express this in an algorithm.. I obviously will need to loop through the various lines constructing the polygon but the check I do eludes me. Can anyone be of assistance? Please know that I'm not asking for the solution necessarily. Anything that will help me figure it out the answer is an enormous help.

Much appreciated.

Answer 1

I'll assume you're in a plane (2D).

• Calculate the slopes of each side (in some coordinate system) and the slope of the line from point X to point Y (line XY).
• For all sides where the slope does not equal the slope of XY, calculate the point of intersection.
• For each point, determine whether the point of intersection is on line segment XY and the line segment defining the side. If it is, you crossed that side. (Check the coordinates of the intersection and see if both the x and y components are included in the range of values for each line segment.)
• Count up the number of crossings, and you have your answer.

Answer 2

See here

Basically there is an approach (I think its the Jordan Curve Theorem) that counts the number of times a ray intersects the line segments making up the polygon. If the result is even then the point is outside the polygon otherwise the point lies inside the polygon.

HTH

EDIT There is another SO question that relates to this question that can be found here

Answer 3

Compute the winding number of the polygon and the point.

Answer 4

One key here is to realize that you are free to choose any point Y that you like. A really nice choice is the point (xx, -infinity). In other words, the point directly down from the point in question and infinitely far away. Now the question becomes: how many of the polygon edges cross your X-coordinate below the point in question. So only line segments that straddle the X coordinate need to be considered.

If your point is P = (x,y), and segment end points are P1 = (x1,y1) and P2 = (x2,y2) the y coordinate of the segment where it crosses x is given by sy = (x-x1)*(y2-y1)/(x2-x1) + y1

Check if sy < y (only if x1 < x < x2 or x2 < x < x1). If there are an odd number of these then P is inside.

There are subtle issues with this when one of the verticies of the polygon is at exactly the same y position as the point in question. You'll have to be careful about that case.

Answer 5

Justin,

You may also need to better define "outside the polygon" to construct a segment.

Take the min & max of all the x & y coordinates and construct a rectangle (xmin,ymin),(xmax,ymin),(xmax,ymax),(xmin,ymax). Any point outside the rectangle would definitely be outside the polygon - then continue as others have shown above. Each polygon segment and the constructed line is defined by an equation y = ax + b and, for each segment, a range xlo and xhi. Your constructed line either crosses a segment in the range or not. That is, the solution of the two simultaneous equations in the segment range either exists or not. Just count the number of solutions that exist to get the number of intersections.