Uma heurística para resolver quebra-cabeças de tangram através de uma representação raster e morfologia matemática
The tangram is a dissection puzzle composed of polygonal pieces which can be combined to form different patterns. Besides being a recreational puzzle, the tangram relates to a more general class of combinatorial NP-hard problems such as the two-dimensional cutting stock problem. Most of the current methods applied in the automatic solution of the tangram present a lack of representation of tangram patterns that are not described by a single closed contour with no holes. In addition, most methods present limitations in the transformations applied to the pieces by restricting the angles of rotation and not implementing the reflection transformation. In this study, we tackle these limitations by introducing a heuristic method that uses a raster representation of the puzzle. In order to adapt the geometrical techniques that are applied in the prevention of piece overlapping and in 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 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.