PUCRS
Faculdade de Informática
Computação
Gráfica
Pós-Graduação
em Ciência da Computação
Trabalho I
Data de Entrega: 02/maio/2011
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 20 segundos para executar.
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.
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).
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.
Links
úteis:
Tutorial de OpenGL (Profa. Isabel Manssour)
Fórmulas
de cálculo de interseção entre
segmentos de reta
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: .
Programas de Triangularização
