IntroduçãoO projeto consiste em dois algoritmos para o problema do fecho convexo planar. Os algoritmos implementados foram: Embrulho para Presente e Graham Scan.
Os algoritmos foram implementados para funcionar com pontos colineares.Implementação
Toda implementação foi feita em C++ para o Linux.
A interface gráfica foi feita utilizando OpenGL.
O programa consiste de 4 arquivos .cpp:Faça o download do programa aqui.
- polígono.cpp: implementação de uma classe que representa um polígono. Para isso, utilizou-se uma lista duplamente ligada.
- conjunto.cpp: implementação de uma classe que representa um conjunto de pontos. Essa classe possui os algoritmos.
- pilha.cpp: uma pilha.
- conv.cpp: parte que cuida do gerenciamento da interface gráfica e interface com o usuário.
O pacote contendo o programa também possui um Makefile e um gerador de pontos aleatórios(random). Esse gerador sempre grava no arquivo conv3.in.Funcionamento
O programa pede um arquivo de entrada e um de saída. A primeira linha do arquivo de entrada contém um inteiro n (número de pontos), seguido por n linhas, cada uma contendo dois floats, que representam as coordenadas dos pontos. O arquivo de saída contém o resultado dos algoritmos, se foram executados.
É facultativo um terceiro parâmetro. Este é um inteiro que indica o número de microsegundos que o programa irá pausar a cada cálculo de área.
Comandos do programa:
Q : Quit, irá sair do programa.
C : Clear, limpa a tela e redesenha os pontos.
E : Embrulho, executa o algoritmo Embrulho para Presente.
G : Graham, executa o algoritmo Graham Scan.A cada execução de um algoritmo o programa imprime na tela o número de cálculos de área2 que foram feitos.
Resultados obtidos
Foram criados três conjuntos de pontos.
O primeiro é um conjunto onde o Embrulho para Presente apresenta o pior caso.
O segundo é um conjunto onde o Graham-Scan apresenta o pior caso do loop interno e o Embrulho para Presente apresenta o melhor caso.
O terceiro é um conjunto aleatorio de pontos.
Os resultados foram, em cálculos de área:
Embrulho para Presente Graham Scan Primeiro 2400 208 Segundo 147 231 Terceiro 432 307