3

Como verifico se um polígono é convexo? O input pode ser dado por:

#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)

O output é TRUE ou FALSE.

1 Resposta 1

4

Para ver se é um polígono convexo, é preciso calcular os ângulos em cada um dos vértices do polígono. Se todos os ângulos têm o mesmo sinal (positivo ou negativo, dependendo da orientação), então o polígono é convexo.

Em vez de encontrar os ângulos, você precisa apenas encontrar o produto cruzado dos segmentos em ambos os lados dos ângulos. Se os segmentos no ponto B são AB e BC, o produto cruzado tem um valor |AB| * |BC| * Sin(teta) onde teta é o ângulo entre os dois segmentos. Uma vez que os comprimentos são sempre positivos, o resultado é positivo se o ângulo é positivo e negativo se o ângulo for negativo.

O código abaixo mostra uma implementação do algoritmo em 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))

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .