Fecho Convexo Bidimensional
Relatório de Projeto
Gilberto da Silva Hemerly
Julho de 2001
Introdução
O objetivo deste projeto é a implementação de um programa que permita a observação da execução de dois algoritmos que calculam o fecho convexo bidimensional de um conjunto de pontos, o algoritmo Embrulho-para-presente e o algoritmo de Graham. O programa deve conter uma interface gráfica que permita ao usuário inserir pontos interativamente, utilizando o mouse, sem a necessidade de gerar arquivos extras. Esta interface deve também permitir que o usuário acompanhe a execução dos principais passos de cada algoritmo, sendo que o tempo de espera entre tais passos é também facilmente escolhido pelo usuário.
Para o desenvolvimento do programa, adotou-se o padrão a linguagem C++ e o padrão Win32, que permite que o programa seja executado em qualquer sistema operacional Windows de 32-bits, ou qualquer outro sistema operacional que possa emulá-lo. A programação da interface gráfica foi escrita utilizando unicamente o Graphics Device Interface (GDI) do sistema operacional, o que aumenta sua compatibilidade e velocidade de execução.
Escolheu-se os algoritmos de Graham e Embrulho-para-presente pois ambos possuem complexidade de tempo bem diferentes. Com o acompanhamento visual que o programa permite, é possível observar os passos de cada algoritmo conforme eles são executados. Além disso, o programa também exibe o tempo de execução gasto com cada algoritmo, o que permite uma diferenciação bem criteriosa dos dois algoritmos.
Ambiente de Desenvolvimento
O programa foi desenvolvido numa máquina Intel Pentium III, na linguagem C++, utilizando o ambiente de desenvolvimento Microsoft Visual C++ 6 SP4. Todo o código do programa foi escrito em ANSI C++, e a interface gráfica contém somente código Win32 nativo, o que permite que o programa seja compilado em qualquer máquina cujo sistema operacional seja o Windows (32-bit).
Estruturas de Dados
O programa foi escrito de modo que seu código seja o mais simples possível, o que facilita a compreensão do mesmo. Sempre que houve opção entre um algoritmo eficiente ou “legível”, este último foi escolhido, com exceção dos algoritmos do fecho convexo em si. Por exemplo, na pilha (stack) utilizada no algoritmo de Graham, a alocação de memória é estática. Uma alocação de memória dinâmica seria mais eficiente, mas a primeira versão contém código relativamente mais simples.
O usuário adiciona novos pontos simplesmente clicando com o botão esquerdo em qualquer parte da janela. Imediatemente aparece um ponto no local selecionado. A estrutura de dados utilizada para guardar os pontos na memória é a seguinte:
// Lista global de pontos definidos pelo usuario
#define MAX_NUM_PONTOS 500
typedef struct
{
int x;
int y;
}_tPontos;
_tPontos tPontos[MAX_NUM_PONTOS];
A matriz tPontos contém todos os pontos definidos pelo usuário. Cada algoritmo do fecho convexo determina várias arestas do fecho, que são guardadas na seguinte estrutura:
// Lista global de arestas do fecho
typedef struct
{
int x1, x2;
int y1, y2;
}_tLinhas;
_tLinhas tLinhas[MAX_NUM_PONTOS];
A matriz tLinhas tem no máximo o mesmo número de pontos, pois não é possível haver mais arestas do que pontos num fecho convexo. Com as estruturas acima, obtém-se o predicado Left:
bool Left( _tPontos a, _tPontos b, _tPontos c )
{
// Predicado LEFT
return( (a.x * b.y - a.y * b.x + a.y * c.x - a.x * c.y + b.x * c.y - c.x * b.y) > 0 );
}
Embrulho para presente
Este é um algoritmo de complexidade O( hn ), onde h é o número de arestas do fecho convexo. Este é um algoritmo output-sensitive, ou seja, sua complexidade depende da sua saída (output). O algoritmo foi implementado da seguinte maneira (as funções gráficas foram aqui removidas por simplicidade):
double EmbrulhoParaPresente()
{
// Executa o algoritmo Embrulho para Presente
int iPontoMaisBaixo, MaiorCoordY = 0;
long inicio, fim;
double tempo;
inicio = clock();
// Encontra o ponto mais "baixo"
for( int i = 0 ; i < iNumPontos ; i++ )
{
if( tPontos[i].y > MaiorCoordY )
{
MaiorCoordY = tPontos[i].y;
iPontoMaisBaixo = i;
}
}
// Encontra menor angulo polar em relacao a um ponto j
int k = ((i + 1) % iNumPontos);
i = iPontoMaisBaixo;
do
{
for( int j = 0 ; j < iNumPontos ; j++ )
{
// j deve ser diferente de i e k
if( (j == i) || (j == k) )
continue;
if( !Left( tPontos[i], tPontos[k], tPontos[j] ) )
k = j;
}
// Adiciona aresta do fecho
tLinhas[iNumLinhas].x1 = tPontos[i].x;
tLinhas[iNumLinhas].y1 = tPontos[i].y;
tLinhas[iNumLinhas].x2 = tPontos[k].x;
tLinhas[iNumLinhas].y2 = tPontos[k].y;
iNumLinhas++;
i = k;
}while( i != iPontoMaisBaixo );
fim = clock();
tempo = ((double)(fim - inicio)) / CLOCKS_PER_SEC;
return tempo;
}
Perceba que a função retorna um valor do tipo double, que é o número de segundos gasto pelo algoritmo principal.
Algoritmo de Graham
O algoritmo de Graham calcula o fecho convexo de um conjunto de pontos em duas fases: uma de pré-processamento e ordenação, e outra que é o processamento principal. A complexidade de tempo deste algoritmo é de O(n log n), onde n é o número de pontos do fecho convexo. A implementação é a seguinte:
double Graham()
{
// Executa o algoritmo de Graham
long inicio, fim;
double tempo;
inicio = clock();
// Encontra o ponto mais "baixo" e mais a esquerda
for( int i = 1 ; i < iNumPontos ; i++ )
{
if( tPontos[i].y > tPontos[0].y )
{
// Coloca o ponto mais baixo no primeiro lugar do vetor de pontos
_tPontos tmp;
tmp.x = tPontos[i].x;
tmp.y = tPontos[i].y;
tPontos[i].x = tPontos[0].x;
tPontos[i].y = tPontos[0].y;
tPontos[0].x = tmp.x;
tPontos[0].y = tmp.y;
continue;
}
if( tPontos[i].y == tPontos[0].y )
if( tPontos[i].x > tPontos[0].x )
{
// Coloca o ponto mais baixo no primeiro lugar do vetor de pontos
_tPontos tmp;
tmp.x = tPontos[i].x;
tmp.y = tPontos[i].y;
tPontos[i].x = tPontos[0].x;
tPontos[i].y = tPontos[0].y;
tPontos[0].x = tmp.x;
tPontos[0].y = tmp.y;
}
}
// Ordena os pontos usando Quicksort
qsort( &tPontos[1], iNumPontos - 1, sizeof( _tPontos ), Compara );
// Inicializa pilha com tPontos[n-1] e tPontos[0]
Pilha p;
p.Push( iNumPontos - 1 );
p.Push( 0 );
i = 1;
while( i < iNumPontos )
{
if( Left( tPontos[p.pPilhaPtr[p.iTopo - 2]], tPontos[p.pPilhaPtr[p.iTopo - 1]], tPontos[i] ) )
{
p.Push( i );
i++;
}
else
p.Pop();
}
// Analisa pilha e obtem arestas do fecho
while( p.iTopo )
{
int indice = p.Pop();
tLinhas[iNumLinhas].x1 = tPontos[indice].x;
tLinhas[iNumLinhas].y1 = tPontos[indice].y;
tLinhas[iNumLinhas].x2 = tPontos[p.pPilhaPtr[p.iTopo - 1]].x;
tLinhas[iNumLinhas].y2 = tPontos[p.pPilhaPtr[p.iTopo - 1]].y;
iNumLinhas++;
}
fim = clock();
tempo = ((double)(fim - inicio)) / CLOCKS_PER_SEC;
return tempo;
}
Operação
Para adicionar pontos ao conjunto, basta que o usuário clique com o botão do mouse em qualquer lugar da janela do programa. A qualquer momento, se o usuário desejar remover todos os pontos do conjunto, basta clicar o botão “Limpar Pontos”. Após um número qualquer de pontos, o usuário então clica ou no botão “Embrulho” ou no botão “Graham”, que executa o algoritmo correspodente. Após o término do algoritmo, o usuário pode observer as arestas do fecho convexo (desenhadas em cor vermelha) e o tempo gasto com a execução do algoritmo. O usuário pode então adicionar mais pontos ao conjunto, remover todos os pontos, ou executar qualquer um dos dois algoritmos. O usuário pode também escolher o tempo de espera entre os passos intermediários dos algoritmos que são desenhados na janela: basta pressionar as teclas de 0-9, que correspondem aos intervalos de 0, 100, 200, 300 milisegundos e assim sucessivamente.
Como a complexidade de tempo do algoritmo de Graham é “melhor” que a do Embrulho-para-presente, nota-se constantemente que este último gasta muito mais tempo de execução que o primeiro. A diferença de tempo entre eles pode reduzir sensivelmente quando o número de arestas do fecho é pequeno (três, por exemplo), pois o algoritmo Embrulho-para-presente é output-sensitive.
Bibliografia
[1] M. J. Laszlo, Computational Geometry and computer graphics in C++, Prentice Hall, Upper Saddle River, NJ, 1996.
[2] C. Petzold, Programming Windows 95, Microsoft Press, Redmond, WA, 1996.
[3] T. H. Cormen, C. E. Leiserson e R. L. Rivest, Introduction to Algorithms, The MIT Press, MacGraw-Hill, 1990