The Tangram Game and Its Algorithmic Potential
Currently, such permutation games are only becoming more diverse. For example, the Mechwood company operating in Novosibirsk offers wooden setsamong which, along with tangram, the games “pentamino”, “circum”, “Columbus egg” and even “tag” are offered.
Note that there is a symmetry in the Circum and Columbus Egg that is not present in the Tangram. Thus, the tangram is one of the simplest puzzles of its kind, but still allows for hundreds of informative configurations. At the same time, the tangram differs significantly from three-dimensional construction sets, in particular LEGO and Meccano, since the number of combinations in a tangram, although large, is strictly limited, which means it can be algorithmized. Below I will briefly review some successful attempts at such algorithmic applications of the tangram.
Tangram as an algorithmic method
The problem of automatically composing tangram figures belongs to a broader class of NP-hard problems, called “Cutting and Packing” (C&P) in English-language sources, and “in Russian-language sources”geometric covering problems” or “tasks of one-dimensional cutting of materials” At the same time, tasks for composing tangram figures can be divided into simple and complex. The first ones come down to the operations of translation and rotation, and the rotations must be multiples of 45° – and as a result we have a figure covering a continuous area of the surface. When solving complex tangram problems, we obtain figures that have at least one of the following characteristics: 1) the presence of several connected sections, 2) the presence of voids (holes) in the mosaic, 3) the need to arbitrarily freely rotate the figures, 4) the need for a mirror transformation of the parallelogram.
To solve tangram problems, the machine must be guided by rules that characterize both the properties of individual polygons (in this case, triangles, squares, and parallelograms) and the combination of polygons when their orientation changes. For example, at the level of axioms it should be taken into account that two small right triangles form a square, and two large right triangles can form a rectangle as a special case of a parallelogram, but in this case an ordinary parallelogram in a tangram set always remains alone, since to obtain a second such parallelogram obtuse-angled triangles, but we don't have them. Tangram problems are also useful for analyzing symmetry, finding negative space, and identifying loose shapes. Detecting loose shapes is also associated with an optimization problem called “finding frozen holes.” A fatal gap is a shape that clearly does not match any of the remaining parts or combination of them, and such a gap must be ignored to improve the performance of the algorithm. The above principles formed the basis of the algorithm “Tangram and Glue» from Google, used to solve the following problems:
Optimization: iterative and geometric operations, with the help of which the most advantageous location and complete fit of figures is selected.
Computational Geometry: An algorithm used for automatic shape manipulation involving the rearrangement of shapes to produce one solid path from another solid path.
It turns out that this algorithm and others like it are used in graphic design, architecture, as well as in artificial intelligence tasks, for example, when selecting search results.
Tangram in conveyor assembly
In 2022, Shuo Qin from Wuhan Institute of Technology offered Using tangram as an abstract symbolic system to simplify robotic assembly line technology. When a manipulator operates based on sensor (camera) data, the most difficult part of the task is to install the parts in the correct order and with the correct mating. This problem can be reformulated in terms of tangram if the algorithm takes into account the bottom edges (bases) of the part as figures on a plane. In this case, the manipulator first receives information about the shape of the part to ensure proper grip, then information about what the partially assembled mechanism at this stage of assembly looks like, and then, guided by tangram-like principles (probably also similar to the principles of Tetris), installs the part exactly at the required point and in the required position. A computer model proposed by Qin demonstrates the assembly line technology of a complete tangram square, as well as stylized animal figures, such as a cow. The order of operation is as follows:
A tangram figure is randomly generated on the conveyor belt. As soon as the figure reaches the end of the conveyor, the conveyor stops and sends a signal to the manipulator to start working. Then the manipulator is turned on, the task of which is to remove the figure from the conveyor and install it correctly.
The visual sensor reads the color and contours of the incoming part and determines which of the seven tangram elements it is dealing with.
The manipulator works. In accordance with the color and shape of the part determined in the previous step, this part is installed in a position that corresponds, firstly, to the shape of the figure, and secondly, to the general outlines of the drawing according to which we assemble the figure (whether it is the original full square of the tangram or a more complex figure).
After seven such operations, it is checked whether the assembled figure corresponds to the given drawing. After this, a signal may be received either to correct the figure, or to analyze it, or to collect the next figure.
When using this method, you can correlate an arbitrary part with a tangram figure in the computer memory and indicate what other parts it should be combined with, what color marker it corresponds to, how many such parts are in the set, and what positions this part cannot occupy under any circumstances . In this case, the manipulator can operate with a relatively simple camera and is less dependent on problems associated with possible misinterpretation of figures.
Tangram for solving visual microtasks
Also in 2022, a group led by Yuzhou Zhao from UCLA suggested use tangram-based algorithms to solve problems related to calculating the folding of flexible figures and the arrangement of elements within a contour. The computer vision algorithm is first trained on tangram figures and their combinations, and then receives a more complex dataset as input, which represents various categories of objects:
As a result, the algorithm learns the rules of symmetry and can be trained on small samples (few-shot learning), since it draws a figure according to the rules of symmetry and, ultimately, reduces it to tangram-like figures. For example, you can tell the algorithm that all of the following items are clothes, but the two silhouettes on the left are dresses (based on symmetry), and the two on the right are not:
Here is a reverse decomposition of clothing silhouettes into their constituent figures:
Finally, tangram-like methods are effective in generating layouts, selecting options for arranging objects (including furniture), as well as in generating scenes in computer games and simulators. These research are also conducted by scientists of Chinese origin at the University of California, Los Angeles. The tangram-like approach allows for algorithmic compactness and reconfigurability indicators. Moreover, a scene can include several levels of detail (for example, at the object level and at the texture level), where each layer can be analyzed separately, but still comes down to a set of simple shapes, between which clear rules of compatibility apply.
To complete the picture, I will mention a couple more developments:
The Mapzen tool allows you to generate various landscapes using the Tangram principle, which take into account both the height and illumination of each point on the terrain.
Here a selection of examples.
Tangram researcher Brett Camper of New York offers use tangram-like algorithms to procedurally generate maps that automatically delineate built-up and undeveloped areas.
Conclusion
It can be assumed that the classic tangram and extended sets of similar figures significantly simplify the solution of non-trivial geometric problems, when working with both computer simulations and physical objects. Tangram simplifies not only the assembly, but also the disassembly of objects, allowing for reliable modeling of complex objects based on simple figures and rules. I will also assume that the development of tangram-like algorithms can lead to the development of algorithms and devices for simulating facet vision, which, unlike the natural facet vision of insects, can rely on powerful neural networks and on the rapid classification of images and objects depending on their geometric similarity.
