Pyramidal Decomposition of 2D Shapes

Pyramidal decomposition of a 2 D shape has a wide range of applications in shape encoding and shape analysis. In order to find common pieces that can be approximately assembled into a set of given shapes, we propose a longest-diagonal based pyramidal decomposition algorithm. First, we partition the input polygon into two sub-polygons along an arbitrary diagonal. Then we construct a visibility based distance matrix between the two sub-polygons to encode the distances between vertices. After that, the longest diagonal can be quickly found with the help of the distance matrix. Finally, we take the longest diagonal as the base and decompose the input shape in a divide-and-conquer style. Extensive experimental results show that our solution is very close to the optimal one. We also demonstrate its use in puzzle designing.