Pós-Graduação
em Ciência da Computação
- Computação Gráfica
Trabalho 4 - 2020/1
Inclusão de Pontos em Malha de Polígonos
Data de Entrega: 30/06/2020
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 um mapa e exibi-lo na tela.
Este mapa deve definir uma região que é dividida em subrregiões, como estados e municípios, ou países e estados.
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 para um certo conjunto de pontos aleatórios
.
O programa deverá executar, pelo menos, os seguintes algoritmos:
- Aplicar o algortimo básico de inclusão de ponto em polígono côncavo. Este algoritmo é o mesmo desenvolvido no primeiro exercício;
- 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 de cada algoritmo do programa, deve ser possível indicar um ponto sobre a malha
de polígonos e o programa deve mostrar qual dos polígonos contém o ponto.
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.
Mapas
Uma sugestão para dados de entrada são mapas no formato shapefile, que consiste de três arquivos:
- 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.
Ferramentas úteis
Geradores de triangularização:
Ferramentas diversas de Geometria Computacional: CompGeom_in_C.zip
FIM.
