# Envolvente convexa e orientação

Usar produtos vetoriais e uma pilha para construir a fronteira de um conjunto de pontos.

Página: https://resumos.rgo.pt/cadeiras/aed/envolvente-convexa/

Imagina pregos espetados num quadro e um elástico esticado à volta de todos eles. O elástico forma o contorno mais apertado que contém os pregos. A **envolvente convexa** é o menor conjunto convexo que contém todos os pontos.

Um conjunto é convexo quando o segmento entre quaisquer dois dos seus pontos fica dentro dele. O elástico mostra a **fronteira** desse conjunto, sem reentrâncias. Em duas dimensões, essa fronteira é um polígono quando existem pelo menos três pontos não colineares.

Com um único ponto ou só pontos colineares, a fronteira degenera, por isso fixa se queres todos os pontos da fronteira ou apenas os vértices extremos; esta página conserva apenas extremos.

## Orientação de três pontos

Para pontos $p,q,r$, calcula

$$
\operatorname{cross}(p,q,r)=(q_x-p_x)(r_y-p_y)-(q_y-p_y)(r_x-p_x).
$$

Um resultado positivo é uma curva para a esquerda, negativo para a direita e zero significa colinearidade. O módulo é duas vezes a área do triângulo. Para `(0,0)`, `(2,0)`, `(2,2)`, o resultado é 4; trocar os dois últimos pontos muda o sinal.

O produto exige espaço numérico suficiente. Se cada coordenada inteira tem módulo no máximo $10^6$, cada diferença tem módulo no máximo $2\cdot10^6$ e a diferença dos produtos cabe em `long long`. Converte os operandos para o tipo largo antes de subtrair, porque com coordenadas maiores a subtração em `int` transborda antes de chegares à multiplicação. Coordenadas reais exigem uma política para erros numéricos, que este exemplo inteiro evita.

## Graham com uma pilha

Escolhe o ponto com menor `y`, desempata pelo menor `x`, e chama-lhe pivô. Todos os outros pontos estão na mesma meia-volta em torno dele. Ordena-os pelo ângulo polar, usando o sinal do produto vetorial; pontos na mesma direção ficam do mais próximo para o mais distante. Não precisas de calcular ângulos com `atan2`.

Percorre a sequência ordenada e conserva a fronteira parcial numa pilha. Antes de inserires `q`, enquanto os dois últimos pontos da pilha e `q` não fizerem uma curva estrita para a esquerda, retira o último ponto. Insere `q`. Remover também na colinearidade elimina pontos interiores de uma aresta.

O invariante é que a pilha representa a cadeia convexa dos pontos processados, por ordem angular, com curvas estritas para a esquerda. Uma curva para a direita põe o vértice do meio no interior da nova cadeia, por isso retirá-lo conserva os extremos necessários. Na colinearidade, o mais próximo já não é um extremo da aresta. E a ordenação angular impede voltar a necessitar de um vértice retirado.

No quadrado `(0,0)`, `(2,0)`, `(2,2)`, `(0,2)`, acrescenta `(1,0)` e `(1,1)`. O ponto `(1,0)` está na fronteira, sobre a aresta de `(0,0)` para `(2,0)`, e sai quando chega `(2,0)` porque são colineares. O ponto `(1,1)` é interior e sai quando um ponto seguinte mostra que está no interior. Os quatro cantos permanecem.

Traço da pilha com pivô `(0,0)` e ordem angular `(1,0)`, `(2,0)`, `(1,1)`, `(2,2)`, `(0,2)`:

| Ponto lido | Pilha antes | Teste com os dois últimos e o novo | Pilha depois |
| --- | --- | --- | --- |
| `(1,0)` | `[(0,0)]` | pilha curta, insere | `[(0,0),(1,0)]` |
| `(2,0)` | `[(0,0),(1,0)]` | colinear, retira `(1,0)` | `[(0,0),(2,0)]` |
| `(1,1)` | `[(0,0),(2,0)]` | curva à esquerda, insere | `[(0,0),(2,0),(1,1)]` |
| `(2,2)` | `[(0,0),(2,0),(1,1)]` | `(1,1)` fica interior, retira; depois curva à esquerda | `[(0,0),(2,0),(2,2)]` |
| `(0,2)` | `[(0,0),(2,0),(2,2)]` | curva à esquerda, insere | `[(0,0),(2,0),(2,2),(0,2)]` |

Cada ponto entra uma vez e sai no máximo uma vez. Na figura, os círculos são vértices extremos e as cruzes são pontos retirados da cadeia. A tabela distingue uma saída por colinearidade de uma saída por curva para a direita.

(0,0)(2,0)(2,2)(0,2)(1,0)(1,1)Só os cantos são extremos.

**main.cpp**

```cpp
#include <algorithm>
#include <iostream>
#include <vector>
struct Ponto {
    long long x, y;
    bool operator==(const Ponto& p) const { return x == p.x && y == p.y; }
};
long long virar(Ponto p, Ponto q, Ponto r) {
    return (q.x-p.x)*(r.y-p.y)-(q.y-p.y)*(r.x-p.x);
}
long long distancia2(Ponto p, Ponto q) {
    return (q.x-p.x)*(q.x-p.x)+(q.y-p.y)*(q.y-p.y);
}
std::vector<Ponto> graham(std::vector<Ponto> a) {
    std::sort(a.begin(), a.end(), [](Ponto p, Ponto q) {
        return p.y != q.y ? p.y < q.y : p.x < q.x;
    });
    a.erase(std::unique(a.begin(), a.end()), a.end());
    if (a.size() < 3) return a;
    const Ponto p = a[0];
    std::sort(a.begin()+1, a.end(), [p](Ponto q, Ponto r) {
        const auto c = virar(p,q,r);
        return c != 0 ? c > 0 : distancia2(p,q) < distancia2(p,r);
    });
    std::vector<Ponto> h;
    for (Ponto q : a) {
        while (h.size() >= 2 && virar(h[h.size()-2], h.back(), q) <= 0) h.pop_back();
        h.push_back(q);
    }
    return h;
}
int main() {
    const auto h = graham({{0,0},{2,0},{2,2},{0,2},{1,1},{1,0},{0,0}});
    for (Ponto p : h) std::cout << p.x << ' ' << p.y << '\n';
    std::cout << "colineares: " << graham({{0,0},{1,1},{2,2}}).size() << '\n';
}
```

O exemplo exige coordenadas inteiras com módulo até $10^6$. Remove duplicados antes de ordenar por ângulo. Zero, um ou dois pontos não entram no caso geral. Se todos forem colineares, ficam os dois extremos. A saída do polígono começa no pivô e segue o sentido anti-horário, sem repetir o primeiro ponto no fim.

Ordenar custa $O(n\log n)$. Cada ponto entra na pilha uma vez e sai no máximo uma vez, pelo que a construção custa $O(n)$ apesar do `while` interior. Espaço auxiliar $O(n)$ nesta representação. A estabilidade da ordenação não é necessária porque os empates relevantes são resolvidos pela distância e os duplicados foram retirados.

O vídeo de Rodrigo Dias oferece outro apoio sobre a envolvente convexa e possíveis soluções.

[Vídeo: Convex Hull & Soluções Possíveis](https://www.youtube.com/watch?v=r0yb_AU5NmI)

[Abrir no YouTube](https://www.youtube.com/watch?v=r0yb_AU5NmI)

## Construção incremental e lista circular

Outra abordagem mantém a envolvente como uma lista duplamente ligada circular. Começa com uma envolvente válida dos pontos iniciais; um ponto interior não a altera. Para um ponto exterior, encontra as duas tangentes à fronteira, retira a cadeia de arestas visível a partir do ponto e liga o novo ponto aos extremos dessa cadeia.

Uma lista circular permite continuar ao longo da fronteira quando se passa pelo primeiro vértice. A lista dupla permite retirar nós conhecidos sem procurar o anterior. Mas achar as tangentes ainda pode exigir percorrer a fronteira, ou seja, repetir esse percurso para muitos pontos dá pior caso quadrático numa implementação linear por inserção.

Versão incremental de Edelsbrunner

Com **pontos ordenados por `x`**, para `n>=3`, sob a hipótese de pontos distintos e sem três colineares, ordena por `x` crescente, desempata por `y` decrescente e começa com três pontos em ordem anti-horária. O ponto seguinte é exterior à envolvente parcial e a pesquisa das tangentes começa no último ponto inserido, o extremo à direita. Avança em cada sentido enquanto a orientação mostrar que o vértice atual deve sair da fronteira. Liga o novo ponto às duas tangentes e elimina a cadeia entre elas.

Aqui os avanços das tangentes cobram-se aos vértices eliminados: cada ponto entra uma vez e não é reencontrado depois de sair. O trabalho total após ordenar é linear, dando $O(n\log n)$ no conjunto. Este argumento depende da ordenação e do início da pesquisa; procurar tangentes desde uma posição arbitrária em cada inserção não tem a mesma garantia. Duplicados e colinearidade precisam de tratamento adicional, por isso o programa desta página usa Graham com a política de extremos já definida.

No Graham, a ordem angular permite corrigir apenas o fim da cadeia com uma pilha. Na abordagem incremental, o novo ponto pode alterar uma cadeia em qualquer zona do polígono, justificando a lista circular. A estrutura deve refletir a ordem em que o algoritmo recebe e elimina candidatos.

Não assumes que os três primeiros pontos são distintos e não colineares sem o declarar. Para entradas gerais, trata os casos degenerados antes de construir um polígono inicial. Decidir conservar todos os pontos colineares da fronteira exige reveres tanto a ordenação dos empates como o teste de remoção.

## Pesquisar um ponto no polígono

Depois de construíres a envolvente, podes testar muitos pontos sem percorrer todas as arestas.

Os pressupostos: um polígono convexo com `h>=3` vértices extremos distintos, em ordem anti-horária `v[0],…,v[h-1]`. Os segmentos de `v[0]` para os outros vértices dividem o polígono em triângulos com direções ordenadas.

A ideia: a pergunta «a direção de `p` já passou a de `v[i]`?» responde-se com orientação, sem calcular ângulos. Primeiro localiza o setor de `p` por bisseção e depois testa-o contra a aresta exterior desse setor.

Primeiro verifica as duas direções extremas. Se `cross(v[0],v[1],p)<0` ou `cross(v[0],v[h-1],p)>0`, o ponto está fora. Se um desses produtos for zero, testa se `p` pertence ao **segmento** correspondente, incluindo os extremos: além de ser colinear, cada coordenada tem de ficar entre as coordenadas dos dois extremos. Estar na mesma reta não chega.

Nos restantes casos, começa com `l=1` e `r=h-1`. Enquanto `r-l>1`, calcula o meio `m`. Se `cross(v[0],v[m],p)>=0`, faz `l=m`; caso contrário faz `r=m`. O invariante mantém a direção de `p` entre os raios de `l` e `r`. No fim, o único triângulo candidato é `v[0],v[l],v[r]`. As duas primeiras orientações já garantem que `p` está entre os seus raios; falta testar `cross(v[l],v[r],p)>=0`, que o coloca do lado interior da aresta exterior. A igualdade inclui a fronteira.

No quadrado `[(0,0),(2,0),(2,2),(0,2)]`, para `p=(1,1)`, o meio inicial é o vértice 2 e o produto vale zero: fica `l=2,r=3`. A aresta de `(2,2)` para `(0,2)` dá produto 2, confirmando que `p` pertence ao polígono. Para `p=(3,1)`, o produto com o raio do vértice 2 é -4, ficando `l=1,r=2`; a aresta de `(2,0)` para `(2,2)` dá -2, portanto está fora. `(3,0)` fica na reta da primeira aresta, mas fora do segmento, e deve ser rejeitado no teste inicial.

Cada pesquisa custa $O(\log h)$, com orientações de custo constante, e usa espaço auxiliar $O(1)$. Para `q` consultas e `n` pontos iniciais, o total é $O(n\log n+q\log h)$. Uma envolvente vazia não contém pontos; com um ponto, testa igualdade; com dois, testa pertença ao segmento. Estes casos não passam pela pesquisa de triângulos. Mantém também os limites aritméticos de `cross`.

## Exercícios

As justificações e os programas em C++ são de autoavaliação. Compara o raciocínio com os critérios da solução.

Calcular o sentido de uma curva

Calcula cross para p=(1,1), q=(4,1), r=(2,3). Dá o sinal, o sentido da curva e a área do triângulo.

Pista

Subtrai p às outras duas coordenadas.

Solução

cross=6, ou seja, curva para a esquerda e área=|6|/2=3. Trocar q e r dá -6 e preserva a área. Os operandos têm de ser largos antes da multiplicação se as coordenadas forem grandes.

Confere a tua resposta:

*   Calculei cross=6 usando diferenças de coordenadas.
*   Associei o sinal positivo à curva para a esquerda.
*   Obtive área 3 dividindo o módulo por dois.

Erros frequentes

O produto vetorial não é a área: é o dobro da área com sinal; não uses valor absoluto para decidir orientação.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/envolvente-convexa/#orienta%C3%A7%C3%A3o-de-tr%C3%AAs-pontos)

Decidir a política da fronteira

Aplica a política de extremos apenas aos pontos (0,0), (1,0), (3,0), (3,2), (0,2), (1,1) e uma segunda cópia de (1,0). Traça a pilha, indica a envolvente e o que acontece aos pontos colineares.

Pista

Remove duplicados e ordena as direções desde o pivô (0,0).

Mais uma pista

(1,0) e (3,0) têm a mesma direção; o mais próximo chega primeiro.

Solução

A envolvente é (0,0), (3,0), (3,2), (0,2), por ordem anti-horária. A cópia de (1,0) é eliminada antes da ordenação angular; o outro (1,0) sai da pilha quando chega (3,0), por cross=0, porque o ponto intermédio não é um vértice extremo. A ordem angular após o pivô é `(1,0),(3,0),(3,2),(1,1),(0,2)`. As pilhas depois de cada ponto são `[(0,0),(1,0)]`, `[(0,0),(3,0)]`, `[(0,0),(3,0),(3,2)]`, `[(0,0),(3,0),(3,2),(1,1)]` e finalmente os quatro cantos. Ao chegar `(0,2)`, o produto com `(3,2),(1,1)` vale -3, retirando `(1,1)`; o teste seguinte vale 6 e permite inserir `(0,2)`. Cada ponto entra uma vez e sai no máximo uma vez: construção linear, precedida da ordenação `O(n log n)`.

Confere a tua resposta:

*   Obtive os quatro cantos pela ordem anti-horária.
*   Eliminei a cópia de (1,0) e retirei o ponto restante quando cross=0.
*   Tracei também a retirada do ponto interior (1,1) e justifiquei construção linear.

Erros frequentes

Se o enunciado pedir todos os pontos da fronteira, esta política precisa de ser revista; não repitas o pivô no fim sem o formato o pedir.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/envolvente-convexa/#graham-com-uma-pilha)

Distinguir um raio de um segmento

O polígono convexo tem vértices `[(0,0),(2,0),(2,2),(0,2)]` em sentido anti-horário. Pesquisa `(2,1)` e `(3,0)`, contando a fronteira como pertencente ao polígono. Mostra a decisão e explica por que orientação zero não basta para aceitar `(3,0)`.

Pista

Para (2,1), o raio até (2,2) fica à esquerda da direção do ponto.

Mais uma pista

O produto com esse raio vale -2; a aresta vertical seguinte dá zero.

Solução

Para `(2,1)`, o meio de `l=1,r=3` é 2; o produto -2 reduz `r` a 2. O triângulo candidato é 0,1,2. A orientação da aresta de `(2,0)` para `(2,2)` vale zero, pelo que aceitamos o ponto na fronteira. `(3,0)` é colinear com a primeira aresta, mas o seu x=3 excede o extremo x=2, por isso não pertence ao segmento. A pesquisa mantém tempo `O(log h)` com `h` vértices.

Confere a tua resposta:

*   Aceitei (2,1) na fronteira e rejeitei (3,0) fora do segmento.
*   Localizei o triângulo de índices 0,1,2 para (2,1).
*   Usei teste de segmento no raio extremo e mantive custo O(log h).

Erros frequentes

O teste de colinearidade identifica uma reta; o teste de limites identifica o segmento.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/envolvente-convexa/#pesquisar-um-ponto-no-pol%C3%ADgono)