Pontos como pares x,y
| X | Y |
|---|
Calculadora de Fecho Convexo
Trace, arraste, gere e anime conjuntos de pontos enquanto o polígono convexo que os envolve é atualizado em tempo real.
Os resultados são calculados automaticamente conforme você informa os dados.
Clique na tela para adicionar pontos ou arraste os pontos existentes.
Resumo do fecho convexo
↓ Veja explicações e dicas abaixo ↓
Calculadoras relacionadas
O que é um fecho convexo?
Um fecho convexo é a menor forma convexa que contém um conjunto de pontos. Em duas dimensões, ele normalmente é um polígono cujos vértices são escolhidos entre os pontos originais. Uma forma comum de visualizá-lo é imaginar um elástico esticado ao redor de todos os pontos e deixá-lo se ajustar. Os pontos tocados pelo elástico se tornam os vértices do fecho, enquanto os demais ficam dentro do contorno ou sobre arestas que não são mantidas como vértices separados.
Uma forma é convexa quando o segmento de reta entre quaisquer dois pontos da forma permanece completamente dentro dela. Essa condição torna o fecho convexo útil: ele fornece o contorno externo mais simples de um conjunto de pontos dispersos, sem reentrâncias, buracos ou curvas para dentro.
Para um conjunto de pontos 2D, o fecho convexo responde a perguntas como:
- Quais pontos formam o contorno externo?
- Qual é o tamanho do polígono delimitado?
- Qual é a distância ao redor do contorno?
- Quantos pontos não fazem parte do fecho externo?
Nesta calculadora, as coordenadas são medidas nas unidades que você informa. O gráfico ajusta a escala e centraliza automaticamente o conjunto de pontos para manter o fecho visível; assim, um ponto como \((120,80)\) é uma coordenada dos dados, não um pixel fixo da tela.
Por que os fechos convexos são importantes
Fechos convexos são uma ferramenta básica da geometria computacional porque transformam uma nuvem de pontos em um contorno mais simples. Depois que o contorno externo é conhecido, muitas outras tarefas geométricas ficam mais fáceis.
Por exemplo, um fecho convexo pode ajudar a resumir a dispersão de dados representados em um gráfico, aproximar o contorno externo de um objeto em uma imagem, encontrar pontos extremos de um conjunto, criar testes simples de colisão ou contenção e preparar a geometria para cálculos posteriores, como distância, área ou comparação de formas.
Fechos convexos também são úteis para aprender algoritmos, pois mostram como um pequeno teste geométrico pode construir uma estrutura maior. A ideia principal não é apenas desenhar um polígono, mas decidir quais pontos formam giros válidos ao redor do exterior do conjunto.
Termos importantes
- Conjunto de pontos: a coleção de pontos informados, geralmente escrita como pares de coordenadas, por exemplo \((x,y)\).
- Polígono convexo: um polígono sem reentrâncias. Cada ângulo interno é, no máximo, \(180^\circ\).
- Fecho convexo: o menor conjunto ou polígono convexo que contém todos os pontos informados.
- Vértice do fecho: um ponto do conjunto informado que se torna um canto do fecho convexo.
- Ponto interior: nesta calculadora, um ponto informado que não é contado como vértice do fecho. Isso pode incluir pontos estritamente internos e, dependendo da disposição dos pontos, pontos colineares sobre uma aresta do fecho.
- Pontos colineares: pontos que estão sobre a mesma reta.
- Teste de orientação: um cálculo de produto vetorial que informa se três pontos formam um giro à esquerda, um giro à direita ou uma linha reta.
- Varredura de Graham: um algoritmo de fecho convexo que ordena os pontos ao redor de um pivô e usa uma pilha para remover giros que não pertencem ao fecho.
- Marcha de Jarvis: também chamada de algoritmo do embrulho de presente, percorre o exterior do conjunto escolhendo repetidamente o próximo ponto extremo.
- Cadeia monótona: um método de fecho convexo que ordena os pontos pelas coordenadas, constrói as cadeias inferior e superior e as une.
- Fórmula do cadarço: uma fórmula com coordenadas para calcular a área de um polígono.
Como funciona um fecho convexo
Um algoritmo de fecho convexo precisa separar os pontos do contorno dos pontos que ficam dentro dele. A maioria dos métodos 2D faz isso usando testes de orientação repetidos.
Para três pontos \(o\), \(a\) e \(b\), o valor da orientação é:
$$
\begin{aligned}
\operatorname{cross}(o,a,b)
&= (a_x-o_x)(b_y-o_y) \\
&\quad - (a_y-o_y)(b_x-o_x)
\end{aligned}
$$
Esse valor é o produto vetorial, semelhante a uma área orientada, dos dois vetores que vão de \(o\) a \(a\) e de \(o\) a \(b\). Em um plano cartesiano matemático padrão, o sinal informa se o giro é anti-horário, horário ou colinear. Em uma tela, a direção positiva de \(y\) aponta para baixo, então a direção visual pode parecer invertida em comparação com um gráfico de livro didático. O cálculo continua funcionando desde que o mesmo sistema de coordenadas seja usado de forma consistente.
Construindo o fecho
Algoritmos diferentes usam o teste de orientação de maneiras diferentes.
A varredura de Graham escolhe um ponto pivô, ordena os demais pontos pelo ângulo em torno desse pivô e percorre a lista ordenada. Quando o ponto mais recente criaria um giro para dentro, o algoritmo remove o ponto anterior da pilha de trabalho. A pilha restante percorre o contorno do fecho.
A marcha de Jarvis começa em um ponto extremo e “embrulha” o conjunto de pontos. A cada etapa, escolhe o próximo ponto de modo que todos os demais fiquem do mesmo lado da aresta atual. Isso pode ser intuitivo de observar porque se parece com girar uma reta ao redor do exterior do conjunto.
A cadeia monótona ordena os pontos pela coordenada \(x\) e depois pela coordenada \(y\). Ela constrói uma cadeia inferior e uma superior, removendo pontos que impedem o contorno de permanecer convexo. Em seguida, as duas cadeias são unidas para formar o fecho final.
A calculadora exibe etapas de reprodução da varredura de Graham ou da marcha de Jarvis. Os cartões de medição finais usam um fecho por cadeia monótona, portanto o algoritmo de reprodução escolhido altera a animação e a explicação das etapas, mas não os valores finais de área e perímetro.
Medindo o perímetro
Depois que os vértices do fecho são conhecidos, o perímetro é a soma das distâncias em linha reta ao redor do polígono. Se o fecho tem \(h\) vértices e o primeiro vértice é repetido depois do último para fechar o ciclo, o perímetro é:
$$
P =
\sum_{i=1}^{h}
\sqrt{(x_{i+1}-x_i)^2 + (y_{i+1}-y_i)^2}
$$
em que \((x_{h+1},y_{h+1})=(x_1,y_1)\).
Medindo a área
A área é calculada a partir dos vértices ordenados do fecho usando a fórmula do cadarço:
$$
A =
\frac{1}{2}
\left|
\sum_{i=1}^{h}(x_i y_{i+1} - x_{i+1}y_i)
\right|
$$
O valor absoluto é usado porque a área orientada muda de sinal conforme a ordem e a orientação dos vértices. A calculadora informa a magnitude da área delimitada em unidades quadradas de coordenada.
Contando os pontos que não pertencem ao fecho
A calculadora chama a quantidade restante de pontos interiores. Ela é calculada assim:
$$
N_{\text{non-hull}} = \max(0, n-h)
$$
em que \(n\) é o número total de pontos informados e \(h\) é o número de vértices do fecho. Como os pontos colineares do contorno não são mantidos como vértices separados no fecho final usado para a medição, é melhor interpretar essa quantidade como “pontos não contados como vértices do fecho”, e não sempre como “pontos estritamente dentro do polígono”.
Exemplos práticos de fechos convexos
Exemplo 1: um retângulo com um ponto interno
Suponha que os pontos informados sejam:
$$
(0,0),\ (4,0),\ (4,3),\ (0,3),\ (2,1)
$$
O ponto \((2,1)\) está dentro do retângulo formado pelos outros quatro pontos, então os vértices do fecho são:
$$
(0,0),\ (4,0),\ (4,3),\ (0,3)
$$
O perímetro é a distância ao redor do retângulo:
$$
P = 4 + 3 + 4 + 3 = 14
$$
A área é:
$$
A = 4 \times 3 = 12
$$
Assim, o conjunto tem \(5\) pontos no total, \(4\) pontos no fecho, \(1\) ponto fora do fecho, perímetro de \(14\) unidades de coordenada e área de \(12\) unidades quadradas de coordenada.
Exemplo 2: estimando a dispersão de uma nuvem de pixels
Imagine marcar várias posições de pixels ao redor de um objeto em uma imagem:
$$
(40,40),\ (160,50),\ (150,120),\ (70,150),\ (100,80),\ (115,70)
$$
Os dois pontos centrais ajudam a descrever a nuvem, mas não ampliam o contorno externo. Os vértices do fecho são:
$$
(40,40),\ (160,50),\ (150,120),\ (70,150)
$$
Usando a fórmula da distância ao redor do contorno, o perímetro é aproximadamente:
$$
P \approx 390.58\ \text{units}
$$
Usando a fórmula do cadarço, obtemos:
$$
A = 9{,}100\ \text{units}^2
$$
Isso não significa que o objeto real cubra exatamente \(9{,}100\) unidades quadradas físicas. Significa que o polígono convexo desenhado ao redor dessas coordenadas contém \(9{,}100\) unidades quadradas de coordenada.
Exemplo 3: um ponto colinear em uma aresta
Suponha que os pontos informados sejam:
$$
(0,0),\ (2,0),\ (4,0),\ (4,2),\ (0,2)
$$
O ponto \((2,0)\) está na aresta inferior, entre \((0,0)\) e \((4,0)\). Ele está no contorno do retângulo geométrico, mas não é necessário como canto. Os vértices do fecho são:
$$
(0,0),\ (4,0),\ (4,2),\ (0,2)
$$
A área é:
$$
A = 4 \times 2 = 8
$$
O perímetro é:
$$
P = 4 + 2 + 4 + 2 = 12
$$
A calculadora pode contar \((2,0)\) como um ponto fora do fecho, pois o fecho final usado para a medição remove pontos colineares do contorno. Isso não é um erro; é uma forma comum de representar um polígono convexo usando apenas os vértices necessários.
Como interpretar o resultado
Total de pontos é o número de pontos informados atualmente no conjunto.
Pontos do fecho é o número de vértices do fecho convexo calculado. Uma quantidade maior significa que mais pontos informados fazem parte do contorno externo. Uma quantidade menor significa que muitos pontos estão dentro do contorno ou sobre arestas que não são mantidas como vértices.
Perímetro é a distância ao redor do fecho, em unidades de coordenada. Ele aumenta quando os pontos externos se afastam ou quando o fecho ganha novos cantos que ampliam o contorno.
Área é o espaço delimitado pelo fecho, em unidades quadradas de coordenada. Ela mede a área do polígono convexo, não a área de cada objeto ou aglomerado visível dentro dele.
Pontos interiores são os pontos que não são contados como vértices do fecho. Nesta calculadora, é uma simples diferença entre o total de pontos e a quantidade de vértices do fecho.
Tempo de medição é o tempo local necessário para calcular o fecho final usado nos cartões de medição. Ele pode variar conforme o navegador, o dispositivo e a carga de trabalho atual. Não deve ser tratado como um teste formal de desempenho.
Etapas do algoritmo mostram a reprodução selecionada da varredura de Graham ou da marcha de Jarvis. Essas etapas são educativas: ajudam você a ver como um algoritmo chega ao contorno do fecho.
Comparação de algoritmos resume os algoritmos selecionados por complexidade e tempo local de geração das etapas. A varredura de Graham aparece com complexidade \(O(n\log n)\), enquanto a marcha de Jarvis aparece com complexidade \(O(nh)\), em que \(n\) é o número total de pontos e \(h\) é o número de pontos do fecho.
Erros e equívocos comuns
Usar menos de três pontos não colineares. Um fecho poligonal precisa de pelo menos três pontos únicos que não estejam todos em uma mesma reta. Um ponto, dois pontos, pontos duplicados ou pontos ao longo de uma única reta não conseguem delimitar uma área poligonal.
Esperar que coordenadas duplicadas contem como geometrias separadas. Repetir o mesmo ponto não amplia o fecho. Na tabela editável, linhas duplicadas são consideradas inválidas quando os valores numéricos armazenados coincidem após a normalização de zero negativo.
Confundir o gráfico exibido com um plano cartesiano de livro didático. A tela mostra \(y\) crescendo para baixo. Isso afeta a aparência dos giros, embora distâncias, magnitude da área e contenção do fecho continuem fazendo sentido no mesmo sistema de coordenadas.
Tratar unidades de coordenada como unidades do mundo real. Um perímetro de \(300\) unidades de coordenada não corresponde automaticamente a \(300\) centímetros, polegadas ou metros. Para converter em comprimento ou área física, é necessária uma escala conhecida fora da calculadora.
Esperar que todo ponto do contorno apareça como vértice do fecho. Um ponto exatamente sobre uma aresta do fecho pode ser removido porque não é necessário como canto do polígono.
Supor que a escolha da reprodução altera o fecho usado nas medições. As opções de varredura de Graham e marcha de Jarvis controlam a animação e os cartões de etapas. Os valores finais de medição são baseados no cálculo final do fecho da calculadora.
Interpretar o tempo local de forma literal demais. Um tempo em milissegundos é afetado pelo dispositivo, pelo navegador e pela carga momentânea do sistema. Ele é útil para comparação e aprendizado, não para testes rigorosos de desempenho.
Quando usar fechos convexos
Use um fecho convexo quando quiser identificar ou medir o contorno externo de um conjunto de pontos 2D. Alguns usos comuns são:
- Encontrar os pontos externos de uma dispersão ou de um conjunto de coordenadas.
- Estudar algoritmos de geometria computacional de forma visual.
- Estimar a dispersão de pixels marcados ou de coordenadas da tela.
- Comparar como diferentes conjuntos de pontos alteram a área e o perímetro.
- Criar uma forma envolvente simples antes de realizar um trabalho geométrico mais detalhado.
- Demonstrar como testes de orientação, ordenação e algoritmos baseados em pilha trabalham juntos.
Um fecho convexo é mais útil quando um envelope externo simples é suficiente. Ele é menos adequado quando você precisa de um contorno côncavo que acompanhe reentrâncias ou limites detalhados da forma.
Limitações e pontos importantes
Esta calculadora trabalha apenas com pares de coordenadas 2D. Ela não oferece suporte a coordenadas 3D, coordenadas geográficas, projeções cartográficas ou conversão de unidades físicas.
Coordenadas finitas informadas, inclusive valores negativos e valores fora da tela, são preservadas e ajustadas automaticamente no gráfico. Valores que não podem ser representados como números finitos em JavaScript são rejeitados.
A área e o perímetro finais são informados em unidades de coordenada e unidades quadradas de coordenada. Eles não são medidas do mundo real, a menos que suas coordenadas já usem uma unidade real ou que você faça uma conversão separada usando uma escala confiável.
Um fecho poligonal válido exige pelo menos três pontos únicos não colineares. Se todos os pontos forem colineares, o fecho pode descrever um segmento de reta, mas não pode delimitar uma área poligonal.
Pontos colineares do contorno não são mantidos como vértices separados no fecho final usado para a medição. Isso mantém mínima a representação do polígono, mas pode surpreender quem espera que todo ponto da aresta apareça na contagem do fecho.
A área e o perímetro normalmente são exibidos com até \(2\) casas decimais; valores diferentes de zero representáveis fora desse intervalo usam notação científica. Uma área diferente de zero pequena demais para binary64 é rotulada como não representável (diferente de zero), e magnitudes além do intervalo numérico disponível são rotuladas como não representáveis. Os tempos são exibidos com até \(3\) casas decimais. Os valores dos pontos editáveis preservam o valor numérico armazenado, e a detecção de duplicatas compara esses valores exatamente depois de normalizar o zero negativo.
Os testes de orientação escalam as três coordenadas finitas antes da multiplicação e preservam o sinal binário exato armazenado caso essa escala elimine os dois produtos. A tolerância usual é \(256\,\text{Number.EPSILON}\) vezes a escala local do produto normalizado. Pontos extremamente próximos de serem colineares podem ser tratados como colineares para fins práticos de exibição e cálculo.
Para trabalhos de engenharia, topografia, GIS, robótica, manufatura ou segurança crítica, use um sistema de coordenadas, um modelo de precisão e um fluxo de software adequados ao projeto. Esta calculadora visual é mais indicada para aprendizado e exploração rápida.
Como usar esta calculadora
- Informe as coordenadas \(X\) e \(Y\) na tabela de pontos ou clique na tela para adicionar pontos.
- Arraste os pontos na tela para reposicioná-los ou use os controles de adicionar e excluir para ajustar a tabela.
- Cole pares de coordenadas na área de importação se já tiver uma lista de pontos. Use um ponto por linha não vazia, com coordenadas separadas por vírgula, espaço ou tabulação.
- Gere um conjunto aleatório informando uma quantidade de pontos aleatórios. Quantidades abaixo de \(5\) ou acima de \(80\) são limitadas ao intervalo compatível.
- Escolha a varredura de Graham ou a marcha de Jarvis para controlar a reprodução da animação.
- Use Avançar, Reproduzir/Pausar e Redefinir para examinar as etapas do algoritmo.
- Consulte o total de pontos, os pontos do fecho, o perímetro, a área, os pontos interiores e o tempo de medição.
- Use a tabela de comparação para comparar a complexidade dos algoritmos e o tempo local de geração das etapas.
- Baixe a tela como PNG se quiser salvar a visualização atual.
Perguntas frequentes
O que é o fecho convexo de um conjunto de pontos?
O fecho convexo é a menor forma convexa que contém todos os pontos. Em 2D, ele normalmente é mostrado como um polígono cujos cantos são os pontos mais externos do conjunto informado.
Por que preciso de pelo menos três pontos não colineares?
Um polígono precisa de pelo menos três cantos, e esses cantos não podem estar todos na mesma reta. Se todos os pontos forem colineares, eles podem formar um segmento de reta, mas não uma forma com área.
Por que um ponto na aresta não é contado como ponto do fecho?
Um ponto colinear sobre uma aresta pode estar no contorno sem ser necessário como canto. O fecho final usado para medição mantém os vértices essenciais e remove os pontos colineares do contorno da contagem de vértices.
Qual é a diferença entre a varredura de Graham e a marcha de Jarvis?
A varredura de Graham ordena os pontos ao redor de um pivô e usa uma pilha para remover giros para dentro. A marcha de Jarvis percorre o exterior escolhendo repetidamente o próximo ponto do contorno. Nesta calculadora, essas escolhas afetam a explicação da reprodução, enquanto os cartões de medição finais usam o cálculo final do fecho.
O que significam \(O(n\log n)\) e \(O(nh)\)?
Eles descrevem como o tempo de execução de um algoritmo cresce quando a entrada muda. Em \(O(n\log n)\), \(n\) é o número de pontos informados. Em \(O(nh)\), \(n\) é o número de pontos informados e \(h\) é o número de vértices do fecho.
A área e o perímetro são medidas do mundo real?
Não. A calculadora informa o perímetro em unidades de coordenada e a área em unidades quadradas de coordenada. Para converter esses valores em unidades reais, suas coordenadas precisam usar uma escala conhecida, como centímetros, metros ou pixels por metro.
Fontes e referências
- Mark de Berg, Otfried Cheong, Marc van Kreveld e Mark Overmars, Computational Geometry: Algorithms and Applications, 3ª ed., Springer, especialmente os capítulos sobre fundamentos da geometria computacional e fechos convexos. Página do livro na Springer
- Franco P. Preparata e Michael Ian Shamos, Computational Geometry: An Introduction, Springer, especialmente os capítulos “Convex Hulls: Basic Algorithms” e “Convex Hulls: Extensions and Applications”. Página do livro na Springer
- Joseph O’Rourke, Computational Geometry in C, 2ª ed., Cambridge University Press, especialmente o material sobre fechos convexos e algoritmos geométricos. Prévia no Google Books
- CGAL, “2D Convex Hulls and Extreme Points”, manual do usuário, para definições de fecho convexo, vértices do fecho como pontos extremos e comparações de complexidade dos algoritmos. Documentação do CGAL
- Robert Sedgewick e Kevin Wayne, site do livro Algorithms, 4th Edition, “Convex Hull”, sobre testes de orientação, exercícios de fecho convexo e contexto de análise de algoritmos. Site do livro de algoritmos de Princeton
- Eric W. Weisstein, “Shoelace Formula”, MathWorld—A Wolfram Resource, sobre a fórmula da área de polígonos a partir das coordenadas dos vértices. MathWorld
- WHATWG, HTML Standard, “The canvas element”, sobre o sistema de coordenadas 2D padrão da tela, com origem no canto superior esquerdo, \(x\) crescendo para a direita e \(y\) crescendo para baixo. Padrão HTML