Fecho convexo 2D

O fecho convexo de um conjunto de pontos em duas dimensões é definido como o menor polígono convexo que contém todos os pontos. Cada ponto do conjunto ou é um vértice desse polígono (o fecho) ou está no seu interior. A figura apresenta o fecho convexo de um conjunto de 10 pontos no plano. Apresentamos aqui alguns algoritmos para computar o fecho convexo de um conjunto de pontos no plano.


Algoritmo Incremental

Um primeiro algoritmo para o cálculo do fecho convexo de um conjunto de pontos é o algoritmo incremental. Algoritmos incrementais resolvem um dado problema para um subconjunto e, passo a passo, calculam a solução inserindo novos elementos do conjunto inicial.

No caso do fecho convexo de um conjunto de n pontos, o algoritmo calcula o fecho convexo para n-1 pontos e compõe esse resultado com o novo ponto. Basta decidir se o novo ponto está dentro ou fora do fecho convexo atual. Se estiver dentro, é um ponto interno ao fecho e não é preciso atualizar nada. Se estiver fora, então é necessário "consertar" o fecho atual de forma a incluí-lo entre os vértices. Nesse processo, pode acontecer de algum(s) dos antigos vértices deixar de ser um vértice passando a ser mais um ponto interior.

Utilizamos as primitivas Esquerda-Direita para saber a posição de um dado ponto em relação a um lado do fecho convexo atual. A idéia é simplificada se assumirmos que o polígono tem a seqüência de seus vértices orientada em um sentido (anti-horário, por exemplo). Assim, basta verificar se um novo ponto está a esquerda (se o sentido adotado for anti-horário) de todos os lados do fecho. Se isso for verdade, então trata-se de um ponto interno ao fecho, senão é um ponto externo que será colocado como um vértice.

Analisando a sua complexidade, podemos gastar tempo O(logn) para decidir se o novo ponto está dentro ou fora do fecho convexo dos n-1 pontos anteriores (para maiores detalhes consulte o tópico "Posição de um ponto em relação a um polígono"). Em seguida temos que "consertar" o fecho anterior com o novo ponto, o que pode levar-nos a mexer em (n-1)-1 arestas do fecho anterior (as arestas que "enxergam" o novo ponto). Portanto, esse passo gasta tempo O(n). Assim, a complexidade da inserção de um ponto é dominada pelo segundo passo, levando tempo O(n) para ser executado. Como vamos executar esse passo n vezes, então a complexidade total do algoritmo é O(n2).

Algoritmo do Embrulho

Outro algoritmo que nos dá o fecho convexo é o algoritmo do Embrulho. Inicialmente, determine o ponto P do conjunto com menor coordenada y. Em seguida encontre o ponto Q, dentre os que outros pontos, com menor ângulo em relação a P e a linha horizontal. Esse é um ponto que certamente é vértice do fecho convexo, e mais, a aresta PQ pertence ao fecho convexo. A partir daí, basta encontrar o próximo ponto com menor ângulo em relação a aresta PQ, e assim por diante. A execução termina quando o ponto P inicial é encontrado novamente.

O número de operações primitivas executadas por esse algoritmo é O(n*k), onde n é o número de vértices no conjunto e k é o número de vértices no fecho convexo. No pior caso, k pode ser igual a n, resultando em um algoritmo que executa em tempo quadrático.

O nome do algoritmo vem da idéia por trás dele. Imagine que cada ponto é uma estaca pregada no chão. Encontramos a estaca do conjunto que está mais ao sul e amarramos nela um barbante. Agora vamos desenrolando o barbante até bater na próxima estaca do fecho, e assim por diante, parecendo que estamos embrulhando o conjunto de pontos com o barbante.

QuickHull

O QuickHull é um algoritmo que calcula o fecho convexo de pontos num plano, com complexidade média O(n*logn), tornando-se um equivalente geométrico do algoritmo de ordenação QuickSort. Ele divide o plano em 5 regiões, utilizando-se dos pontos mais extremos (isto é, pontos com menor e maior coordenada x e maior e menor coordenada y) do conjunto. A região interna a este quadrilátero é desprezada, pois obviamente não fará parte do fecho convexo dos pontos (são todos pontos interiores).

A seguir aplica-se a cada uma das regiões restantes um algoritmo recursivo, que calcula o ponto P mais distante do segmento correspondente (na primeira vez é um segmento do quadrilátero) e divide o problema local em duas partes, como se o segmento da iteracao atual fosse dividido em outros dois, tendo o ponto P em comum. A recursão é aplicada até uma parte possuir somente dois pontos, que são então conectados.

Analisando a sua complexidade, esse algoritmo é quadrático no pior caso, mas equivalentemente ao quicksort, podemos perceber sua eficiência: em exemplos com pontos aleatoriamente distribuídos, muitos pontos estarão dentro do quadrilátero inicial e serão descartados logo na primeira fase do algoritmo. Após diversos testes percebe-se que o QuickHull se iguala ao algoritmo de Graham em relacão a tempo, quando nao possui desempenho melhor. Como no Quicksort, o QuickHull possui no "caso médio" tempo O(n*logn). Aqui a primitiva utiizada continua sendo a primitiva Esquerda.


Algoritmo de Graham

O algoritmo de Graham calcula o fecho convexo de pontos num plano, com complexidade de tempo O(n*logn). Ele encontra o ponto P com menor coordenada y e então ordena os pontos restantes pelo ângulo em relação à linha horizontal que passa pelo ponto P. Agora, com ajuda de uma pilha, o algoritmo trabalha em tempo linear. Empilhamos os dois primeiros pontos e então basta percorrermos os pontos ordenados fazendo o seguinte:

Ao final temos na pilha uma lista de pontos que forma o fecho convexo dos pontos. A complexidade do algoritmo é O(n*logn) porque precisamos gastar esse tempo para ordená-los. Já o processamento após os pontos estarem ordenados é linear, nao alterando a complexidade final. O algoritmo de Graham é um algoritmo ótimo para o cálculo do fecho convexo. Aqui a primitiva pode ser considerada a operação Esquerda que verifica se um ponto está a esquerda de um vetor.

Convém ressaltar que tudo funciona desse modo obedecendo a definição de que um polígono seja definido como uma lista de vértices ordenados em um sentido. Assim, um ponto fora do polígono estará a esquerda de todas as arestas orientadas do polígono se o sentido escolhido for o sentido anti-horário. Se definirmos o polígono ordenado no sentido horário, um ponto estará fora do polígono se estiver a direita das arestas orientadas.


MergeHull

O algoritmo MergeHull é o análogo geométrico do MergeSort. Trata-se de um algoritmo Divisão-e-Conquista para obter o fecho convexo. A idéia, como em todos os algoritmos do tipo Divisão-e-Conquista, é dividir o problema ao meio, resolver recursivamente as duas metades, e "colar" as duas metades. A base da recursão é quando temos 2 ou 3 pontos.

A parte da conquista consiste em descobrir as duas arestas tangentes (superior e inferior) às duas metades. Isso pode ser feito em tempo O(n) da seguinte forma: encontre o ponto mais a direita da metade da esquerda e o ponto mais a esquerda da metade da direita, em seguida "suba" a aresta que liga esses dois pontos até que ela seja a tangente superior e a inclua no fecho (retirando as arestas interiores que estão nos subfechos). Analogamente "desça" a aresta inicial até que ela seja a tangente inferior.

A complexidade do algoritmo é O(n*logn) porque estamos sempre quebrando o problema na metade e gastando O(n) na fase da conquista. Os mais escolados em análise de algoritmos sabem que essa é a solução da recorrência que aparece na recursão: T(n) = 2*T(n/2) + O(n) que quer dizer que o tempo para resolver o problema para n pontos é o tempo de resolver dois problemas de tamanho n/2 mais o custo da fase da conquista do algoritmo.

Voltar

Para saber mais

Consulte a seguinte bibliografia:

  1. B.G. Baumgart - A Polyhedron Representation for Computer Vision
    Proc. AFIPS Natl. Comput. Conf. volume 44 (1975).
  2. M.J. Laszlo - Computational Geometry and Computer Graphics in C++
    Prentice Hall (1996).
  3. J. O'Rourke - Computational Geometry in C
    Cambridge University Press (1993).
  4. M.I. Shamos - Computational Geometry
    Yale University (1978).

Last modified: Tue Jan 18 15:52:09 EDT 2000