Tamanho da fonte:
ANÁLISE DE CUSTO COMPUTACIONAL DE ALGORITMOS INCREMENTAIS IMPLEMENTADOS NA CGAL PARA A TRIANGULAÇÃO DE DELAUNAY
Última alteração: 2018-08-15
Resumo
A modelagem e a resolução de problemas físicos e da Engenharia utilizando procedimentos computacionais é usual.Uma das maneiras de se realizar essa modelagem é através da malha de Delaunay. Para um conjunto bidimensionalcontendo n pontos, essa é a melhor malha a ser gerada, por conter triângulos equiláteros ou o mais próximo aequiláteros. Para a construção dessa estrutura, a ordem em que os pontos são inseridos no domínio interfere no tempodos algoritmos que a geram. Assim, neste trabalho, é avaliado o tempo que diferentes formas de inserção de pontoslevam para gerar a malha de Delaunay. Os testes foram realizados na biblioteca CGAL, com até 10 milhões de pontos, eutilizaram-se as ordens de inserção de pontos aleatória, a ordem da curva de Hilbert e a ordem da curva de Hilbertcombinada com buckets dessa biblioteca. Verificou-se que, dentre as ordens de inserção testadas, a curva de Hilbert combuckets apresentou os melhores custos computacionais, seguida da curva de Hilbert tradicional.
Texto completo:
PDF