A heuristic for solving tangram puzzles through raster representation and mathematical morphology.
O tangram é um quebra-cabeça de dissecação composto por peças poligonais que podem ser combinadas para formar diferentes padrões. Além de ser um quebra-cabeça recreativo, o tangram se relaciona a uma classe mais geral de problemas combinatórios NP-difíceis, como o problema do corte bidimensional. A maioria dos métodos atuais aplicados à solução automática do tangram é incapaz de representar padrões que não são descritos por um único contorno fechado sem furos. Além disso, a maioria dos métodos apresenta limitações nas transformações aplicadas nas peças, restringindo os ângulos de rotação e não implementando a transformação de reflexão. Neste estudo, atacamos essas limitações através da introdução de um método heurístico que usa uma representação raster do quebra-cabeça. De modo a adaptar as técnicas geométricas que são aplicadas na prevenção de sobreposições e na redução do espaço entre as peças, utilizamos representações e operadores morfológicos tradicionalmente aplicados no domínio discreto tais como o operador de dilatação, a transformada de distância e a esqueletonização morfológica. Investigamos os efeitos da representação raster no processo de montagem do quebra-cabeça e verificamos a eficácia do método proposto na resolução de diferentes quebra-cabeças de tangram.