O Fecho Convexo (Convex Hull)

Definição:

O fecho convexo de um conjunto de pontos $$P$$ é o menor polígono convexo que contém todos os pontos de $$P$$, como mostrado na figura 1. Aqui analisaremos especificamente o Convex Hull para um conjunto de pontos bidimensional. É importante, para fins de solução de vários problemas de geometria computacional, conseguirmos calcular o convex hull de um conjunto de pontos.

Observações importantes:

Seguem algumas observações importantes para conseguirmos um algoritmo que calcule o conjunto $$C$$ dos pontos no fecho convexo:

• Ao se ordenar os pontos de $$P$$ por suas abscissas, o primeiro ponto (ou seja, o mais a esquerda) estará em $$C$$, e o mesmo também será verdade para o último.
• A mesma observação vale ao se ordenar os pontos de $$P$$ pelas ordenadas.
• Ao se ordenar $$C$$ de forma anti-horária, dois pontos consecutivos $$A$$ e $$B$$, nessa ordem, em $$C$$ formarão um vetor $$\overrightarrow{AB}$$ à direita de qualquer outro vetor $$\overrightarrow{AD}$$, onde $$D$$ é um ponto de $$P$$, ou seja $$\overrightarrow{AB} \times \overrightarrow{AD} \ge 0$$

O algoritmo:

Um algoritmo subótimo em $$O(n^3)$$ pode ser visto da seguinte maneira:

1. Seja o ponto $$i$$ o próximo ponto que sabemos que está em $$C$$ (inicialmente o de abcissa mínima em $$P$$)
2. Para cada outro ponto $$j$$ em $$P$$ que não está em $$C$$, verifique o cross do vetor $$\overrightarrow{ij}$$ com todos os outros vetores $$\overrightarrow{ik}$$, sendo $$k$$ um ponto de $$P$$  diferente de $$i$$ e $$j$$.
3. Se em nenhum caso $$\overrightarrow{ij} \times \overrightarrow{ik} < 0$$, $$j$$ é o próximo ponto em $$C$$.
4. Quando $$i$$ retornar ao ponto inicial, ou encontrarmos um ponto que ja está em $$C$$, terminamos o algoritmo.

Esse algoritmo, mesmo que funcional, não é muito eficiente. O algoritmo descrito abaixo tem complexidade $$O(n log n)$$, conhecido como monotone chain:

1. Ordene os pontos por ordem crescente de abscissas, com desempate em ordenadas.
2. Para simplificar o algoritmo, iremos separar o Convex Hull em duas partes: o Upper Hull e o Lower Hull, ou seja a parte de cima da envoltória, e a parte de baixo da envoltória.
3. Para o Upper Hull:
   1. Assuma que estamos no ponto $$i$$. Iremos manter uma pilha equivalente ao prefixo dos pontos a esquerda de $$i$$.
   2. Enquanto o vetor entre $$i$$ e o penúltimo da pilha estiver a direita do vetor entre o último e o penúltimo, retiraremos o último da pilha.
   3. Adicionamos $$i$$ a pilha.
4. Calculamos o Lower Hull de maneira semelhante, paralelamente ao Upper Hull, porém ao invés de checar esquerda no segundo passo, checamos se está a direita.
5. O convex hull, ordenado no sentido anti-horário,  será o upper hull que calculamos na ordem, até seu penúltimo ponto, seguido pelo Lower Hull na ordem reversa, até o segundo ponto.

Duas observações importantes:

• O segundo algoritmo só tem complexidade $$O(n log n)$$ pois temos que ordenar os pontos, caso os pontos já estejam ordenados, ele é apenas $$O(n)$$
• Do modo mostrado, pontos colineares no fecho aparecerão. Para garantir que só haverão dois pontos por segmento do polígono, basta mudar as inequações para também removerem vetores paralelos na pilha.

Problemas:

Para praticar e fixar os algoritmos de convex hull, e para aplicarmos suas ideias recomendamos os 2 seguintes problemas:

• Macacos me Mordam (OBI P2 Fase 2 – 2015)
• Convex Hull