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 = 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])
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
v1 = [px(1) – px(end), py(1) – py(end)];
should be
v1 = [px(end) – px(1), py(end) – py(1)];
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
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.