Computação Gráfica
Trabalho sobre Inclusão de Ponto em Polígonos
2020/2
Introdução
Este trabalho, que
deverá ser feito em dupla ou individualmente, consiste em desenvolver
program que avalie algoritmos de inclusão de ponto em polígonos, usando OpenGL.
O programa deverá ler um polígono descrito
em um arquivo e exibi-lo na tela. A partir disto deverá ser gerado um
conjunto de pontos que serão classificados como dentro ou fora do
polígono lido.
Para desenvolver o trabalho, utilize o programa base, apresentado ao final desta página.
Não serão aceitos trabalhos que não sejam genéricos quanto ao número de objetos gráficos manipulados.
Descrição
Após a carga do polígono deverá ser gerado:
- o Convex Hull do polígono. O polígono gerado deverá ser exibido na tela com uma cor diferente do polígono lido;
- um conjunto de 10 faixas dividindo o
espaço ao longo do eixo Y e cadastrando, em cada faixa, o número das
arestas que passam naquela faixa. As faixas deverão ser exibidas na
tela.
Os pontos que estiverem dentro do polígono deverão ser exibidos em azul e os que estiverem fora do polígono, mas dentro do Convex Hull em amarelo e os que estiverem fora do Convex Hull, em vermelho.
Deverão ser implementados os seguintes algoritmos de teste de inclusão:
- Força bruta, calculando o número de de interseções;
- Teste de inclusão em polígono convexo, usando o Convex Hull;
- Teste de força bruta, considerando apenas as arestas que estão na faixa onde fica o ponto.
Para a entrega do trabalho deverá ser
gerado um relatório que demonstre o comportamento dos algoritmos com
200, 2000 e 20000 pontos. Este comportamento deverá ser descrito em
termos de :
- o tempo de execução de cada algoritmo
- número de vezes que a função HaIntersecao foi chamada;
- numero de vezes que a função ProdVetorial foi chamada.
Descrição do Programa Base
Como base para implementar seu trabalho, utilize o código disponivel em
Este código lê um arquivo texto que descreve um polígono e exibe-o na
tela. No exemplo, o polígono descreve as fronteiras o estado do Rio
Grande do Sul.
Para analisar este programa, inicie pelo arquivo ExibePoligonos.cpp. Neste fonte, comece para função init que faz a leitura do arquivo, chamando a função LeMapa("EstadoRS.txt").
Os dados lidos são colocados em uma estrutura de dados que descreve um polígono. Esta estrutura é baseada na classe Poligono, conforme o código a seguir apresentado em C++. Os códigos em Python e Java são muito semelhantes.
class Poligono
{
vector <Ponto> Vertices;
public:
Poligono();
Ponto getVertice(int);
unsigned long getNVertices();
void insereVertice(Ponto);
void desenhaPoligono();
void desenhaVertices();
void imprime();
};
Após a leitura, são ajustados os limites da área de trabalho do OpenGL,
a fim de que o polígono possa ser exibido na tela. As variáveis que
armazenam estes limites chamam-se Min e Max.
Após a carga, a função display é executada automaticamente. Para
exibir o polígono são chamados dois métodos, conforme o trecho de
código a seguir. Na primeira parte são desenhadas as arestas em
amarelo, na segunda, os vértices em verde.
glLineWidth(2);
glColor3f(1,1,0); // R, G, B [0..1]
Mapa.desenhaPoligono();
glPointSize(5);
glColor3f(0,1,0); // R, G, B [0..1]
Mapa.desenhaVertices();
A saída do programa é apresentada na figura a seguir.
Figura - Exemplo do Mapa do Rio Grande do Sul
Entrega
-
Data de entrega no Moodle e apresentação: 17/09/2020 até o
horário da aula.
- Os
trabalhos podem ser desenvolvidos em duplas. Os arquivos, contendo os
fontes do programa, devem ser compactados e submetidos pelo Moodle até
a data e hora especificadas. ENVIE APENAS ARQUIVOS .ZIP, ou seja,
não envie 7z, rar, tar.gz, tgz, tar.bz2, etc.
-
A nota do trabalho depende da apresentação deste no laboratório, na
data marcada. Trabalhos entregues mas não apresentados terão sua nota
anulada automaticamente. Durante a apresentação será avaliado o domínio
da resolução do problema, podendo inclusive ser possível invalidar o
trabalho quando constatada a falta de conhecimento sobre o código
implementado.
-
A cópia parcial ou completa do trabalho terá como consequência a
atribuição de nota ZERO ao trabalho dos alunos envolvidos.
FIM.