Vertex correspondence for compatible convex decompositions between polygons

This paper presents an algorithm to establish a correspondence between the vertices of a pair of polygons. The proposed technique establishes a vertex correspondence between two polygons by inserting new vertices regardless of the locations, orientations, sizes, shapes, or number of vertices of the polygons. These new vertices can be either inserted at the existing vertices, or they can be inserted along the corresponding edges of the polygons. After establishing a successful correspondence between the vertices, the pair of polygons are decomposed into convex sub polygons constructing a compatibility between the decomposed parts. Such a compatible representation between objects are applicable in various techniques such as morphing, warping and blending one shape into another. The vertex correspondence itself is also useful in the areas of pattern recognition and surface reconstruction. The applications in computer animation and shape representation and analysis benefit much from these techniques since establishing correspondence and compatibility play major roles in object representation.