|
|
|
|
|
 |
|
|
|
 |
|
|
|
 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Nesta página você poderá acompanhar como foi o desenvolvimento do projeto que escolhemos:
Problema do Par mais Próximo no R²
Como este projeto foi feito em C, h� alguns requisitos b�sicos para o funcionamento:
- GLUT/Mesa
- GTK e GDK
- Biblioteca GTK GLArea Arquivo para instala��o
� poss�vel entrar com os pontos do conjunto no formato arquivo texto, ou
atrav�s de cliques do mouse.
O formato do arquivo texto deve ser:
3 --------------------> N�mero de pontos do conjunto
5.36 -5----------------> Coordenadas (x,y) dos pontos, um por linha
0 -1.2
1 2.04
Maiores informa��es podem ser encontradas no menu Ajuda do programa execut�vel.
Relatório do desenvolvimento:
O objetivo desse relat�rio � descrever as tomadas de decis�es que tivemos
que fazer durante o desenvolvimento do projeto de Geometria Computacional,
intitulado Problema do Par mais Pr�ximo, realizado no ano de 2000.
(Data de cria��o [in�cio] do projeto: 23/05/2000)
23/05/2000:
Ao pensarmos melhor no problema e na interface que teria que ser feita
com o usu�rio, decidimos alterar a biblioteca que usar�amos. Ao inv�s de se
utilizar a Mesa/GLUT, precisaremos usar a GTK, pois esta cont�m intrinsicamente
fun��es usadas para controle de janelas, bot�es e caixas de di�logo.
Quanto ao problema de desenho, vimos que todas as fun��es que
usar�amos no Mesa, possuem equivalentes no GTK, n�o alterando muito o que
tinhamos planejado. Pelo que vimos, h� uma biblioteca chamada GDK, que pode
ser usada em conjunto com o GTK, usada para desenhos.
20/06/2000:
Retomamos o projeto, ainda pensando nas estruturas que teremos que
utilizar para desenvolvermos o Problema do Par mais Pr�ximo.
Precisaremos ter:
Estrutura para guardar os n pontos do R� :
Lista duplamente ligada: P ={0,...,n-1}
(D1,p1,p2) = ParProximo(P):
Se #elementos <= 3, use for�a bruta e devolva (Dmin,pmin1,pmin2).
Caso contr�rio: /* Divis�o, conquista e combina��o */
2 PR�-PROCESSAMENTOS:
- Ordena��o dos pontos segundo as x-coordenadas (em caso de
empate, use como decis�o a coordenada y). [O(n.logn)]
Coloque o resultado em um vetor X.
- Ordena��o dos pontos segundo as y-coordenadas (em caso de
empate, use como decis�o a coordenada x). [O(n.logn)]
Coloque o resultado em um vetor Y.
ALGORITMO de Divis�o e Conquista [O(n)]
Dividir:
* Pegue o elemento do meio em X e considere-o como mediana do
conjunto, chame-o de med.
* Tome Pl o conjunto {0,...,med} de pontos.
* Tome Pr o conjunto {med+1,...,n-1} de pontos.
Conquistar: Resolver recursivamente para os dois conjuntos.
* (Dl,pl1,pl2) = ParProximo(Pl).
* (Dr,pr1,pr2) = ParProximo(Pr).
* onde: Dr = dist(pr1, pr2);
* Dl = dist(pl1, pl2);
Combinar:
* D = min(Dl, Dr);
* Calcula-se todos os pontos de Pl a uma dist. <= D da reta
vertical dada pela mediana em X (reta: x = med). => Conj. Pl'
* Calcula-se todos os pontos de Pr a uma dist. <= D da reta
vertical dada pela mediana em X (reta: x = med). => Conj. Pr'.
* Para cada ponto p em Pl' fa�a:
Encontre os pontos em Pr' a uma dist. m�xima D de p:
Para isso, projete p em y:
Percorra Pr' e tome apenas os pontos q cujo c�lculo:
|q.y - p.y| <= D. O n�mero m�ximo de q ser� 6.
Calcule a dist�ncia entre p e cada q.
No final encontraremos um par (p3,q3) que dever� ser o
que tem menor dist�ncia nessa faixa entre Pl' e Pr'.
* Para determinar o par mais pr�ximo, teremos que determinar
quem � o m�nimo entre Dl = dist(pl1, pl2),
Dr = dist(pr1, pr2),
Dm = dist(p3, q3).
Chame-os de Dmin, pmin1, pmin2
RETORNE: (Dmin, pmin1,pmin2).
27/06/2000:
In�cio da implementa��o propriamente dita:
Come�amos a desenvolver as estruturas para guardar os pontos e tamb�m
o algoritmo de ordena��o dos pontos segundo suas x-coordenadas.
Escolhemos o Quicksort como algoritmo de ordena��o, seguindo uma
implementa��o dada no livro do Sedgewick (Algorithms in C), que se o
vetor a ser ordenado for menor que uma certa constante M, n�o se chama
o Quicksort recursivamente. No final, � feita uma ordena��o
InsertionSort que rearruma os termos que n�o foram ordenados. Mesmo com
essa passagem do vetor por um Insertionsort, o custo da ordena��o ainda
� O(n.log n).
O algoritmo ainda n�o est� perfeito, caso haja pontos com mesma
coordenada x. Ou seja, ainda n�o colocamos o desempate pela y-coordenada.
28/06/2000:
O algoritmo para ordenar em rela��o � x-coordenada foi arrumado.
Ou seja, agora tamb�m est� funcionando quando h� empate na coordenada x
dos pontos analisados.
Tamb�m foi pensado uma forma r�pida de reaproveitar o c�digo e poder
us�-lo para ordena��o em rela��o � y-coordenada sem muitas altera��es.
29/06/2000:
Foi implementado o algoritmo para ordena��o atrav�s das y-coordenadas
dos pontos. A id�ia foi tentar reaproveitar ao m�ximo o c�digo que j�
tinhamos feito para ordenar em rela��o � x-coordenada.
Partindo desse princ�pio, foram necess�rios apenas alguns ajustes
nas fun��es que eram respons�veis pela compara��o das coordenadas
de dois pontos, que eram passados como par�metros.
Sendo assim, � parte do projeto que corresponde ao pr�-processamento,
que � a ordena��o dos pontos em termos das x-coordenadas e
y-coordenadas, j� est� feito. Resta apenas testar para quantidades
realmente grande de n�meros (mais de 30 pontos, por exemplo).
04/07/2000:
Retomamos o projeto. Nosso objetivo hoje � come�ar a implementar a
parte interna do programa, ou seja, a parte respons�vel pela
determina��o do par de pontos mais pr�ximo.
Est�vamos com d�vida quanto ao real uso de 2 vetores ordenados (um em
rela��o � X e outro em rela��o em Y), mas pensamos um pouco mais e
estamos quase certos que um s� ser� necess�rio.
Tamb�m pensamos quanto � fun��o dist�ncia que ser� definida pelo
usu�rio. Definimos que:
- Precisa haver um arquivo cabe�alho, com nome: distancia.h
que � o prot�tipo da fun��o que incluiremos no programa principal.
- O cabe�alho da fun��o deve ser:
double Distancia(double, double, double, double);
onde cada double recebido como par�metro � na verdade uma coordenada
do ponto ao qual queremos calcular a dist�ncia. Por exemplo, a
chamada:
Distancia(-5.6, 4.2 8.0, 0.33)
Calcula a dist�ncia entre os pontos do R�: (-5.6, 4.2) e (8.0, 0.33).
- O arquivo que cont�m a implementa��o da fun��o deve se
chamar: distancia.c
Implementamos mais algumas estruturas que usaremos para guardar os
pontos mais pr�ximos e sua dist�ncia, um vetor de Pontos, que � a
cole��o onde armazenaremos os pontos do problema. Al�m disso,
escrevemos opera��es b�sicas que mexam com essas estruturas.
05/07/2000:
Detalharemos uma estrutura que ser� muito usada:
Estrutura ParProximo:
valor double para a dist�ncia.
vetor com 2 Pontos, que s�o os mais pr�ximos.
Na parte da manh�, a fun��o para calcular a dist�ncia m�nima, Parproximo,
foi codificada seguindo o pseudo-c�digo que foi escrito nesse relat�rio no
dia 20/06. O c�digo s� foi compilado e corrigido no in�cio da tarde.
A fun��o Parproximo, que � a parte principal do programa entre os pontos
do conjunto est� completada e, pelos testes realizados, parece estar
funcionando corretamente, devolvendo a estrutura que corresponde ao
verdadeiro par de pontos que minimiza a dist�ncia.
Falta realizar mais testes, no sentido de comprovar a validade do programa
desenvolvido.
Pr�ximos passos: Interface gr�fica, que ainda estamos em d�vida se
utilizaremos GLUT/Mesa3D ou GTK (com GDK) ou ainda os dois juntos.
06/07 - 03/08:
A Rede Linux ficou por duas semanas inoperante, o que nos for�ou a
trabalharmos na rede IME e tamb�m em casa.
Tivemos que estudar o GTK e o GDK para fazermos a interface, o que
j� nos consumiu um bom tempo.
Gastamos cerca de uma semana e meia ajustando o c�digo � interface.
No dia 03/08 o projeto j� estava conclu�do e apresentamos ao professor.
|