We are given the lengths of all sides of a polygon. We need to determine if the given polygon is convex or concave. How can this be done? What is the propery applied to determine this?
[Math] Given the sides of a polygon, determine if it is convex or concave
convex-analysisgeometrypolygons
Related Solutions
For a $n$ sided polygon, you need all the angles in order and $n-2$ consecutive side lengths in order to construct the polygon. So, you need the lengths of sides $B,C$ or $E,B$ or $D,E$ to construct your polygon.
The best way to find out the length of the remaining side is by drawing diagonals and applying triangle laws (sine or cosine rule).
Consider the (very badly drawn) pentagon. It is not drawn to scale, but you get the idea. Here are the steps you will take to find out the lengths of $D,E$.
1.Find out length of $X$ using cosine rule in $\Delta ABX$.
2.Knowing $\angle a,X,A,B$, find out $\angle e,\angle b$ using sine rule.
3.$\angle c = \angle\mbox{(between B,C)} -\angle b$. So, $\angle c$ is known.
4.Repeat the whole procedure for $\Delta CXY$. Find out $Y,\angle d, \angle f$.
5.$\angle g, \angle h$ are easily calculated now.
6.$\angle i$ is known. Apply sine rule in $\Delta DEY$ to find out $D,E$-the two unknown sides.
Rewritten on 2018-03-26.
We only need to rely on the following four statements:
The sign of the 2D analog of the vector cross product indicates whether the second vector is clockwise (positive) or counterclockwise (negative) with respect to the first vector, in a standard right-handed coordinate system.
If the 2D analog of the vector cross product is zero, the two vectors are collinear.
If the 2D analog of the vector cross product between consecutive pairs of edge vectors in a polygon has differing signs (ignoring zeroes, as if they had no sign), the polygon must be concave.
If we examine the signs of the $x$ and $y$ components of the edge vectors, (again ignoring zeroes as if they had no sign), consecutively along the polygon, as a circular list, there must be exactly two sign changes, or the polygon is concave.
Statements 1, 2 and 3 are known from basic vector algebra.
Statements 3 and 4 combined, is equivalent to calculating the angle between each pair of consecutive edges in the polygon, and verifying that they are all in the same orientation (counterclockwise or clockwise), and that the sum of the angles is 360° (so that we can correctly detect self-intersecting polygons), except that we only consider four separate directions (the four quadrants in a standard coordinate system).
In pseudocode, the testing algorithm is as follows:
Function isconvex(vertexlist):
If (the number of vertices in 'vertexlist' < 3), Then
Return FALSE
End If
Let wSign = 0 # First nonzero orientation (positive or negative)
Let xSign = 0
Let xFirstSign = 0 # Sign of first nonzero edge vector x
Let xFlips = 0 # Number of sign changes in x
Let ySign = 0
Let yFirstSign = 0 # Sign of first nonzero edge vector y
Let yFlips = 0 # Number of sign changes in y
Let curr = vertexlist[N-1] # Second-to-last vertex
Let next = vertexlist[N] # Last vertex
For v in vertexlist: # Each vertex, in order
Let prev = curr # Previous vertex
Let curr = next # Current vertex
Let next = v # Next vertex
# Previous edge vector ("before"):
Let bx = curr.x - prev.x
Let by = curr.y - prev.y
# Next edge vector ("after"):
Let ax = next.x - curr.x
Let ay = next.y - curr.y
# Calculate sign flips using the next edge vector ("after"),
# recording the first sign.
If ax > 0, Then
If xSign == 0, Then
xFirstSign = +1
Else If xSign < 0, Then
xFlips = xFlips + 1
End If
xSign = +1
Else If ax < 0, Then
If xSign == 0, Then
xFirstSign = -1
Else If xSign > 0, Then
xFlips = xFlips + 1
End If
xSign = -1
End If
If xFlips > 2, Then
Return FALSE
End If
If ay > 0, Then
If ySign == 0, Then
yFirstSign = +1
Else If ySign < 0, Then
yFlips = yFlips + 1
End If
ySign = +1
Else If ay < 0, Then
If ySign == 0, Then
yFirstSign = -1
Else If ySign > 0, Then
yFlips = yFlips + 1
End If
ySign = -1
End If
If yFlips > 2, Then
Return FALSE
End If
# Find out the orientation of this pair of edges,
# and ensure it does not differ from previous ones.
w = bx*ay - ax*by
If (wSign == 0) and (w != 0), Then
wSign = w
Else If (wSign > 0) and (w < 0), Then
Return FALSE
Else If (wSign < 0) and (w > 0), Then
Return FALSE
End If
End For
# Final/wraparound sign flips:
If (xSign != 0) and (xFirstSign != 0) and (xSign != xFirstSign), Then
xFlips = xFlips + 1
End If
If (ySign != 0) and (yFirstSign != 0) and (ySign != yFirstSign), Then
yFlips = yFlips + 1
End If
# Concave polygons have two sign flips along each axis.
If (xFlips != 2) or (yFlips != 2), Then
Return FALSE
End If
# This is a convex polygon.
Return TRUE
End Function
where != is the not-equal operator. This approach considers vertex lists with less than three vertices concave, but as this is determined by the very first If clause, you can change it to suit yourself. Degenerate polygons with at least three points, so either all the same point, or collinear, are considered convex by this approach.
Note that because this implementation does only two multiplications, and a number of additions, subtractions, and comparisons per polygon edge, it should be extremely efficient approach in most programming languages.
In a practical implementation, you might wish to replace > 0 with > eps, < 0 with < eps, x == 0 with x >= -eps && x <= eps, and x != 0 with x < -eps || x > eps, to account for rounding errors with floating-point numbers. I'd use an eps about one quarter to one sixteenth of the smallest meaningful change in either $x$ or $y$ coordinates.
Best Answer
Summary of comments: Lucian gave an example of two polygons with the same sidelengths, only one of which is convex.
Wojowu added that "If it's possible to form a polygon from given line segments, then it's possible to form a convex one from these."
Additional remark: if you know the coordinates $V_j$ of vertices, then the signs of scalar cross-products of vectors $V_jV_{j+1}$ can be used to determine convexity. I.e., the determinants such as $$ \begin{vmatrix} V_2^x-V_1^x & V_3^x-V_2^x \\ V_2^y-V_1^y & V_3^y-V_2^y \end{vmatrix} $$ must be all $\ge 0$, or all $\le 0$. (Including one with $V_n$ and $V_1$ to close the loop.)