Determine whether a polygon is convex based on its vertices.

We have a polygon $A_1A_2\ldots A_k \subset \Bbb{R^2}$ with the coordinates:

$$A_1 = (x_1, y_1)$$ $$A_2 = (x_2, y_2)$$ $$\vdots$$ $$A_k = (x_k, y_k)$$

Is there any way to determine whether or not this polygon is convex or concave?

Rewritten on 2018-03-26.

We only need to rely on the following four statements:

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

2. If the 2D analog of the vector cross product is zero, the two vectors are collinear.

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

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

• The cross product in $n$-dimensions requires $n-1$ vectors and produces an another vector orthogonal to all its operands, so in $2$-dimensional space it operates on a single vector (rotating it by $90$ degrees). It should be mentioned that what you perform is not a cross product, but the so-called perp dot product which is the $2$-dimensional mixed product ($2$-dimensional analogue of the $3$-dimensional triple product). Jul 29 '17 at 18:03
• It is also worth to mention that this solution works for non-self-intersecting polygons only. For self-intersecting polygons see stackoverflow.com/a/45372025/2430597 Jul 29 '17 at 20:17
• @plasmacel: Rewritten for a much better algorithm. Note that this one is much more efficient than the one you linked to, because no trigonometric functions are needed (they are typically slow). Mar 26 '18 at 20:31