Check convexity of polygon

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.

MATLAB irregular 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).

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 = numel(px);
if numPoints < 4
    isConvex = true;
    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 signs match
    if not (isequal(curr_signPoly, signPoly))
        isConvex = false;
        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 not (isequal(curr_signPoly, signPoly))
    isConvex = false;
else
    isConvex = true;
end

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

Note: The polygon we define is not closed (e.g. each point is unique, without repetition between the first vertex and the final vertex in px and py).
Given the test cases presented by Kurt Fiegl we would have the following:


%% test case should return false
% checkConvex([4,3,2,1.5,-1,-1,1],[1,4,4,2.5,1,-1,-1])
%
%% remove point (1.5, 2.5) to make convex and return true
% checkConvex([4,3,2,-1,-1,1],[1,4,4,1,-1,-1])
%
%% closing polygon returns false
% checkConvex([4,3,2,1.5,-1,-1,1,4],[1,4,4,2.5,1,-1,-1, 1])
%
%% walk in reverse order returns true
% checkConvex([1,-1,-1,2,3,4],[-1,-1,1,4,4,1])

 

5 thoughts on “Check convexity of polygon

  1. I have tested with the following dataset and it returns isConvex = true;
    However, I think it should be isConvex = false;

    [px,py] =
    4.7171 -0.0037
    3.9572 0.0095
    2.8408 0.1555
    1.4414 0.4641
    -0.1474 0.9514
    -1.8183 1.6186
    -3.4566 2.4511
    -4.9489 3.4191
    -6.1896 4.4789
    -7.0885 5.5760
    -7.5769 6.6477
    -7.6118 7.6275
    -7.1793 8.4493
    -6.2954 9.0518
    -5.0055 9.3825
    -3.3814 9.4014
    -1.5167 9.0841
    0.4787 8.4233
    2.4860 7.4303
    4.3849 6.1344
    6.0613 4.5819
    7.4145 2.8332
    8.3639 0.9600
    8.8538 -0.9588
    8.8571 -2.8418
    8.3772 -4.6092
    7.4473 -6.1880
    6.1285 -7.5152
    4.5057 -8.5422
    2.6820 -9.2367
    0.7722 -9.5842
    -1.1047 -9.5891
    -2.8333 -9.2732
    -4.3091 -8.6744
    -5.4454 -7.8437
    -6.1783 -6.8419
    -6.4713 -5.7351
    -6.3173 -4.5911
    -5.7385 -3.4741
    -4.7854 -2.4416
    -3.5327 -1.5400
    -2.0746 -0.8029
    -0.5183 -0.2484
    1.0232 0.1210
    2.4388 0.3183
    3.6264 0.3704
    4.5000 0.3157
    4.9954 0.2009
    5.0746 0.0774
    4.7280 -0.0029

  2. 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
    % https://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

  3. 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.

Leave a Reply to crepes Cancel reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.