Geração de Malhas Triangulares
Detalhes
- Tipo de apresentação: Trabalho
- Eixo temático: EXATAS
- Palavras chaves: Triangulações; Malhas; Delaunay;
- 1 Unicamp
- 2 UNICAMP
Geração de Malhas Triangulares
Henrique Tonello Pereira
UNICAMP
Resumo
A ideia da geração de malhas consiste em decompor um domínio geométrico de forma a representar informações em pequenas células. Neste projeto trabalhamos com malhas triangulares em 2D, isto é, regiões no plano decompostas por triângulos. Malhas triangulares são muito importantes em computação gráfica, pois diversos objetos são mapeados por malhas para serem renderizados ou submetidos a outros métodos de imagem. Na cartografia, geografia, entre outros, os terrenos podem ser representados por meio de malhas, fornecendo uma representação mais compacta das informações da região. O foco particular é no estudo de triangulações de Delaunay no plano, como são definidas e sobre o processo de construção, tanto teórico quanto computacional, de geração de uma malha de qualidade. As triangulações de Delaunay foram utilizadas por fornecerem um bom conjunto de triângulos para usar como polígonos em malhas. Em específico, a triangulação Delaunay evita triângulos estreitos (a resolução de equações diferenciais utilizando-se malhas com esses triângulos, por exemplo, leva a dificuldades numéricas).
Apoio/Financiamento da Pesquisa: PICME/CNPq
Discussões Científicas de Qualidade
Com ~200 mil publicações revisadas por pesquisadores do mundo todo, o Galoá impulsiona cientistas na descoberta de pesquisas de ponta por meio de nossa plataforma indexada.
Confira nossos produtos e como podemos ajudá-lo a dar mais alcance para sua pesquisa:
Henrique Tonello Pereira
Olá Bernardo, que legal o problema do caixeiro viajante! Eu realmente não conhecia!
De fato existe certa semelhança, eu acho que é porque ambos os problemas possuem um paralelo com teoria de grafos.
Quanto a sua pergunta, de fato não pensamos em alguma forma de deixar o algoritmo ótimo, mas o algoritmo para gerar triangulações de Delaunay, pelo método que eu utilizei de base, que faz a troca de arestas, é de ordem n^2, no entanto existem outros mais rápidos, de ordem n.log(n), que utilizam outros meios. Certamente o meu código não é tão bom quanto esses, pois o objetivo do projeto foi apenas desenvolver esses códigos para entender o processo de geração de malhas.
Espero que sua pergunta tenha sido respondida, e muito obrigado :)