How the Beast really moves: Cayley analysis of mechanism realization spaces using CayMos

For a common class of 2D mechanisms called 1-dof tree decomposable linkages, the following fundamental problems have remained open: (a) How to canonically represent (and visualize) the connected components in the Euclidean realization space. (b) How to efficiently find two realizations representing the shortest distance between two connected components. (c) How to classify and efficiently find all the connected components, and the path(s) of continuous motion between two realizations in the same connected component, with or without restricting the realization type (sometimes called orientation type). For a subclass of 1-dof tree-decomposable linkages that includes many commonly studied 1-dof linkages, we solve these problems by representing a connected component of the Euclidean realization space as a curve in a carefully chosen Cayley (non-edge distance) parameter space; and proving that the representation is bijective. We also show that the above set of Cayley parameters is canonical for all generic linkages with the same underlying graph, and can be found efficiently. We add an implementation of these theoretical and algorithmic results into the new software CayMos, and give (to the best of our knowledge) the first complete analysis, visualization and new observations about the realization spaces of many commonly studied 1-dof linkages such as the amusing and well-known Strandbeest, Cardioid, Limacon and other linkages. (C) 2013 Elsevier Ltd. All rights reserved.