Remoção de contatos em curvas cilíndricas via reposicionamento de polilinhas 2D utilizando coloração de grafos
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Universidade Federal de Juiz de Fora (UFJF)
DOI
Abstract
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.
Description
Citation
Endorsement
Review
Supplemented By
Referenced By
Rights and licensing
Acesso Aberto
