Envolvente convexa e orientação

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

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

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.

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

Convex Hull & Soluções PossíveisCarregar vídeo do YouTube

Abrir no YouTube

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.

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.