Point in Polygon

Ray Casting Algorithm

There is a polygon with vertices:

\[ a=(20,20), b=(80,20), c=(50,50), d=(80,80), e=(20,80) \]

and we have to check if a point \(\textbf{p}\) is within the perimeter of that polygon:

\[ \textbf{p}=(55, 35) \]

We can see that the point is inside, but how to test it numerically ?

Draw a horizontal line from the point, and if this line intersects the polygon an odd number of times, the point is inside; otherwise is outside de polygon.

We do this by testing for each side whether the line crosses it or not.

For example the side \(\overline{bc}\):

\[ \begin{align} &b_x = 80, b_y = 20\\ &c_x = 50, c_y = 50\\ &\textbf{p}_x = 55, \textbf{p}_y = 35 \end{align} \]

Two conditions must be met for the intersection to occur:

The point must be between the endpoints of the side, in the vertical axis:

\[ \begin{align} &(\textbf{p}_y < b_y) \neq (\textbf{p}_y < c_y)\\\\ &(35 < 20) \neq (35 < 50) \end{align} \]

If so, the \(x\) coordinate of the point must be less than the \(x\) coordinate of the intersection point.

This intersection point is derived from the two-point form equation of a line:

\[ \begin{align} &(x_2 - x_1) (y - y_1) - (y_2 - y_1) (x - x_1) = 0\\\\ &x = \frac{(x_2 - x_1) (y - y_1)}{(y_2 - y_1)} + x_1 \end{align} \]

We do this with each side. If we end up with an odd number of intersections, then the point is within the polygon.

For example the side \(\overline{ea}\) meets the first condition:

But not the second one:

What about a point with zero intersections ?:

A point with zero intersections is outside, because zero is an even number.

JS code:

function ray_casting(point, polygon){
    var n=polygon.length,
        is_in=false,
        x=point[0],
        y=point[1],
        x1,x2,y1,y2;

    for(var i=0; i < n-1; ++i){
        x1=polygon[i][0];
        x2=polygon[i+1][0];
        y1=polygon[i][1];
        y2=polygon[i+1][1];

        if(y < y1 != y < y2 && x < (x2-x1) * (y-y1) / (y2-y1) + x1){
            is_in=!is_in;
        }
    }

    return is_in;
}

Watch the video: