Teste de convexidade de polígono

Um teste de convexidade de polígono responde a uma pergunta fundamental da geometria computacional: dado um anel ordenado de vértices cartesianos, cada ângulo interior permanece no máximo em cento e oitenta graus de modo que a forma nunca se afunde para dentro? Agrimensores que validam parcelas cadastrais, desenvolvedores de jogos que definem cascos de colisão, equipes GIS que limpam polígonos de geocerca, exportadores CAD que impõem restrições de convexidade e ferramentas de sala de aula que avaliam exercícios de polígonos simples precisam de uma resposta determinística de sim ou não sem montar uma biblioteca geométrica completa. Esta capacidade aceita uma lista ordenada de vértices, percorre o anel fechado uma vez e compara o produto vetorial bidimensional de cada par de arestas consecutivas. Quando todo produto vetorial não nulo compartilha o mesmo sinal, cada virada segue o mesmo sentido e o polígono é convexo; sinais mistos indicam pelo menos um ângulo reflexo e o polígono é côncavo. Produtos vetoriais nulos marcam vértices colineares e são permitidos sem quebrar a convexidade.

Como produtos vetoriais de arestas consecutivas decidem a convexidade

Rotule os vértices ordenados V zero até V n menos um e feche o anel tratando a aresta do último vértice de volta ao primeiro como presente mesmo quando quem chama não repete o ponto inicial. Em cada vértice B com vértice anterior A e seguinte C, forme os vetores de saída de A para B e de B para C. O produto vetorial bidimensional deles é o escalar z igual a (B.x menos A.x) vezes (C.y menos B.y) menos (B.y menos A.y) vezes (C.x menos B.x).

O sinal de z é a direção da virada em B: positivo para uma virada à esquerda quando o plano se orienta com y para cima e x à direita (percurso anti-horário do contorno), negativo para uma virada à direita (percurso horário) e zero quando A, B e C são colineares.

Um polígono simples é convexo se e somente se toda virada não nula compartilha o mesmo sinal, o que significa que cada ângulo interior é no máximo cento e oitenta graus e o contorno nunca inverte o sentido de rotação. Viradas positivas e negativas misturadas provam um ângulo interior reflexo em algum ponto do anel, de modo que o polígono é côncavo.

O algoritmo é estritamente O(n) no número de vértices após um único passo de normalização que remove um duplicado final do primeiro ponto quando quem chama já fechou o anel.

Quando vale testar a convexidade

Pipelines de mapeamento e GIS usam um teste de convexidade de polígono antes de algoritmos que assumem entrada convexa — recorte contra uma janela convexa, decomposição de regiões complexas ou alimentadores de solvers que rejeitam vértices reflexos. Motores de jogos e simulação validam malhas de colisão definidas por designers para que um único afundamento não quebre depois hipóteses de eixos de separação ou GJK. Exportadores CAD e de fabricação impõem restrições de convexidade em blanks e polígonos de suporte antes de enviar geometria a um cortador.

Plataformas educacionais avaliam itens «este polígono é convexo?» com um oráculo determinístico que trata de forma coerente vértices colineares no meio da aresta em vez de confiar no olho. A validação falha não consome saldo.