Kinematic Reasoning with Spatial Decompositions

This paper examines the application of hierarchical discrete spatial representations to the kinematic analysis and synthesis of the higher pairs. Two instances of hierarchical representation are investigated, a global decomposition in the form of quadtrees, and an object-centered, multi-level molecular decomposition. Kinematic reasoning with both representations relies upon the rapid evaluation of the single occupancy constraint. For both representations we present algorithms that allow the rapid detection of intersection between two objects, the analysis of higher pair mechanisms, and a restricted class of kinematic synthesis.