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