Bioeconomia: Diversidade e Riqueza para o Desenvolvimento Sustentável
21 a 25 de outubro de 2019
Trabalho 12110
| ISSN | 2237-9045 |
|---|---|
| Instituição | Universidade Federal de Viçosa |
| Nível | Graduação |
| Modalidade | Pesquisa |
| Área de conhecimento | Ciências Exatas e Tecnológicas |
| Área temática | Ciências Exatas e da Terra |
| Setor | Departamento de Informática |
| Bolsa | PIBIC/CNPq |
| Conclusão de bolsa | Não |
| Primeiro autor | Rodrigo Eduardo de Oliveira Bauer Chichorro |
| Orientador | SALLES VIANA GOMES DE MAGALHAES |
| Título | Algoritmo para interseção de mapas bidimensionais |
| Resumo | Um mapa bidimensional é um conjunto de pontos e segmentos de reta ligando esses pontos, formando um ou vários polígonos fechados, com várias faces internas e uma face externa. Dados dois mapas bidimensionais, a interseção destes mapas é um outro mapa tal que cada face deste é a interseção entre uma face de um dos mapas de entrada com uma face do outro mapa. Calcular essa interseção é uma operação importante no âmbito da geometria computacional. Contudo, devido à grande quantidade de casos especiais, aos possíveis erros de arredondamento de números de ponto flutuante e ao tamanho dos mapas a serem processados na prática, a implementação de um algoritmo exato, robusto e eficiente para realizar esse cálculo ainda é um uma tarefa não-trivial. Assim, é comum que algoritmos de interseção possuam algumas das características mencionadas anteriormente, mas não todas (exemplo: um algoritmo robusto e eficiente, mas que não é exato). Com isso, durante o projeto de Iniciação Científica, trabalhou-se com o aprimoramento de um algoritmo de interseção de mapas desenvolvido pelo orientador do projeto, que apesar de ser robusto, exato e eficiente, ainda possuia espaço para aperfeiçoamento no quesito da eficiência. O foco do projeto foi afunilando-se com o passar dos meses, e no final fixou-se um dos subproblemas do problema maior da interseção de mapas: encontrar o ponto de interseção entre um par de segmentos de reta. O subproblema envolve calcular os pontos de interseção entre todos os segmentos de reta do primeiro mapa com todos os segmentos do segundo mapa. Para acelerar o processo, primeiro cria-se uma grade uniforme e insere-se os segmentos em suas respectivas células da grade. Assim, a grade funciona como um índice geométrico e só é necessário calcular o ponto de interseção de um par de segmentos se estes estão na mesma célula da grade. Outra otimização importante, já que o cálculo entre dois pares diferentes é independente, é a utilização de programação paralela, permitindo o processamento de vários pares ao mesmo tempo. Concluindo, com o uso destas (e um conjunto adicional de) técnicas, foi possível acelerar ainda mais as interseções de segmentos, sem perder a exatidão e robustez do algoritmo. |
| Palavras-chave | Algoritmo, interseção, mapas |
| Forma de apresentação..... | Painel |