Por que Graham e QuickHull às vezes dão listas diferentes de vértices?

Todos os pontos **extremos** estão na fronteira da envoltória convexa, mas, com muitos pontos numa **mesma reta**, algoritmos diferentes escolhem de outro modo quais deles ficam como **vértices** do polígono. Graham com o teste **≤ 0** em geral deixa só as **extremidades** do trecho colinear; o QuickHull, sem filtragem extra, pode incluir pontos **intermediários** na aresta. A **envoltória convexa** como conjunto no plano coincide; muda só a representação poligonal.

O que é a poligonal azul-clara no modo Graham?

É a **pilha** atual de candidatos a vértices da envoltória no **passo** escolhido — a envoltória parcial depois de processar o prefixo correspondente da lista ordenada. O **anel rosa** é o ponto que neste instante se considera para inclusão.

Quão estável isto é numericamente?

Usam-se **float64** comuns e produtos vetoriais. Se os pontos quase coincidem ou ficam quase alinhados, a orientação pode oscilar; ao acrescentar pontos vale um pequeno **afastamento** em relação aos vizinhos, para não criar duplicatas acidentais.

Como o QuickHull parte os pontos?

Depois de escolher **L** e **R**, os pontos **estritamente à esquerda** da reta orientada **LR** entram na cadeia **superior**, os **estritamente à direita** na **inferior**. Em cada passo escolhe-se, entre os que restam, o ponto **C** **mais afastado** da aresta atual **AB** (pelo módulo da área orientada); a recursão segue para os conjuntos do lado de fora dos triângulos **ABC**, até não restar ponto do lado externo da aresta.

Envoltória convexa

Pontos no plano: varredura de Graham com animação passo a passo ou QuickHull; comparação dos conjuntos de vértices.

Sobre o modelo

A envoltória convexa de um conjunto finito de pontos no plano é o menor polígono convexo que contém todos os pontos; equivalentemente, a interseção de todos os superconjuntos convexos. Há duas construções clássicas de ordem O(n log n). A varredura de Graham escolhe um ponto âncora (o mais baixo e, em empate no y, o mais à esquerda), ordena os demais pelo ângulo polar em relação à âncora (em empate de ângulo, pela distância) e percorre a lista mantendo uma pilha: antes de incluir o próximo ponto, desempilham-se vértices enquanto a orientação do último terno não for estritamente à esquerda no sentido anti-horário (pelo produto vetorial: removem-se os casos cross ≤ 0, ou seja, giro à direita ou terno alinhado). Os quadros registram a pilha e o ponto “em exame” para a exibição passo a passo. O QuickHull toma os extremos em x, L e R, parte o conjunto em pontos acima e abaixo da reta orientada LR e, em cada aresta, acrescenta recursivamente o ponto de maior módulo da área orientada do triângulo (via |cross|); os pontos sobre o segmento são descartados como interiores à aresta. Em colinearidades, implementações diferentes podem escolher subconjuntos distintos de vértices no mesmo lado; a interface mostra se os conjuntos de índices dos vértices de Graham e do QuickHull coincidem. Um clique no vazio acrescenta um ponto (com proteção contra coincidências quase totais); o arraste perto de um ponto o desloca; o número de pontos e a semente geram uma nuvem aleatória.

Para quem: Matemática discreta e geometria computacional: construção incremental e “dividir e conquistar”.

Conceitos-chave

envoltória convexa
varredura de Graham
QuickHull
ordenação polar
pilha monótona
orientação do terno
dividir e conquistar
colinearidade

Como funciona

A envoltória convexa é o menor polígono convexo que contém todos os pontos. Graham: ponto âncora, ordenação polar, pilha e teste de giro via cross; QuickHull: extremos em x, recursão pelo ponto mais afastado da aresta (área ∝ |cross|). Colinearidades podem dar listas diferentes de vértices com a mesma envoltória.

Perguntas frequentes

Por que Graham e QuickHull às vezes dão listas diferentes de vértices?: Todos os pontos extremos estão na fronteira da envoltória convexa, mas, com muitos pontos numa mesma reta, algoritmos diferentes escolhem de outro modo quais deles ficam como vértices do polígono. Graham com o teste ≤ 0 em geral deixa só as extremidades do trecho colinear; o QuickHull, sem filtragem extra, pode incluir pontos intermediários na aresta. A envoltória convexa como conjunto no plano coincide; muda só a representação poligonal.
O que é a poligonal azul-clara no modo Graham?: É a pilha atual de candidatos a vértices da envoltória no passo escolhido — a envoltória parcial depois de processar o prefixo correspondente da lista ordenada. O anel rosa é o ponto que neste instante se considera para inclusão.
Quão estável isto é numericamente?: Usam-se float64 comuns e produtos vetoriais. Se os pontos quase coincidem ou ficam quase alinhados, a orientação pode oscilar; ao acrescentar pontos vale um pequeno afastamento em relação aos vizinhos, para não criar duplicatas acidentais.
Como o QuickHull parte os pontos?: Depois de escolher L e R, os pontos estritamente à esquerda da reta orientada LR entram na cadeia superior, os estritamente à direita na inferior. Em cada passo escolhe-se, entre os que restam, o ponto C mais afastado da aresta atual AB (pelo módulo da área orientada); a recursão segue para os conjuntos do lado de fora dos triângulos ABC, até não restar ponto do lado externo da aresta.

Continue com temas próximos desta categoria — ou todos os 85 em «Visualização matemática».

Toda a categoria →

NovoEscola

Curvas de Bézier e de Casteljau

Abrir o simulador

Pontos de controle definem a curva de Bézier; o algoritmo de de Casteljau constrói B(t) por interpolação linear aninhada.

NovoEscola

Triangulação de Delaunay e diagrama de Voronoi

Abrir o simulador

Triangulação de Bowyer–Watson e diagrama de Voronoi dual: o clique acrescenta sítios, o arraste os desloca.

NovoEscola

Regressão linear: MQO, ridge, lasso e R²

Abrir o simulador

Pontos no plano e o modelo y = β₀ + β₁x: MQO usual, ridge (penalização L₂ na inclinação) ou lasso (penalização L₁). O deslocamento Δy no ponto de maior |x| é um valor atípico de grande alavancagem; comparam-se SSE e R².

NovoEscola

Agrupamento k-médias

Abrir o simulador

Pontos no plano, número de grupos k e centróides iniciais. Passo de Lloyd: atribuição ao centro mais próximo e deslocamento do centróide ao baricentro. A demonstração é uma mistura de gaussianas; soma dos quadrados intra-grupo.

NovoEscola

Gradiente descendente

Abrir o simulador

Curvas de nível de f(x, y) e trajetória (x, y) ← (x, y) − η∇f; tigela ou poço elíptico.

NovoEscola

Rede de duas camadas e retropropagação

Abrir o simulador

Duas características e um rótulo binário: camada oculta com tanh e saída logística. Gradiente completo da entropia cruzada binária média; mapa de calor da probabilidade e fronteira de nível 0,5 (XOR ou espirais).

Envoltória convexa

Sobre o modelo

Como funciona

Perguntas frequentes

Simuladores relacionados

Curvas de Bézier e de Casteljau

Triangulação de Delaunay e diagrama de Voronoi

Regressão linear: MQO, ridge, lasso e R²

Agrupamento k-médias

Gradiente descendente

Rede de duas camadas e retropropagação

Envoltória convexa

Sobre o modelo

Como funciona

Perguntas frequentes