Point in Polygon Test

Given a polygon and a point, how do you tell if the point is inside or outside the polygon?

Idea

In 2D let’s think of the polygon as dividing the whole space into two regions. The finite region inside the polygon and the infinite region outside. Imagine yourself standing at the point which we wish to classify as being inside or outside. Next, pick a direction and start walking in a straight line. As you walk, keep track of the number of times you cross an edge of the polygon. After a long while when you are certain you have left the polygon behind, maybe at infinity, take a break and consider the number of times you crossed its edges.

Every edge crossing implies that you have either left or entered the polygon so it toggles your current state of being inside or outside. An odd number of crossings means that your current state is opposite of what it was when you started while an even number of crossings means it is the same. So as you take your break at infinity far outside of the polygon you know that if the number of crossings was odd you started on the inside and if it was even you started outside.

Implementation

Now let’s convert the idea into some code. Here is what a polygon looks like:

struct Polygon
{
    vec2 *Vertices;
    int   NumVertices;
};

A polygon is a list of vertices. The edges are implied by the order of the vertices with each pair of consecutive vertices forming an edge. In this case the algorithm translates to code fairly naturally:

// This function returns true if the ray with origin o and direction d intersects a line segment
// with endpoints a and b.
bool RayLineSegmentIntersection( const vec2 &o, const vec2 &d, const vec2 &a, const vec2 &b );

bool IsInside( const vec2 &point, const Polygon &polygon )
{
    int numCrossings = 0;

    // Loop over all edges in the polygon.
    for( int i = 0; i < polygon.NumVertices; ++i )
    {
        int j = ( i + 1 ) % polygon.NumVertices;

        // Check if a ray in the positive x direction crosses the current edge.
        if( RayLineSegmentIntersection( point, vec2( 1, 0 ), polygon.Vertices[ i ], polygon.Vertices[ j ] ) )
            ++numCrossings;
    }

    // If the number of crossings is odd, the point was inside the polygon.
    return ( numCrossings % 2 ) == 1;
}

The implementation above does exactly what we described. It shoots a ray from the point in question down the x axis(the direction doesn’t matter since a polygon will completely surround us if we’re inside) and counts how many edges it intersects. Then depending on the count the point is classified.

Ray-Line Segment Intersection Test

Here is a way to test a ray against a line segment. To get this result just set the ray equal to the line segment and solve for . The ray will hit the line segment if (line segment is in front of the ray) and (the ray crosses the line segment between and ).

bool RayLineSegmentIntersection( const vec2 &o, const vec2 &d, const vec2 &a, const vec2 &b )
{
    vec2 ortho( -d.y, d.x );
    vec2 aToO( o - a );
    vec2 aToB( b - a );

    float denom = dot( aToB, ortho );

    // Here would be a good time to see if denom is zero in which case the line segment and
    // the ray are parallel.

    // The length of this cross product can also be written as abs( aToB.x * aToO.y - aToO.x * aToB.y ).
    float t1 = length( cross( aToB, aToO ) ) / denom;
    float t2 = dot( aToO, ortho ) / denom;

    return t2 >= 0 && t2 <= 1 && t1 >= 0;
}

That is all there is to it. In a future post we’re going to revisit and solve this problem using some tricks!