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

dc.contributorVieira, Marcelo Bernardes
dc.contributorhttp://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4763472P6
dc.contributorBernardino, Heder Soares
dc.contributorhttp://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4742940J5
dc.contributorSilva, Rodrigo Luis de Souza da
dc.contributorhttp://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4769102Z1
dc.contributorColuci, Vitor Rafael
dc.contributorhttp://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4767258T1
dc.creatorAlmeida, Liliane Rodrigues de
dc.date2017-09-22T15:22:19Z
dc.date2017-09-21
dc.date2017-09-22T15:22:19Z
dc.date2017-02-23
dc.date.accessioned2023-09-29T16:38:38Z
dc.date.available2023-09-29T16:38:38Z
dc.identifierhttps://repositorio.ufjf.br/jspui/handle/ufjf/5806
dc.identifier.urihttps://repositorioslatinoamericanos.uchile.cl/handle/2250/9137849
dc.descriptionThis work proposes a method to reposition of 2D polylines representing cylindrical curves in order to keep the distance between line segments with at least c unities plus the radii of any two cylinders, each associated with a polyline. Our approach relies on the construction of a graph representing the points violating a minimum distance, reducing the contact removal problem to a graph coloring problem. Once constructed, the graph is colored using a heuristic to find out which vertices can be in the same plane. The final number of colors indicates the number of planes in third dimension needed to solve contacts. We also propose two approaches to compute vertex displacements from the computed graph and colors, both designed to obtain forests with minimum sum of displacements. Results show the efficiency of the graph construction, graph coloring and color to plane mappings. We apply the proposed method and the two displacement approaches on the problem of untangling forests of polylines representing carbon nanotubes. The number of contacts drops significantly after applying our method even in dense forests of tubes with numerous contacts.
dc.descriptionEste 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.
dc.descriptionFAPEMIG - Fundação de Amparo à Pesquisa do Estado de Minas Gerais
dc.formatapplication/pdf
dc.languagepor
dc.publisherUniversidade Federal de Juiz de Fora (UFJF)
dc.publisherBrasil
dc.publisherICE – Instituto de Ciências Exatas
dc.publisherPrograma de Pós-graduação em Ciência da Computação
dc.publisherUFJF
dc.rightsAcesso Aberto
dc.subjectProcessamento de curvas cilíndricas
dc.subjectPolilinhas livres de cruzamento
dc.subjectColoração de grafos
dc.subjectCylindrical curve processing
dc.subjectCross-free polylines
dc.subjectGraph coloring
dc.subjectCNPQ::CIENCIAS EXATAS E DA TERRA
dc.titleRemoção de contatos em curvas cilíndricas via reposicionamento de polilinhas 2D utilizando coloração de grafos
dc.typeDissertação


Este ítem pertenece a la siguiente institución