As we demonstrated in our previous post, 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.

function isConvex = checkConvex(px,py)

% Check convexity of polygon

% 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

% Posted on September 23, 2015 by Vipul Lugade

% http://matlabgeeks.com/tips-tutorials/computational-geometry/check-convexity-of-polygon/

%

% 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).

%

% Modified by Kurt Feigl 20161126

%

%% test case should return false

% checkConvex([4,3,2,1.5,-1,-1,1,4],[1,4,4,2.5,1,-1,-1,1])

%

%% remove point to make convex

% checkConvex([4,3,2,-1,-1,1,4],[1,4,4,1,-1,-1,1])

%

%% do not close should return false

% checkConvex([4,3,2,1.5,-1,-1,1],[1,4,4,2.5,1,-1,-1])

%

%% walk in reverse order should return false

% checkConvex([1,-1,-1,1.5,2,3,4],[-1,-1,1,2.5,4,4,1])

if numel(px) ~= numel(py)

error(‘mismatch in length’);

end

% initialize

isConvex = true

%% check to see if polygon is closed

if abs(px(end)-px(1)) > eps || abs(py(end)-py(1))

warning(‘closing polygon’);

px(end+1) = px(1);

py(end+1) = py(1);

end

numPoints = numel(px);

% By rule, all triangles are convex, so we only need check if the polygon

% has four or more vertices.

if numPoints 180, or making the polynomial concave.

for i = 1:numPoints-1

v1 = [dx(i), dy(i)];

v2 = [dx(i+1), dy(i+1)];

signPoly = sign(det([v1; v2]));

if signPoly < 0

isConvex = false;

return

end

end

return

This does not work for a polygon defined by px=[4,3,2,1.5,-1,-1,1,4] and py=[1,4,4,2.5,1,-1,-1,1], does it? I used copy+paste to create a matlab function using your code.

You should use

isConvex = true;

instead of

isConvex = 1;

Matlab has support for booleans, no need to use C-style int’s.