T-Pattern V1.0
The seven basic shapes are combined to form different planar shapes. The most optimal form is to obtain a square shape by combination in terms with the "Tangram" game rules. The computer program was designed with MATLAB in 3 main sequential functions, including gridding the targeted canvas, which we want to fill with sets of 7-piece tangram, searching potential module and matching the modules to find out solutions.
Generated Patterns
1. Basic concepts
(1) Definition of convex polygon
A convex polygon is defined as a polygon with all its interior angles less than 180°. This means that all the vertices of the polygon will point outwards, away from the interior of the shape. Thus, there exists some features that we can judge if a polygon is convex. 1) A line drawn through a convex polygon will intersect the polygon exactly twice. 2) All the diagonals of a convex polygon lie entirely inside the polygon. And, as you can see, a 7-piece tangram actually consists of 7 convex polygons including 5 triangles, 1 rectangle and 1lozenge. To be consistent with computer programming, here in figure 1 we define the module 1, 2, …, and 7 associated with the relative convex polygons.
(2) Definition of basic triangle
A basic triangle in a 7-piece tangram is defined as a right triangle with the length of its two leg 1 and its hypotenuse 2. Thus, we will find that a 7-piece tangram can be divided into 16 identical basic triangles. And all the related modules actually consist of the different number of basic triangles, as shown in figure 1.
Fig. 1 Basic concepts illustration in a 7-piece tangram
2. Program design
The computer program was designed with 3 main sequential functions, including gridding the targeted canvas, which we want to fill with sets of 7-piece tangram, searching potential modules and matching the modules to find out solutions. The specific steps are designed as follow.
(1) dividing the canvas and generating the dot matrix (coordinate points), shown in figure 1, according to the both sizes of the canvas and basic triangle.
(2) searching each point (coordinate point) and its related surrounding points, which can be formed as module n (n = 1, 2, …, 7), to find out the potential modules.
(3) detecting the collusion among all the sets of potential tangram to determine the options. The corresponding program flow chart is shown in figure 2 in terms of the thought above.
Fig. 2 Program flow chart
3. Collusion detection for modules
The separating axis theorem (SAT) says that if two 2D convex polygons don’t intersect, then there exists some line (known as a “separating axis”), such that when the polygons are projected onto that line, the projections of the two polygons will not overlap. Here are two non-overlapping polygons, shown in figure 3. The blue line is a separating axis for these two polygons, because the projections of the polygons onto that axis do not overlap. A separating axis is really just a direction (we would describe the axis as a vector). And translating the axis does not affect the polygon projections. We now have a strategy for detecting the overlap of 2D convex polygons. Scan all the edges of both polygons. For each edge, we form a candidate separating axis that is perpendicular to that edge.
Fig. 3 SAT illustration
Fig.4 Four separating axes for detecting collusion (intersecting) in tangram program
One more question is how do we represent that projection, in such a way that we can tell if the projections overlap? The dot product is the answer. Let’s translate our axis so that it contains the origin. (We said that this does not change whether the projections overlap.) Now we can describe the projection of any given polygon vertex onto this axis by giving the signed distance from the projected vertex to the origin. This distance just so happens to be precisely what we get when we dot the vertex with a unit vector parallel to the axis, which we call v. The dot product gives us a tool to describe the projection of a polygon onto each candidate separating axis v. For each polygon vertex, we take the dot product of the vertex with v, which gives us a signed distance from the origin. We collect the minimum and maximum of these distance, which gives us the extents of the projection, labeled amin and amax in figure 3. In the specific case of 7-piece tangram, we can find that there are 4 separating axes, which are x = 0, y = 0, y = x and y = -x respectively shown in figure 4, for detecting if all the polygons (modules) are intersecting.
4. Interpretation of program
The program was coded with a number of specific functions to find out the options of matched tangram, starting with main program, interpreted as follow.
/**********************************************************************
clear; clc; // clearing the memory
/**********************************************************************
length_tg = sqrt(2) * 2; // length of targeted canvas
width_tg = sqrt(2) * 2; // width of targeted canvas
length_sd = 1.0; // length of basic triangle’s leg
// generating the gridding points (coordinate points)
points = basic_pts_generating(length_tg, width_tg, length_sd);
// number of points in row and column
M = size(points, 1);
N = size(points, 2);
ratio_area = (M - 1) * (N -1) / 16;
// finding the potential modules, note that m2 and m5 are actually identical to m1 and // m4 respectively
m1 = module1_searching(points);
m3 = module3_searching(points);
m4 = module4_searching(points);
m6 = module6_searching(points);
m7 = module7_searching(points);
// determining the eventual options
options = puzzle_matching(m1, m3, m4, m6, m7, ratio_area);
// saving the options as mat format designed by MATLAB
save options options;
// plotting the options using files test.m and test2.m, and all the sub-functions are annotated, please go ahead to the program getting // more detailed information …
8 Combinations