Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-09-21T18:30:26Z No. of bitstreams: 1 lilianerodriguesdealmeida.pdf: 4991501 bytes, checksum: 0d4dbf0a69e24ecbaec4ff6581381709 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-09-22T15:22:19Z (GMT) No. of bitstreams: 1 lilianerodriguesdealmeida.pdf: 4991501 bytes, checksum: 0d4dbf0a69e24ecbaec4ff6581381709 (MD5) / Made available in DSpace on 2017-09-22T15:22:19Z (GMT). No. of bitstreams: 1 lilianerodriguesdealmeida.pdf: 4991501 bytes, checksum: 0d4dbf0a69e24ecbaec4ff6581381709 (MD5) Previous issue date: 2017-02-23 / FAPEMIG - Fundação de Amparo à Pesquisa do Estado de Minas Gerais / 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. / This 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.