文章基本信息

标题：Graph Layout Algorithms for Automated Sketching of Linkage Mechanisms
本地全文：下载
作者：Martín A. Pucheta ; Nicolás E. Ulrich ; Alberto Cardona 等
期刊名称：Mecánica Computacional
印刷版ISSN：2591-3522
出版年度：2010
卷号：XXIX
期号：61
出版社：CIMEC-INTEC-CONICET-UNL
摘要：The graph layout problem arises frequently in the conceptual stage of mechanism design, specially in the enumeration process where hundreds of topological solutions must be analyzed. Several combinatorial, heuristic (e.g. geometrical and genetic algorithms), and force-directed algorithms (based on spring models, self-organizing maps) have been used for layout of graphs of kinematic chains and linkage mechanisms. Two main objectives of graph layout are the avoidance of edge crossings and the aesthetics. Edge crossings cannot be always avoided by force-directed algorithms since they reach a minimum of the energy in dependence with the initial position of the vertices, often randomly generated. Since the number of vertices of graphs of mechanisms is low, combinatorial algorithms can b e used to ﬁnd an adequate initial position. In this paper, we present a combination of two algorithms: a combinatorial algorithm based on the exhaustive exploration of loop combinations with identiﬁcation of all possible forms of drawing the graph as a base circle and successive arcs, followed by a force-directed algorithm based on spring repulsion and electrical attraction. The ﬁrst algorithm is used to ﬁnd an initial layout without edge crossings; then, the force-directed algorithm is used to achieve regularity on edges sizes and nodes distribution. Several available graphs of complex kinematic chains are used to validate the results. The layouts obtained have go od quality in terms of minimization of edge crossings and maximization of aesthetic characteristics.