Fecho Convexo no Plano

Objetivo

        Visualizar graficamente a execução de ambos os algoritmos, tanto passo a passo, quanto de uma única vez, permitindo desta forma um melhor entendimento do funcionamento dos mesmos.
        Além disso, analisar a "performance" de cada um deles, ou seja, quanto tempo ( medido pelo número de
comparações feitas ) cada um deles leva para executar a mesma tarefa que é a de achar o fecho convexo planar ( por se tratar de pontos em 2D ) de um conjunto de pontos quaisquer dados.

Introdução

        Encontrar o fecho convexo de n pontos no plano quando n é muito grande, pode demorar um bom tempo, dependendo do algoritmo. Algoritmos mais "ingênuos" podem chegar a gastar O(n4) e  O(n3). Algoritmos mais rápidos, como o de Jarvis, constroem o fecho convexo de um conjunto de n pontos no plano em tempo O(nh), onde h é o número de vértices do fecho convexo que será dado como resposta - ou seja, o algoritmo é output-sensitive. O algoritmo de Graham foi o primeiro algoritmo com complexidade de tempo O(n log n) para o problema do fecho convexo planar que mais tarde foi provado como tempo ótimo para o problema.

Algoritmo Ingênuo ( Arestas-Extremas )

Este algoritmo vem de uma variação da sequinte defininição:
    Definição: O fecho convexo de um conjunto S de pontos no plano é a união de todos os triângulos determinados por pontos em S.
E do seguinte Lema:
    Lema: Um ponto v de um conjunto S é ponto não-extremo de S se e somente se v pertence a algum triângulo cujos vértices são pontos de S distintos de v.

Basicamente, percorremos todas as arestas e pra cada uma delas, perguntamos se a mesma está a esquerda ou sobre todos os outros pontos do conjunto de entrada, excetuando-se os vértices das arestas atuais. Se isso não for verdade, então a aresta não faz parte do Convexo.

Como percorremos todas as arestas ( O ( n2) ) e como para cada aresta percorremos todos os pontos, menos os próprios vértices da aresta sendo observados ( O ( n ) ) gastamos, no total, O (n3).

Algoritmo de Graham

O algoritmo de Graham constrói o fecho convexo de um conjunto de pontos em duas fases. A primeira fase consiste em um pré-processamento dos pontos de entrada de acordo com seus angulos polares ao redor um ponto inicial p0. Na segunda fase, o algoritmo utiliza o fato de os pontos estarem ordenados para iterativamente produzir a fecho convexo dos pontos.
Este algoritmo gasta tempo O(nlogn) para computar o fecho convexo. Veja a demonstração nas notas de aula do Professor Coelho.

Implementação

                    Makefile
                    const.h
                    embrulho.c
                    fecho1
                    fecho2
                    graham.c
                    rotinas.c
                    rotinas.h
                    rotinasEmbrulho.c
                    rotinasEmbrulho.h
 
            Faça o download

            Compilamos e testamos o programa na rede Linux. Para compilar digite:

                            make Graham
                            make Ingênuo

            Para rodar:

                             Graham     <ArqPontos>     1 | 2

                                  ArqPontos: Arquivo de entrada contendo os pontos
                                  1: modo normal, sem passo a passo
                                  2: modo passo a passo. Digite 'n' dentro da janela gráfica para rodar um passo da execução do programa

                             Ingênuo    <ArqPontos>     WaitTime

                                  ArqPontos: Arquivo de entrada contendo os pontos
                                  WaitTime:   Tempo de espera entre cada passo. '0' é o mais rápido possível.

Testes

 

Número de Pontos	Graham	Ingênuo
5	15	60
10	54	720
15	119	2730
20	209	6840
25	324	13800
30	464	24360
35	629	39270
40	819	59280

Como podemos observar, o algoritmo ingênuo gasta muito mais tempo ( faz muito mais comparações ) que o algoritmo de graham.
 

Bibliografia

• de Pina, J. C. - Página da disciplina de Geometria Computacional 2000
• J.O'Rourke - Computacional Geometry in C

Cambridge University Press, Cambridge, 1993, Second Edition, 1998
• R.L.Graham - An efficent algorithm for determining the convex hull of a finite planar set, Information Processing Letters 1 (1972)