Contact constraint analysis and determination of geometrically valid contact formations from possible contact primitives

A complete, precise, and systematic analysis on the geometrical nature of contacts between two arbitrary polygons and derivation of the geometric contact constraints between two such polygons are provided. Based on the results, a general algorithm is presented to identify the geometrically valid contact formations (CFs) from a given set S/sub pc/ of possible principal contacts (PCs) between two polygonal objects with location uncertainties. For any (nonempty) subset of S/sub pc/, the algorithm tests if the PCs in the set form a possible CF by verifying the geometrical contact constraints. The obtained set of geometrically valid CFs can serve as input to an additional verifier based on force sensing which can extract the actual CF from the set. The notion of equivalent CFs is introduced to describe those contact situations constraining the relative location between two objects to the same region. This concept proves to be extremely useful to the completeness of the analysis and efficiency of the algorithm. Of the many discoveries, a particularly significant one is that despite uncertainties in object locations, in many cases, if two or more PCs are formed between two objects, their relative location is fixed or can take up to only four solutions.