Pós-Graduação
em Ciência da Computação
Computação Gráfica
Trabalho I - 2019/1
Data de Entrega: 07/maio/2019
Prof. Márcio Sarroglia Pinho
Objetivo
Analisar
algoritmos de cálculo de inclusão de ponto em polígonos.
Descrição
Criar um programa
que deverá ler um arquivo com a descrição de uma malha de polígonos 2D e exibi-lo na tela.
Esta malha deve conter um número de polígonos tal que o algoritmo
básico, descrito abaixo, leve pelo menos 5 segundos para executar.
O programa deverá executar, pelo menos, os seguintes algoritmos:
- Aplicar o algortimo básico de inclusão de ponto em polígono côncavo;
- Transformar os polígonos côncavos em convexos e aplicar na nova malha o algoritmo de inclusão de ponto em polígono convexo;
- Acrescentar o uso de envelopes nos dois algoritmos acima
- Implementar o Método das Faixas(Slab Method).
Para demostrar o
funcionamento correto do programa, deve ser possível indicar um ponto
sobre a malha de polígons e o program deve mostrar qual dos polígonos
contém o ponto indicado.
Ao final, o programa
deverá gerar um relatório do
comportamento dos algoritmos com várias quantidades de polígonos e
pontos. Neste relatório devem estar presentes informações a respeito de
tempo de processamento em cada fase dos algoritmos e de seu consumo de
memória.
Sugestões de Malhas de Polígonos
Mapas
Uma sugestão para dados de entrada são mapas no formato shapefile, definido pela ESRI para dados
vetoriais simples com atributos, e consiste de três arquivos para cada
tipo de informação:
- XXX.shp – contém os vértices;
- XXX.shx – contém o índice de dados que aponta para as estruturas no arquivo.shp;
- XXX.dbf – contém os atributos no formato xBase (dBase).
Para facilitar a leitura dos dados, pode ser usada a biblioteca Shapefile C Library, disponível neste link local. No arquivo shpdump.c há um exemplo do uso da biblioteca. A documentação completa da biblioteca está em seu site oficial no endereço http://shapelib.maptools.org.
Exemplos de mapas podem ser obtidos no final desta página.
A partir da exibição dos mapas, o programa
deverá, quando for comandado pelo usuário,
sortear uma grande quantidade de pontos sobre a malha de polígonos e determinar dentro de que polígonos está cada ponto.
Exemplos de mapas
http://www.fepam.rs.gov.br/biblioteca/geo/bases_geo.asp
ibge.zip
dados_geo.zip
ArcExplorer: Visualizador de mapas no formato shapefile.
Malha de Triângulos
Outra possibilidade é gerar uma malha de triângulos a partir de um conjunto de pontos aleatórios distribuídos no plano.
Exemplos destas malhas podem ser obtidas neste arquivo.
Além disto, você pode usar os programas que estão nos links a seguir para gerar suas próprias malhas.
Geradores de Malha de Polígonos
CompGeom_in_C.zip
Triangularization.zip
http://www.cs.cornell.edu/home/chew/Delaunay.html
http://www.cs.cmu.edu/~quake/triangle.html
http://www.robertschneiders.de/meshgeneration/software.html
http://www.codeproject.com/Articles/492435/Delaunay-Triangulation-For-Fast-Mesh-Generation
Links
úteis
Tutorial de OpenGL (Profa. Isabel Manssour)
Fórmulas
de cálculo de interseção entre
segmentos de reta
Exemplo de programa em OpenGL
