Remoção de contatos em curvas cilíndricas via reposicionamento de polilinhas 2D utilizando coloração de grafos

Detalhes bibliográficos
Ano de defesa: 2017
Autor(a) principal: Almeida, Liliane Rodrigues de lattes
Orientador(a): Vieira, Marcelo Bernardes lattes
Banca de defesa: Silva, Rodrigo Luis de Souza da lattes, Coluci, Vitor Rafael lattes
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Universidade Federal de Juiz de Fora (UFJF)
Programa de Pós-Graduação: Programa de Pós-graduação em Ciência da Computação
Departamento: ICE – Instituto de Ciências Exatas
País: Brasil
Palavras-chave em Português:
Área do conhecimento CNPq:
Link de acesso: https://repositorio.ufjf.br/jspui/handle/ufjf/5806
Resumo: Este trabalho propõe um método de reposicionamento de polilinhas em 2D que representam curvas cilíndricas para manter a distância entre os segmentos de reta com pelo menos e unidades mais os raios de dois cilindros quaisquer, cada um associado a uma polilinha. A abordagem depende da construção de um grafo que representa os pontos que violam uma distância mínima, reduzindo o problema de remoção de contatos ao problema de coloração de grafos. Uma vez construído, o grafo é colorido usando uma heurística para encontrar quais vértices podem estar no mesmo plano. O número final de cores indica o número de planos na terceira dimensão necessários para resolver os contatos. Propõe-se também duas abordagens para calcular os deslocamentos dos vértices a partir dos grafo e das cores computadas, ambas projetadas para obter florestas com a soma de deslocamentos mínima. Os resultados mostram a eficiência da construção do grafo, da coloração do grafo e do mapeamento de cor em planos. Aplica-se o método proposto e as duas abordagens de deslocamento no problema de desentrelaçamento de florestas de polilinhas que representam nanotubos de carbono. O número de contatos cai significativamente depois da aplicação do método mesmo em florestas de tubos densas e com vários contatos.