Solving Tangram Puzzles Using Raster-Based Mathematical Morphology - Yamada, Fernanda M.; Gois, Joao; Batagelo, Harlen C. (Anais da Conference on Graphics, Patterns and Images (SIBGRAPI); 2019: Anais da XXXII Conference on Graphics, Patterns and ImagesDO - 10.5753/sibgrapi.2019.9791, 2019)
The Tangram is a dissection puzzle composed of polygonal pieces which can be combined to form different patterns. Solving the Tangram is a two-dimensional irregular shape packing problem known to be NP-hard. Tangram patterns may be composed of multiple connected components, and assembling them may require the reflection transformation and unconstrained rotations of the pieces. In this work, we propose a novel approach for the automatic solution of the Tangram based on a raster representation of the puzzle. In order to adapt the geometrical techniques that are applied to the prevention of piece overlapping and the reduction of space between pieces, we use morphological operators and representations commonly used in the discrete domain such as the dilation operator, the distance transform and the morphological skeletonization. We investigate the effects of the raster representation in the puzzle assembly process and verify the effectiveness of the proposed method in solving different Tangram puzzles.