Previously we had shown how to check if a two dimensional point is within a convex polygon. Now let’s look at the general case, where the polygon can be either convex or non-convex. To do so, we’ll use the ray casting algorithm. Briefly, this algorithm creates a ray or line segment from a point outside of the polygon to the point in question. Counting up the number of intersections, if the count is even (or zero), then the point lies outside of the polygon. Alternatively, if the count is odd, then the point is within the polygon.

So let’s create the general function pointWithinPolygon.m, which you can download and try yourself, to check if a given point is within a polygon defined by x and y coordinates px and py. This function will utilize the previously described checkSegmentIntersection and checkPointOnSegment functions. Once again we will define the polygon in either the clockwise or counterclockwise directions without repeating the first vertex. For the polygon, let’s define the following non-convex polygon as follows:

px = [0, 1,-1,-1,2,2,3,4];
py = [0, -1,-1,1,2,4,4,1];

First, let’s initialize our function and do some error checking to ensure proper definitions for the polygon and point of interest:

function insidePoly = pointWithinPolygon(px, py, point, plotResults)

if numel(px) ~= numel(py) || numel(px) < 3
    error('Incorrectly defined Polygon');
end
if numel(point) ~= 2
    error('Incorrectly defined point');
end

Now, to generate a count of how many segment intersections occur for a given ray from outside the polygon to the point in question, we first need to generate an outside point and the ray. To ensure that the outsidePoint is not within the polygon, we will utilize the minimum values minus one along all x and y of the polygon. The ray will be defined as an array from the defined outsidePoint to the point in question.

%% Generate ray from outside polygon to the point in question.
outsidePoint = [min(px) - 1, min(py) - 1];
ray = [outsidePoint; point];

The count for segment intersection will performed by looping through each edge of the polygon and checking if the given segment and ray will intersect. The intersection check will once again use the previously described checkSegmentIntersection code. A true value indicates that the ray intersects a segment and will lead to an increment in the count.

%% Check the intersection of each segment with the ray 
count = 0;
for k = 1:numel(px)
    if k < numel(px)
        doesIntersect = checkSegmentIntersection(ray, [px(k) py(k); px(k+1) py(k+1)], false);
    else
        doesIntersect = checkSegmentIntersection(ray, [px(k) py(k); px(1) py(1)], false);
    end
    if doesIntersect
        count = count + 1;
    end
end

This code is almost perfect… Unfortunately something goes horribly wrong when the ray passes through vertices of the polygon. For example, if we want to check the point (1,1) and select the outside point from (-2,-2), we will pass through the vertices (-1,-1) and (0,0), resulting in a count of 4, and incorrectly predicting that the point is outside the polygon:

To fix this problem, we’ll check if any vertices lie on the ray (using the code provided previously in checkPointOnSegment), and if they do, rotate the outside point until no vertices intersect the ray. This part of the code will have to be performed prior to the previously posted segment intersection check.

% ensure that ray does not intersect with polygon vertices and modify the
% outside point if it does so.
checkVert = true;
while checkVert
    for k = 1:numel(px)
        onRay = checkPointOnSegment(ray, [px(k), py(k)], false);
        if onRay
            outsidePoint = outsidePoint - rand(1,2);
            ray = [outsidePoint; point];
            break
        end
        if k == numel(px)
            checkVert = false; 
        end
    end
end

Now, our code should be robust with example results provided below. Please give the pointWithinPolygon.m code a try and let us know if you have any comments!