Solving Tangram Puzzles Using Raster-Based Mathematical Morphology
Resumo
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.
Palavras-chave:
Tangram, cutting and packing, raster representation, mathematical morphology
Referências
S. J. Spencer, The Tangram Route toInfinity, Trafford, 2004.
L. R. Mundim, M. Andretta, M. A. Carravilla, J. F. Oliveira, "A general heuristic for two-dimensional nesting problems with limited-size containers", International Journal of Production Research, pp. 1-2017.
T. Martins, M. S. G. Tsuzuki, "Simulated annealing applied to the irregular rotational placement of shapes over containers with fixed dimensions", Expert Systems with Applications, vol. no. 3, pp. 1955-192010.
F. M. Yamada, H. C. Batagelo, "A comparative study on computational methods to solve tangram puzzles", Workshop of Works in Progress (WIP) in the 30th Conference on Graphics Patterns and Images (SIBGRAPI'17), October 2017.
E. S. Deutsch, K. C. Hayes, "A heuristic solution to the tangram puzzle", Machine Intelligence, vol. 7, pp. 205-21972.
K. Oflazer, "Solving tangram puzzles: A connectionist approach", International journal of intelligent systems, vol. 8, no. 5, pp. 603-61993.
F. A. Andaló, G. Taubin, S. Goldenstein, "Solving image puzzles with a simple quadratic programming formulation", Graphics Patterns and Images (SIBGRAPI) 2012 25th SIBGRAPI Conference on., pp. 63-2012.
E. D. Demaine, M. L. Demaine, "Jigsaw puzzles edge matching and polyomino packing: Connections and complexity", Graphs and Combinatorics, vol. no. 1, pp. 195-208, 2007.
D. Bartoněk, "A genetic algorithm how to solve a puzzle and its using in cartography", Acta Scientiarum Polonorum. Geodesia et Descriptio Terrarum, vol. 4, no. 2, pp. 15-2005.
S. Z. Kovalsky, D. Glasner, R. Basri, "A global approach for solving edge-matching puzzles", SIAM Journal on Imaging Sciences, vol. 8, no. 2, pp. 916-92015.
F. M. Toledo, M. A. Carravilla, C. Ribeiro, J. F. Oliveira, A. M. Gomes, "The dotted-board model: a new mip model for nesting irregular shapes", International Journal of Production Economics, vol. 1no. 2, pp. 478-487, 2013.
M. O. Rodrigues, F. M. Toledo, "A clique covering mip model for the irregular strip packing problem", Computers & Operations Research, vol. 87, pp. 221-22017.
S. MirHassani, A. J. Bashirzadeh, "A grasp meta-heuristic for two-dimensional irregular cutting stock problem", The International Journal of Advanced Manufacturing Technology, vol. no. 1–4, pp. 455-42015.
L. R. Mundim, M. Andretta, T. A. de Queiroz, "A biased random key genetic algorithm for open dimension nesting problems using no-fit raster", Expert Systems with Applications, vol. pp. 358-32017.
A. M. del Valle, T. A. de Queiroz, F. K. Miyazawa, E. C. Xavier, "Heuristics for two-dimensional knapsack and cutting stock problems with items of irregular shape", Expert Systems with Applications, vol. no. pp. 12589-12598, 2012.
D. Dalalah, S. Khrais, K. Bataineh, "Waste minimization in irregular stock cutting", Journal of Manufacturing Systems, vol. no. 1, pp. 27-2014.
M. Fischetti, I. Luzzi, "Mixed-integer programming models for nesting problems", Journal of Heuristics, vol. no. 3, pp. 201-22009.
R. Alvarez-Valdes, A. Martinez, J. Tamarit, "A branch & bound algorithm for cutting and packing irregularly shaped pieces", International Journal of Production Economics, vol. 1no. 2, pp. 463-42013.
A. M. Gomes, J. F. Oliveira, "Solving irregular strip packing problems by hybridising simulated annealing and linear programming", European Journal of Operational Research, vol. 1no. 3, pp. 811-82006.
K. A. Dowsland, S. Vaid, W. B. Dowsland, "An algorithm for polygon placement using a bottom-left strategy", European Journal of Operational Research, vol. 1no. 2, pp. 371-32002.
B. Baran, B. Dogusoy, K. Cagiltay, "How do adults solve digital tangram problems? analyzing cognitive strategies through eye tracking approach", Human-Computer Interaction. HCI Intelligent Multimodal Interaction Environments. Springer, pp. 555-52007.
E. Esicup, Special interest group in cutting and packing, 2007, [online] Available: https://www.euro-online.org/websites/esicup/data-sets/.
L. R. Mundim, M. Andretta, M. A. Carravilla, J. F. Oliveira, "A general heuristic for two-dimensional nesting problems with limited-size containers", International Journal of Production Research, pp. 1-2017.
T. Martins, M. S. G. Tsuzuki, "Simulated annealing applied to the irregular rotational placement of shapes over containers with fixed dimensions", Expert Systems with Applications, vol. no. 3, pp. 1955-192010.
F. M. Yamada, H. C. Batagelo, "A comparative study on computational methods to solve tangram puzzles", Workshop of Works in Progress (WIP) in the 30th Conference on Graphics Patterns and Images (SIBGRAPI'17), October 2017.
E. S. Deutsch, K. C. Hayes, "A heuristic solution to the tangram puzzle", Machine Intelligence, vol. 7, pp. 205-21972.
K. Oflazer, "Solving tangram puzzles: A connectionist approach", International journal of intelligent systems, vol. 8, no. 5, pp. 603-61993.
F. A. Andaló, G. Taubin, S. Goldenstein, "Solving image puzzles with a simple quadratic programming formulation", Graphics Patterns and Images (SIBGRAPI) 2012 25th SIBGRAPI Conference on., pp. 63-2012.
E. D. Demaine, M. L. Demaine, "Jigsaw puzzles edge matching and polyomino packing: Connections and complexity", Graphs and Combinatorics, vol. no. 1, pp. 195-208, 2007.
D. Bartoněk, "A genetic algorithm how to solve a puzzle and its using in cartography", Acta Scientiarum Polonorum. Geodesia et Descriptio Terrarum, vol. 4, no. 2, pp. 15-2005.
S. Z. Kovalsky, D. Glasner, R. Basri, "A global approach for solving edge-matching puzzles", SIAM Journal on Imaging Sciences, vol. 8, no. 2, pp. 916-92015.
F. M. Toledo, M. A. Carravilla, C. Ribeiro, J. F. Oliveira, A. M. Gomes, "The dotted-board model: a new mip model for nesting irregular shapes", International Journal of Production Economics, vol. 1no. 2, pp. 478-487, 2013.
M. O. Rodrigues, F. M. Toledo, "A clique covering mip model for the irregular strip packing problem", Computers & Operations Research, vol. 87, pp. 221-22017.
S. MirHassani, A. J. Bashirzadeh, "A grasp meta-heuristic for two-dimensional irregular cutting stock problem", The International Journal of Advanced Manufacturing Technology, vol. no. 1–4, pp. 455-42015.
L. R. Mundim, M. Andretta, T. A. de Queiroz, "A biased random key genetic algorithm for open dimension nesting problems using no-fit raster", Expert Systems with Applications, vol. pp. 358-32017.
A. M. del Valle, T. A. de Queiroz, F. K. Miyazawa, E. C. Xavier, "Heuristics for two-dimensional knapsack and cutting stock problems with items of irregular shape", Expert Systems with Applications, vol. no. pp. 12589-12598, 2012.
D. Dalalah, S. Khrais, K. Bataineh, "Waste minimization in irregular stock cutting", Journal of Manufacturing Systems, vol. no. 1, pp. 27-2014.
M. Fischetti, I. Luzzi, "Mixed-integer programming models for nesting problems", Journal of Heuristics, vol. no. 3, pp. 201-22009.
R. Alvarez-Valdes, A. Martinez, J. Tamarit, "A branch & bound algorithm for cutting and packing irregularly shaped pieces", International Journal of Production Economics, vol. 1no. 2, pp. 463-42013.
A. M. Gomes, J. F. Oliveira, "Solving irregular strip packing problems by hybridising simulated annealing and linear programming", European Journal of Operational Research, vol. 1no. 3, pp. 811-82006.
K. A. Dowsland, S. Vaid, W. B. Dowsland, "An algorithm for polygon placement using a bottom-left strategy", European Journal of Operational Research, vol. 1no. 2, pp. 371-32002.
B. Baran, B. Dogusoy, K. Cagiltay, "How do adults solve digital tangram problems? analyzing cognitive strategies through eye tracking approach", Human-Computer Interaction. HCI Intelligent Multimodal Interaction Environments. Springer, pp. 555-52007.
E. Esicup, Special interest group in cutting and packing, 2007, [online] Available: https://www.euro-online.org/websites/esicup/data-sets/.
Publicado
28/10/2019
Como Citar
YAMADA, Fernanda M. ; GOIS, Joao; BATAGELO, Harlen C. .
Solving Tangram Puzzles Using Raster-Based Mathematical Morphology. In: CONFERENCE ON GRAPHICS, PATTERNS AND IMAGES (SIBGRAPI), 32. , 2019, Rio de Janeiro.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
DOI: https://doi.org/10.5753/sibgrapi.2019.9791.
