Check convexity of polygon - SPIRO THE TECH GURU

www.spiroprojects.com
We can generate polygons by tracing a circle around a given center and placing vertices at randomly spaced angles and radii.

While on visual inspection it should be clear whether some polygons are convex or concave, we want to find a way to check for this property mathematically. We will do so by checking the direction that each internal angle takes around the polygon, as by definition, convex polygons will have all internal angles of less than 180 degrees (additional rules include the fact that all diagonals are contained within the polygon and a line drawn through a convex polygon in any direction will intersect at exactly two points).

By rule, all triangles are convex, so we only need check if the polygon has four or more vertices.

function isConvex = checkConvex(px,py)
% Given a set of points determine if they form a convex polygon
% Inputs 
%  px, py: x and y coordinates of the vertices for a given polygon

% Output 
%  isConvex: 1 or 0 for polygon being convex or concave

numPoints = size(px,1);
if numPoints < 4
    isConvex = 1;
    return
end

We will now check each internal angle, by determining the sign of the angle created by the two vectors intersecting at each vertex. This can be done by taking the determinant of the two vectors. When taking the determinant, the resulting sign (+ or -) signifies the oriented area of the parallelogram that would be generated by the two vectors (v1 and v2). First determine the sign for the initial two vectors of the polynomial at the first vertex.

% can determine if the polygon is convex based on the direction the angles
% turn.  If all angles are the same direction, it is convex.
v1 = [px(1) - px(end), py(1) - py(end)];
v2 = [px(2) - px(1), py(2) - py(1)];
signPoly = sign(det([v1; v2]));

We use the MATLAB built in function sign to see if the resultant determinant (ad – bc) is negative or positive. Now we check each subsequent vertex, with any vertex having a different sign for the oriented area signifying a vertex with an internal angle of > 180, or making the polynomial concave.

% check subsequent vertices
for k = 2:numPoints-1
    v1 = v2;
    v2 = [px(k+1) - px(k), py(k+1) - py(k)]; 
    curr_signPoly = sign(det([v1; v2]));
    % check that the sign matches the first vectors or is 0
    if curr_signPoly * signPoly < 0
        isConvex = 0;
        return
    end
end
% check the last vectors
v1 = v2;
v2 = [px(1) - px(end), py(1) - py(end)];
curr_signPoly = sign(det([v1; v2]));
if curr_signPoly * signPoly < 0
    isConvex = 0;
else
    isConvex = 1;
end

If the function returns a 0, the polygon you check is concave, otherwise (isConvex = 1) the polygon convex.