Determine whether a polygon is convex based on its vertices.

Question

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?

Answer 1

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.