%0 Conference Proceedings
%4 sid.inpe.br/sibgrapi/2019/09.08.20.59
%2 sid.inpe.br/sibgrapi/2019/09.08.20.59.51
%@doi 10.1109/SIBGRAPI.2019.00024
%T Solving Tangram Puzzles Using Raster-Based Mathematical Morphology
%D 2019
%A Yamada, Fernanda Miyuki,
%A Gois, João Paulo,
%A Batagelo, Harlen Costa,
%@affiliation Federal University of ABC
%@affiliation Federal University of ABC
%@affiliation Federal University of ABC
%E Oliveira, Luciano Rebouças de,
%E Sarder, Pinaki,
%E Lage, Marcos,
%E Sadlo, Filip,
%B Conference on Graphics, Patterns and Images, 32 (SIBGRAPI)
%C Rio de Janeiro, RJ, Brazil
%8 28-31 Oct. 2019
%I IEEE Computer Society
%J Los Alamitos
%S Proceedings
%K Tangram, cutting and packing, raster representation, mathematical morphology.
%X 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.
%@language en
%3 Paper_84_SIBGRAPI.pdf