• Primeira parte
  • Resumo
  • Introdução
  • Trabalhos correlatos
  • Objetivos do projeto
  • Atividades já realizadas
  • Resultados obtidos
  • Bibliografia
• Segunda parte
  • O BCC no projeto
  • Aplicando MAC332
  • Aplicando MAC328
  • Aplicando MAT112
  • Aplicando MAC211
  • Considerações finais
• Versão alfa em applet do iGeom

Um programa de geometria dinâmica (GD) permite fazer construções geométricas a partir de construções elementares como marcar pontos, traçar retas, semi-retas, segmentos e circunferências, simulando com o mouse o uso de régua e compasso. Entretanto, diferentemente das construções feitas no ``papel'', as construções em um programa de GD são dinâmicas, ou seja, podemos interagir com a construção ``arrastando'' os objetos que a compõem. Quando o usuário intearge com a construção, o programa automaticamente reconstrói os objetos preservando suas relações e propriedades originais. Além disso, a GD ainda traz grandes vantagens num ensino no qual o aluno é incentivado a realizar descobertas, pois transforma o computador numa excelente bancada para realização de testes geométricos.
Por exemplo, podemos construir um segmento AB de extremidades A e B e o seu ponto médio M. Assim, sempre que for ``alterada a coordenada'' de uma das extremidades do segmento, o programa deve ``recalcular a coordenada'' de M de modo que respeite a propriedade da construção original (neste caso M deve ser sempre o ponto médio do segmento AB).
Este trabalho de iniciação científica tem como objetivo a implementação de um programa de geometria dinâmica em Java, estando ligado ao projeto iMatica.
Uma versão alfa do iGeom está disponível em forma de applet neste link.

Um programa de geometria dinâmica (GD) permite construções geométricas elementares como marcação de pontos (inclusive ponto de interseção e ponto sobre outros objetos), traçado de retas, semi-retas, segmentos e circunferências.

Com essas operações podemos reproduzir as construções geométricas que podem ser feitas utilizando régua e compasso, através de um ``mouse''. Por exemplo, podemos traçar as mediatrizes do triângulo da figura abaixo:


Abaixo mostramos como construir o ponto médio de um dos lados do triângulo acima:


Aplicamos o mesmo método para os outros lados e escondemos os objetos que foram construídos para nos auxilar durante a construção:


Agora traçamos o segmentos que liga um vértice ao ponto médio do lado oposto:


O programa pode adicionalmente efetuar construções auxiliares, ou seja, construções que podem ser obtidas a partir de duas ou mais construções elementares e são utilizadas quando há necessidade de fazer uma construção mais complexa em menos passos. Como exemplo de construções auxiliares, podemos citar: construir o ponto médio de um segmento, traçar uma reta passando por um ponto dado e perpendicular uma reta também dada, ou ainda, traçar uma reta que tangencia uma circunferência em um ponto, traçar um polígono dado um conjunto de pontos, dentre muitas outras possibilidades. Um programa de GD mais sofisticado permite a criação de uma nova construção auxiliar e sua gravação na forma de macro. Um outro recurso que pode estar disponível é o cálculo de comprimento, ângulo e área.
Mas o que é mais interessante em um programa de GD é que podemos interagir com a construção arrastando os objetos que a compõem. Fica a cargo do programa preservar as propriedades geométricas e as relações entre os objetos da construção original. Por exemplo, na construção das medianas, podemos movimentar os vértices do triângulo:


Assim, a partir de uma única construção podemos obter uma infinidade de instâncias com as mesmas propriedades da construção original.

Já existem vários programas de geometria dinâmica:

Um programa de GD pode ser utilizado para auxiliar o ensino de geometria plana. Através dele, o aluno será estimulado a aprender geometria fazendo, visualizar as relações e propriedades geométricas, descobrir novas para depois tentar prová-las.
Poderá servir também como uma ferramenta para o ensino de geometria plana à distância, já que o programa terá uma versão applet (programa que pode ser colocado numa página da Web).
O propósito deste projeto é a implementação de um programa de geometria dinâmica as principais funcionalidades dos programas de GD já existentes e mencionadas na seção introdução.

• Análise Orientada a Objetos:
• Estudo de alguns dos softwares de geometria dinâmica já existentes, dando especial atenção ao GSP e ao Cinderella
.
• Identificação de classes de objetos a partir do estudo mencionado no item anterior.
• Design Orientado a Objetos:
  • refinamento da Análise Orientada a Objetos, identificando subclasses;
  • identificação de objetos seus atributos e operações (métodos);
  • estabelecer interfaces para o relacionamento entre objetos;
  • definir uma estrutura de dados para um atributo do objeto;
  • detalhamento dos métodos.
• Estudo do funcionamento do dinamismo num programa de GD.
• Estudo de uma estrutura de dados eficiente para que o dinamismo funcionasse e atualizasse um número mínimo de objetos.
• Estudo do pacote awt do Java.
• Implementação das construções elementares: marcar pontos, traçar retas, segmentos e circunferências.
• Implementação de uma parte do dinamismo (a translação ainda não foi implementada).
• Estudar alguns tópicos de Geometria Analítica para implementar a interseção entre objetos.
• Achar uma forma de diferenciar um ponto de interseção do outro quando há duas interseções entre os objetos.
• Implementação da interseção entre qualquer combinação de dois objetos do conjunto {reta, segmento, circunferência}.
• Implementação do módulo que grava e recupera as construções geométricas em um arquivo.
• Geração de applets
: gerar um arquivo em html com uma applet contendo uma construção geométrica lida de um arquivo.

O programa já está com uma funcionalidade básica. Podemos marcar pontos, traçar retas, segmentos, circunferências, marcar pontos de interseção, ponto sobre objeto. Por enquanto podemos mover somente os pontos. Já é possível gravar e recuperar uma construção e gerar applet de uma construção.
Para ver os resultados, uma versão applet do programa está disponível neste link.

[1]

Paulo Boulos e Ivan de Camargo, Geometria Analítica Um Tratamento Vetorial, McGraw-Hill, 1987.

[2]

Cormen, Leiserson e Rivest, Introduction to Algorithms, McGraw-Hill, 1999.

[3]

Patrick Naughton, Dominando o Java, Makron Books, 1996.

[4]

Laura Lemay e Rogers Cadenhead, Aprenda em 21 dias Java 1.2, Editora Campus, 1999.

[5]

R. Pressman, Engenharia de Software, Makron Books, 1995.

[6]

Documentação do Java

[7]

Paulo Feofiloff, Notas de aula do curso MAC338: Algoritmos em grafos

Nas próximas 4 seções vou relacionar alguns cursos do BCC com este projeto.

O primeiro passo foi utilizar as técnicas aprendidas no curso MAC332 (Engenharia de Software).

• Análise Orientada a Objetos:
• Estudo de alguns dos softwares de geometria dinâmica já existentes, dando especial atenção ao GSP e ao Cinderella
.
• Identificação de classes de objetos a partir do estudo mencionado no item anterior.

• Design Orientado a Objetos:
• refinamento da Análise Orientada a Objetos, identificando subclasses;
• identificação de objetos seus atributos e operações (métodos);
• estabelecer interfaces para o relacionamento entre objetos;

• definir uma estrutura de dados para um atributo do objeto;
• detalhamento dos métodos.

Para que o dinamismo funcionasse, uma solução foi representar uma construção em um grafo onde os vértices são os objetos geométricos (pontos, retas,..) e um arco (a, b) indica que o objeto b depende de a. Por exemplo um vértice (Ponto, Reta) significa que Ponto é um dos pontos que define Reta. E um vértice (Reta, Ponto) significa que Ponto foi construído sobre Reta.
Abaixo, vou mostrar passo a passo uma construção e o respectivo grafo que a representa.
Marco os pontos B e C:

Construo uma circunferência C1 com centro C e que passa pelo ponto B. Em seguida, construo os ponto A e D sobre C1:


Construo uma reta r que passa por A e B e uma s que passa por A e D:


Construo um ponto E sobre r e os pontos F e G sobre s. Em seguida construo um segmento de extremidades E e F:


Ao mover um ponto P devemos atualizar todos os objetos que depende direta ou indiretamente dele, ou seja, devemos atualizar todos os objetos a em que existe um caminho entre P e a fazendo, por exemplo, uma busca em profundidade.
Por exemplo, na última construção, ao mover o ponto B, devemos atualizar os objetos C1, A, D, r, s, E, F, G e EF.
No entanto, apesar do algoritmo utilizado funcionar, ele é ineficiente, pois um objeto pode ser atualizado mais de uma vez. Não adiantaria atualizar e marcar um objeto como ``atualizado'' para fazer um teste durante a busca, pois o objeto foi influenciado por objetos diferentes. Por exemplo, o ponto E será atualizado duas vezes, pois E foi construído sobre r, ele será atualizado uma vez devido a A e outra devido a B.
Para resolver o problema, temos que saber quais objetos vão ser influenciado no movimento do ponto B, achando um conjunto S de objetos que são alcançáveis a partir de B (ou seja, que existe um caminho entre B e o objeto) fazendo, por exemplo uma busca em profundidade.
Um objeto b é dito atualizado se não existir nenhum arco (a, b) com a, b em S.
Se um objeto a já foi atualizado então podemos atualizar os objetos que dependem diretamente dele (ou seja os objetos b tal que existe um arco (a, b)) e se isso for feito, devemos remover a de S.
Cada passo do algoritmo consiste em remover um objeto S até que ele fique vazio. Abaixo vamos simular este algoritmo para a última construção feita acima.
Primeiro achamos o conjunto S:


O objeto em vermelho indica o objeto que foi escolhido para ser removido numa dada iteração.
Inicialmente, o único objeto que podemos remover é o ponto B (veja o primeiro grafo da figura abaixo). No último grafo podemos remover tanto o ponto A quanto o ponto D.


Observe que só agora podemos remover a reta r de S.

Nesta seção vou falar sobre alguns problemas que tive e resolvi utilizando o que eu aprendi em MAT112.

Problema: Se dois objetos se interceptam em dois pontos, temos que saber diferenciar um do outro já que o método que calcula a interseção irá devolver dois pontos e o programa deverá saber qual das duas coordenadas será usada para atualizar o ponto que chamou o método.

A figura abaixo ilustra este problema: no canto superior direito temos a configuração correta após termos arrastado o ponto D; o método atualizou os pontos A e B corretamente. Já no canto inferior direito, o método atualizou os pontos A e B incorretamente, levando o objetos que dependia dele ser atualizado incorretamente.

Solução: Dar uma orientção aos pontos:



Assim, ao criar o ponto de interseção A, marco ele como norte ou sul de acordo com o critério acima (neste caso marco norte). Deste modo, quando o método que calcula a interseção me devolver os pontos P1 e P2 atualizo o ponto A com a mesma coordenada do ponto que está ao norte (dentre P1 e P2).

Problema: Às vezes, para calcular os pontos de interseção entre duas circunferências temos que resolver um difícil sistema de equações:


Solução: Mudança de base.


Assim, temos que resolver um sistema mais simples:

Foi bastante útil a experiência adquirida durante o projeto de MAC211 para este projeto, pois pude usar as mesmas técnicas lá aprendidas e aplicadas como modularização, gerenciamento e depuração de código.
Seria interessante se eu tivesse tido este curso em paralelo (ou antes) que o curso MAC332.

Este projeto foi uma ótima experiência, pois participei dele desde a modelagem até a implemtação além de ter tido a oportunidade aplicar um pouco de quase tudo do que aprendi no BCC. Usei apenas conceitos básicos (busca em largura, produto escalar), mas sem eles seria difícil resolver alguns dos problemas mencionados nas seções anteriores, ou seria difícil adicionar novas funcionalidades ao programa.
Foi uma pena estar sozinho neste projeto. A única pessoa com que podia discutir os problemas era com o meu orientador e que estava sempre disposto.
Talvez uma frustação seria que este projeto não está relacionado com nenhuma área da ciência da computação, pois gostaria de aproveitar um trabalho que pudesse continuar estudando numa pós-graduação.