Is a Point inside a Polygon?

Introduction

The question whether a point is contained within a polygon is a straight-forward one for us to answer visually. However, devising an algorithm that answers this question efficiently and covers most practical cases might still be a little difficult. In this article I will try to describe a short and efficient algorithm named PNPoly by W. Randolph Franklin which solves this problem.

Background

Often when dealing with 2D surfaces, map object or even simple hit tests a fast and efficient implementation is required. Algorithms that address these issues may vary in subset of polygons they are dealing with, whether they are convex, concave, with or without holes and so forth. In this article I will cover the broader case of both convex and concave polygons, but will not address the issue of holes, since it depends on the polygon representation of holes. 

The algorithm

Preliminary Check

First of all and before running this algorithm, it is advisable to perform a simple check that our target point resides outside the bounding rectangle. It's quick and straight-forward to calculate the bounding rectangle and can even be done "offline", while inserting points to the polygon. Then, the check whether our target point is outside the bounding rectangle should look like this:

if (p.x < minX || p.x > maxX || p.y < minY || p.y > maxY) {
    // We're outside the polygon!
}

where p is our target point and minX/maxX/minY/maxY are the bounding rectangle coordinates. If the above check evaluates to true we can simply return false and avoid further, more costly calculations.

Core algorithm (PNPoly)

Here is an implementation of the algorithm in C (taken from W. Randolph Franklin's website):

<a name="The C Code"></a>int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
  int i, j, c = 0;
  for (i = 0, j = nvert-1; i < nvert; j = i++) {
    if ( ((verty[i]>testy) != (verty[j]>testy)) &&
	 (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
       c = !c;
  }
  return c;
}

This is it! no additional code, a single loop that iterates over the array of points just once and toggles a flag. But what does it do?!? Let me explain. 

First of all, notice that each iteration considers two adjacent points and the target point. Then the if statement evaluates two conditions:

1. Y-value of our target point is within the range [verty[j], verty[i]).
2. X-value of our target point is below the linear line connecting the point j and i.

(If you're having problems to see this second condition, just write down the linear equation of the line, reorganize the expression a little bit and place testy as the free variable).

Every time the above two conditions are met, we toggle the flag c. So we return true if above conditions are met odd number of times and false otherwise. But what does that mean?!?

Correctness

Let's make the following observation:

a point is within a polygon if and only if its y-value is within the range of the projected polygon on the y-axis and the x-value of the point is below odd number of polygon edges. I will not prove this mathematically, but quick look at few examples will convince yourself that this is true. Notice that this observation is valid for holes too.

Now, if you would go back to the previous section which describes the two conditions you will immediately see that the algorithm is simply checking that the observation is met odd number of times.

Complexity 

Since the algorithm simply iterates through the points collection its runtime complexity is O(n), where n is the number of polygon points. 

References 

• W. Randolph Franklin (WRF), PNPOLY - Point Inclusion in Polygon Test.

Further Reading  

• Haines, Eric, "Point in Polygon Strategies," Graphics Gems IV, ed. Paul Heckbert, Academic Press, p. 24-46, 1994.
• Haines, Eric, "Point in Polygon Strategies," web-page.
• Thread at StackOverflow.com, Point in Polygon aka hit test, link.