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