Is a Point Inside a Polygon?

July 29th 2018


Recently I needed to figure out if a point was inside a polygon. After a little bit of research I was surprised at how simple and straightforward the algorithm is. Run a line out from a given test point and determine how many times the line intersects with the individual segments of a polygon. If the number of intersections is odd then we know that the point is inside the polygon. Hover your mouse over the example above to see this.

My interest in writing this was not the algorithm itself but a particularly cool implementation of the algorithm that I found online. See the implementation below.

                
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;
}
                
            
The above code was taken from W. Randolph Franklin’s website.

That’s it. A single loop that toggles a flag on and off. But what exactly does it do? At first glance this code can seem quite complicated but it's really just running the algorithm we discussed previously. For each segment in a polygon we check for two conditions:

  1. Is our test point’s y value within the range verty[i] and verty[j]

    ((verty[i]>testy) != (verty[j]>testy))

  2. Is the test point in the left half plane of the line connecting i and j

    (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i])

If the above conditions are true for an odd number of segments then we know the point is inside the polygon.

If you hover your mouse over the example at the top of this post you will notice that the segments change color based on these conditions.

  1. A red line shows that the first condition has been satisfied.
  2. A blue segment shows that the second condition has been satisfied
  3. A green line indicates that both of the conditions have been satisfied.
Notice that if your mouse is inside the polygon then their is only ever an odd number of green lines.