PUCRS
Programação de Software Básico
Faculdade de Informática
Trabalho I - 2007/1
Este trabalho poderá ser desenvolvido por grupos de 2 alunos ou de forma individual
Data da entrega 17/05/2007
DESCRIÇÃO
Este trabalho tem por objetivo
aplicar os conceitos de Programação Orientada a Objetos e Listas encadeadas
vistos em aula.
O objetivo geral do programa a ser desenvolvido
é gerenciar a execução de uma operação de diferença entre dois polígonos.
Todas os dados relativos aos polígonos devem ser armazenados em Listas Encadeadas, desenvolvidas pelos alunos do grupo.
DIFERENÇA ENTRE POLÍGONOS
A operação de
diferença entre dois polígonos PA e PB resulta em
um terceiro polígono que representa os pontos do plano que estão em PA e que não estão em PB. Na figura abaixo, pode-se observar o resultado da operação de diferença entre dois polígonos.
O algoritmo para
realização da operação de diferença
entre dois polígonos é o seguinte:
- Assume-se que os vértices dos polígonos estão ordenados no sentido anti-horário;
- Calcular todas as interseções entre as arestas dos dos polígonos PA e PB;
- Inserir os pontos calculados como novos vértices dos
polígonos PA e PB. Esta inserção deve ser feita de
forma que estes polígonos continuem com seus vértices
orientados no sentido anti-horário;
- Calcular o ponto médio PM(i) de cada um das arestas (i) dos dois polígonos;
- Determinar para cada ponto PM(i) do polígono PA se este ponto está dentro ou fora do polígono PB;
- Determinar para cada ponto PM(i) do polígono PB se este ponto está dentro ou fora do polígono PA;
- A diferença PA-PB é formada pelos vértices
de PA classificados como FORA de PB e pelos vértices de PB
classificados como DENTRO de PA.
FUNÇÕES
O programa deverá executar, pelo menos estas funções:
- Permitir a definição de um polígono: o
usuário poderá informar com o mouse um conjunto de pontos
que formará um polígono. Para definir um vértice
de um polígono o usuário deve clicar com o botão
esquerdo do mouse. Para concluir a entrada dos pontos de um polígono o usuário deve clicar com o botão esquerdo do mouse;
- Executar a operação de diferença:
para executar a operação de diferença o
usuário deve tecla ENTER; Neste momento o polígono
resultante da operação de diferença deve ser
desenhdo na tela à direita dos polígonos PA e PB. Ete
dois polígonos devem permanecer na tela;
- Reiniciar sem polígonos: o programa deve permitir à qualquer momento
que o usuário reinicie a entrada dos polígonos. Neste
caso os pontos que já estiverem na tela devem ser removidos;
- Reiniciar a entrada de um dos polígonos: durante
o processo de entrada dos vértices e qualquer dos dois
polígonos deve ser possível descartar os vértices
DESTE polígono e reiniciar sua entrada. Os vértices que
foram reçem informados devem ser apagados da tela. O outro
polígono deve continuar na tela;
- Reiniciar com o resultado da diferença: após
a realização de uma operação de
diferença, o usuário terá a opção
utiliza-lo com um dos polígonos para a próxima
operação de diferença.
INTERSECÇÃO ENTRE SEGMENTOS DE RETA
O cálculo da
interseção entre dois segmentos de reta pode ser
realizado através do algoritmo descrito em : http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d. Nesta página, você encontra inclusive uma implementação do método em C++.
Além desta página você pode encontrar inúmeras outras usando o google e procurando por line segment intersection.
TESTE DE INCLUSÃO DE PONTO EM POLÍGONO
A determinação de
inclusão de um ponto em um polígono, pode ser
realizada através do algoritmo descrito em http://local.wasp.uwa.edu.au/~pbourke/geometry/insidepoly. Nesta página, você encontra várias implementações.
PROGRAMA PARA ENTRADA DE PONTOS COM MOUSE
Para obter um programa que premite a entrada de pontos através do mouse, clique aqui. Este programa foi projetado para ser usado no wxDevCPP. Descompacte o arquivo .Zip e abra o projeto Poly.dev.
Para marcar os vértices do polígono, utilize o
botão esquerdo do mouse. Para fechar o polígono, clique
com o botão direito.
ENTREGA E APRESENTAÇÃO
A apresentação do trabalho deve ser feita na aula do dia 17 de maio de 2007.
