This project aims to implement a function to grow a given hat tile cluster automatically. At first, some reduction about specific vertex configurations are deducted to filter possible cases. Then, a multiway grow function is implemented to study some special hat tile clusters. A dynamic module showing the grow process of cluster is implemented to illustrate the procedure with clarity. Additionally, a function with a fast algorithm to find all special subclusters in a big super-tile is obtained. The next step is to use more local vertex information to improve the growth algorithm, which will be useful to study the hat tile space.
Hat Tiling
Hat Tiling
The hat tile is an aperiodic monotile, which can fill the whole infinite two-dimensional plane without translation symmetry. It looks like a “hat”, or a “t-shirt”.
GraphicsRowshow[{{0,0},0,False,0},ImageSize->Small],show[{{0,0},0,True,0},ImageSize->Small],show
Out[]=
The left two figures are single hat tiles with different parity and right one is a cluster, which can cover the whole plane after using substitution rules. Here, however, we are trying to implement a grow function rather than substitution rule to generate a hat tiling cluster. The first step is to study the vertex configurations of hat tiles and discover how they fit together.
Vertex Configuration Study
Vertex Configuration Study
In order to implement a grow function to generate valid and promising tiling patterns, it’s important to reduce as many invalid vertex configurations as possible. There are four different angles of a hat tile; if we take 2π as unit, then the angles are 1/4, 1/3, 2/3 and 3/4. Starting from the bottom concave vertex, we number each vertex from 0 to 12. There are several configurations for hats to meet and fill a point on the plane - 1/4+1/4+1/4+1/4, 1/3+1/3+1/3, 1/3+2/3 and 1/4+3/4. Additionally, there is a notable 1/2+1/4+1/4 vertex configuration with a characteristic “T” structure if we regard an edge as a 1/2 vertex. The 1/3 vertices combination has been studied by Brad Klee - https://community.wolfram.com/groups/-/m/t/2935078. We use black and brown to represent reflected hats, and yellow and blue for unreflected hats.
First, some preparations are needed for the convenience of future study.
First, some preparations are needed for the convenience of future study.
Fundamental Code
Fundamental Code
Preparation Analysis
Preparation Analysis
Intersection Test
Intersection Test
First, an efficient intersection test method is needed to create a table recording all intersections of two hats sharing a vertex . I used Internal Line Test, Area Test to build the table twice, and finally, choose the algorithm and code by Brad Klee to double-check and improve the table.
In[]:=
fixedHat[n_]:={{0,0},0,False,n};moveHat[rotation_,ref_,pt_]:={{0,0},rotation,ref,pt};
Only considerate two hats, one is fixed and the other can move around the first one at different vertices and angles, parity as well. We can the fixed hat shift different vertex to intersection with the other one, but it’s rotations and parity is fixed. And we change the state of the other one. What matters is the rotation angle difference and parity difference between these two hats, many cases can be reduced. Let them meet at point (0,0). And a intersection test function is needed:
In[]:=
planarTest[hat1_,hat2_]:=With[{res=Length/@PlanarPolygonFragmentation@@(hat@@@{hat1,hat2})},If[hat1==hat2,False,res==<||>||Total[res]==3]]
In[]:=
testForTable[n_,rotation_,ref_,m_]:=planarTest[fixedHat[n],moveHat[rotation,ref,m]]
All possible cases of two hats are as following:
GraphLayout
allcasesForIntersectionTable=Tuples[{Range[0,12],Range[0,11],{False,True},Range[0,12]}];allcasesForIntersectionTable//Length
Out[]=
4056
However, there are some way to reduce these cases, by regard state of (n, rotation, ref, m) as a dual state of (m, r/-r, ref, n) where if ref == False then we take r, otherwise -r because of the reflection. So we can reduce almost half of the cases.
In[]:=
allcasesForIntersectionTable=Outer[{#1[[1]],#2[[1]],#2[[2]],#1[[2]]}&,Flatten[Table[{j,i},{i,0,12},{j,0,i}],1],Tuples[{Range[0,11],{False,True}}],1];allcasesForIntersectionTable=SortBy[Flatten[allcasesForIntersectionTable,1],(((((#[[1]]*13)+#[[2]])*2)+Boole[#[[3]]])*13+#[[4]])&];
AbsoluteTiming[IntersectionTable=testForTable@@@allcasesForIntersectionTable;]
Out[]=
{61.5302,Null}
Then we have a table recording all intersection cases. When we have two hats sharing same vertex as pt, {pt, n, , } and {pt, m, , }, we have to transform the their codes into the above format and look up the table.
dir
1
p
1
dir
2
p
2
In[]:=
IntersectionTable=;getIndexforIT=First[First[Position[allcasesForIntersectionTable,{##}]]]&;checkIntersectionTable[n_,r_,ref_,m_]:=IntersectionTable[[getIndexforIT[n,r,ref,m]]]/;n<=mcheckIntersectionTable[n_,r_,ref_,m_]:=IntersectionTable[[getIndexforIT[m,If[ref,r,Mod[-r,12]],ref,n]]]/;n>m
Since the two hats we check must share the same vertex in their code, so we need to check and transform them.
In[]:=
findEqualHat[pos_,hatstate_]:=With[ p = Simplify[pos], With[{position = Position[Simplify[hatVertices@@hatstate],p]}, If[ position === {}, hatstate, {p,hatstate[[2]],hatstate[[3]],First[First[position]]-1}] ] ]
Then, by the previous analysis, transform the code and check the table:
In[]:=
checkIntersectionofTwoHats[reference_,test_]:=Module[ relative=findEqualHat[reference[[1]],test], If[relative === reference, Return[False]]; checkIntersectionTable[ reference[[4]], If[ Xor[relative[[3]],reference[[3]]], Mod[relative[[2]]+reference[[2]],12], Mod[relative[[2]]-reference[[2]],12]], Xor[relative[[3]],reference[[3]]], relative[[4]]]]
Then we can visualize the result, the following is part of the table:
Grid[Partition[Labeled[show[{fixedHat[#1],moveHat[#2,#3,#4]},ImageSize{100,100}],Style[checkIntersectionofTwoHats[{{0,0},0,False,#1},{{0,0},#2,#3,#4}],Bold,Italic,Purple],Bottom,ContentSize{100,100}]&@@@Tuples[{{8,10},{0,1,2},{False,True},{8,10}}],6],FrameAll,FrameStyleLightGray]
In this table, only when two hats do not intersection and do not form a hole, the result is True.
Angle Analysis
Angle Analysis
Generating all cases then checking intersection to delete is inefficient. However, there is a way to reduce some cases at the beginning. This idea is from Brad Klee, who use twelve points around a vertex of hat and number each of them, and by which points are in the hat and which are not, we can easily distinguish hats with different angle and state at a point.
The reason we do it is that there are only 12 directions for all edges of a hat:
The reason we do it is that there are only 12 directions for all edges of a hat:
Number each point from 1 to 12, it is easy to see the angle state at a certain point.
It is easy to get an association for each vertex and its point occupation.
It’s enough to analyze when some hats meet at on point at vertices, but this is some case when two hats meet at the mid-point of an edge of another hat:
So it is necessary to calculate the angle occupations by edges in different directions. As we discussed before, there are only 12 directions for any edge, they are:
Then, build the function for getting angle configuration of edges:
With this tool, many invalid cases would not be generated at first which improves the efficiency significantly.
Obvious Invalid Cases
Obvious Invalid Cases
There are some obvious invalid cases, which were derived during the study. A summary table is helpful to filter possible cases.
Some of them are shown as following:
1/4 + 3/4 Vertex Configuration
1/4 + 3/4 Vertex Configuration
Get all 1/4 vertex and 3/4 vertex, combine them and delete intersected and invalid cases. Only 8 of them survived.
Consider reflection, the fourth and seventh can be reflected.
1/3 + 2/3 Vertex Configuration
1/3 + 2/3 Vertex Configuration
Same as before, generate promising candidates and filter, only 10 of them survived.
1/4+1/4+1/4+1/4 Vertex Configuration
1/4+1/4+1/4+1/4 Vertex Configuration
Get all 1/4 vertices and all states of one hat.
Group all state by its angle occupation:
Create some temporary functions for the convenience of analysis:
Then, imagine a point waiting to be filled, add hats one by one:
◼
First Hat
First, create all possible cases where this is only one hat.
Check intersection table to filter cases:
◼
Second Hat
Now, add the second hat. Organize the previous result first:
Apparently there are many obvious invalid cases need to be deleted. The least angle of a hat is 1/4, which corresponds to 3 points, so if the points left which are divided into small continuous pieces any of whose length is smaller than 3, it must be invalid. So I build a function to cluster points from 1 to 12:
Then, select those with valid continuous points:
Organize the result again, and get its available angle points:
◼
Third Hat
Now let’s add the third hat there:
There are many intersected cases need to be reduced, which took a while:
Now we can see, some points have been filled already, which is not really occupied by four 1/4 vertices that remains some impossible gap. So they are need to be deleted:
◼
Fourth Hat
Now comes to the last hat. Build all possible cases first:
Since it takes 6min to finish calculation, the result is iconized as following:
Now, we need to delete all know invalid cases, which took much longer time:
Result is iconized below:
From the result, there are many cases who are reflected or rotated to each other, now reduce them:
Canonize the result, make unreflected hats to be majority.
1/4+1/4+1/2 “T” Configuration
1/4+1/4+1/2 “T” Configuration
There is a special way for three hats to fill a point on the plane. Two hats meet at the middle point of another hat’s longest edge, forming a “T” shape configuration.
First, choose a hat as “edge hat” and add two more to meet at the middle point of its edge.
First, choose a hat as “edge hat” and add two more to meet at the middle point of its edge.
Here, we can build a simple grow function with previous vertex configuration conclusions, which would be easily and fast to get few promising cases. However, implement this kind of grow function will occupy too much space for new code, so I choose to use intersection test from Brad Klee to filter cases, which is also fast enough.
There are many impossible cases which can be deleted by eyes looking easily as well as by angle points method.
The fixed hat occupies half of the points of the upper half plane. The available angle represented by points is a set of {7,8,9,10,11,12}. Then get each point occupation of res1 to generate corresponding possible cases.
The fixed hat occupies half of the points of the upper half plane. The available angle represented by points is a set of {7,8,9,10,11,12}. Then get each point occupation of res1 to generate corresponding possible cases.
Then use intersection test by Brad Klee to filter cases.
Delete same hat tile but different order of codes:
Only 19 cases which are easily tested by looking. Only case 2,3,4,15 are promising.
According to the An aperiodic monotile by David Smith, the third one shows up as its reflected version. So there we change it into its reflected version, too.
The result is:
The result is:
Conclusion
Conclusion
Vertex configurations summary:
Grow Cluster
Grow Cluster
Multi Growth Tree
Multi Growth Tree
From H2 to H7/H8
From H2 to H7/H8
Take a two hat tile, which is denoted by H2. Then, we can find a way to grow it to H7, which is a meta-tile constructed from seven hat tiles. If we put all possible hats along the boundary point of H2, a multiway growth tree will be obtained.
The result would be huge and would take 20 min to evaluate. Following is the iconized result to avoid this tedious evaluation:
Find all possible paths from H2 to H7 :
The two leaves on the low left side includes H7, and the lower subtree on right hand side all include H7. Then, from H7, it is forced to get H8.
From Symmetric 11,11,11
From Symmetric 11,11,11
11,11,11 is the second to last vertex configuration of 1/3+1/3+1/3. This kind of configuration does not appear in any cluster, so here I try to prove it is invalid.
If a tile cluster is invalid, then its multiway growth tree is finite, which means it cannot grow to cover the whole plane without any holes.
The first step is to fill the three concave vertices, choosing points at the deepest position of each concave vertex.
If a tile cluster is invalid, then its multiway growth tree is finite, which means it cannot grow to cover the whole plane without any holes.
The first step is to fill the three concave vertices, choosing points at the deepest position of each concave vertex.
If the tree is finite, it will take considerably long to reach a fixed state . Otherwise, if it is infinite, it will never converge on a fixed state.
A example multiway tree is shown as following:
A example multiway tree is shown as following:
When the tree grows deeper, the number of concavities on the boundary gets larger. However, many of the gaps are not possible to fill. So this tree is finite, i.e. 11,11,11 vertex configuration is invalid.
From Symmetric 6,10,6,10
From Symmetric 6,10,6,10
6,10,6,10 is the fourth result of the 1/4 vertex conclusion, which doesn’t appear in the big cluster and seems to be invalid. Here I try to grow it and prove invalidity.
Then we try to grow it.
The leaves seem to grow into a straight diagonal line with 2-hat width cutting the whole plane into two parts. There are no obvious invalid cases appearing here.
Here we try to grow more points on the boundary simultaneously.
Here we try to grow more points on the boundary simultaneously.
So far there are no obvious dead ends, which means the multi-growth tree of 6,10,6,10 is quite large, potentially infinite. If invalidity is to be proved, the tree will need to be larger and deeper. However, with branches growing more and more, the computation would be much too time-consuming to be practical.
Find Subclusters
Find Subclusters
Examples
Examples
H7 and H8 are important meta-tiles, which are the base of substitution rule. There is a good way to find out all subclusters in a big cluster, or super-tile.
Here is a massive cluster, which are made up of 169 hat tiles.
Here is a massive cluster, which are made up of 169 hat tiles.
The idea is to give each edge a tag from 1 to 13, and record the special order of H7 and H8 boundary tags and their edge vectors (which are easily obtained from its topologic graph).
There is a easy way to find subclusters by the built-in function FindCycle, as long as we know the edge tags sequence. These are unique enough for each sub-cluster.
Notice that every H7 or H8 has a reflected hat in its center. Imagine walking from the 6th vertex of the reflected hat - the top point of the black tile - along the boundary, and it is easy to get the tag sequence of boundary edges.
Given the length, it is easy to find the cycle:
Notice that every H7 or H8 has a reflected hat in its center. Imagine walking from the 6th vertex of the reflected hat - the top point of the black tile - along the boundary, and it is easy to get the tag sequence of boundary edges.
Given the length, it is easy to find the cycle:
Additionally, each vector of the boundary edge can be recorded to nail down the problem, and find all cycles faster.
From 4 Hat Tiles to Super-tile
From 4 Hat Tiles to Super-tile
It is surprised that, with grow function and growth tree, a path from the second and last case of vertex configuration 1/4+1/4+1/4+1/4 to the H7/H8 super-tile is found, which is generated with vertex configurations rather than substitution rule.
The dynamic growth is shown as following:
The dynamic growth is shown as following:
As for the other three cases, they do not appear in any big clusters so far, which is potentially eventually invalid. To prove their invalidity is a part of the work in the future.
Concluding remarks
Concluding remarks
In summary, a fundamental growth function for the hat tile is obtained, which is fast enough to generate all possible valid and promising cases for a given cluster at a given certain point. Also, a multiway function is implemented to further study growth branches of a certain hat tile cluster.
However, the algorithm is only built on the information of one point, which is extremely local and limited. If growth is from all points on the boundary, the time-consumption is huge and the multiway tree is too complex to study.
The next step is to study the relationship between different vertex configurations, especially those who show up as neighbors in the big cluster. More information will generate less branches and make the multiway tree smaller and clearer.
However, the algorithm is only built on the information of one point, which is extremely local and limited. If growth is from all points on the boundary, the time-consumption is huge and the multiway tree is too complex to study.
The next step is to study the relationship between different vertex configurations, especially those who show up as neighbors in the big cluster. More information will generate less branches and make the multiway tree smaller and clearer.
Keywords
Keywords
◼
Hat Tiling
◼
Aperiodic
◼
Multiway Graph
Acknowledgment
Acknowledgment
I want to thank Brad Klee for his careful guidance and mentoring, who also provided us with the important function PlanarPolygonFragmentation. It is really enjoyable to work with Johannes. Thanks to Mark Greenberg for his help with graph layout codes and to Bob Nachbar for his help with pattern match codes. I’m glad to have met Zsombor Méder, Ben Peter, Russell Martinez and everybody in Wolfram Summer School. It is an unforgettable experience for me. Thanks!
References
References
◼
David Smith, Joseph Samuel Myers, Craig S. Kaplan and Chaim Goodman-Strauss, An Aperiodic Monotile, arXiv preprint, March 20, 2023.
◼
◼
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Hat tiling space reduction and grow function implementation
by Bowen Ping
Wolfram Community, STAFF PICKS, July 11, 2023
https://community.wolfram.com/groups/-/m/t/2957268
by Bowen Ping
Wolfram Community, STAFF PICKS, July 11, 2023
https://community.wolfram.com/groups/-/m/t/2957268