|
|
|
|
|
 |
|
|
|
 |
|
|
|
 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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.
|