How to check if a polygon is convex

Question

How do I check if a polygon is convex? The input can be given by:

#Por exemplo um quadrilátero, a primeira coluna é x e a segunda coluna é y.
quadrilatero = matrix(c(0,2,-7,1,4,3, 4,5), ncol = 2)

The output is TRUE or FALSE.

Answer 1

To see if it is a convex polygon, it is necessary to calculate the angles on each of the vertices of the polygon. If all angles have the same sign (positive or negative, depending on orientation), then the polygon is convex.

Instead of finding the angles, you just need to find the cross product of the segments on both sides of the angles. If the segments in point B are AB and BC, the cross-product has a value |AB| * |BC| * Sin(teta) where theta is the angle between the two segments. Since the lengths are always positive, the result is positive if the angle is positive and negative if the angle is negative.

The code below shows an algorithm implementation in R.

# Codigo (e descrição) adaptado de
# http://csharphelper.com/blog/2014/07/determine-whether-a-polygon-is-convex-in-c/
verifica_convexo <- function(polygon) {
    crossProductLength <- function(ax, ay, bx, by, cx, cy) {
        BAx = ax - bx
        BAy = ay - by
        BCx = cx - bx
        BCy = cy - by

        (BAx * BCy - BAy * BCx)
    }

    no_vertices <- nrow(polygon)

    testFor <- function(a) {
        b <- (a + 1) %% no_vertices
        c <- (b + 1) %% no_vertices
        sign(crossProductLength(polygon[a + 1,1], polygon[a + 1,2],
                                polygon[b + 1,1], polygon[b + 1,2],
                                polygon[c + 1,1], polygon[c + 1,2]))
    }

    signs <- sapply(0:(no_vertices - 1), testFor)
    convexo <- all(signs == signs[1])
}

quadrado <- matrix(c(0, 0, 0, 5, 5, 5, 5, 0), ncol = 2, byrow = TRUE)
print(quadrado)
print(verifica_convexo(quadrado))
seta <- matrix(c(0, 0, 1, 4, 2, 0, 1, 1), ncol = 2, byrow = TRUE)
print(seta)
print(verifica_convexo(seta))