OEIS/Tilings

From tehowiki
Revision as of 21:20, 11 May 2020 by imported>Gfis (Example)
Jump to navigation Jump to search

Generating functions of coordination sequences

New format

On May 02 2020 Brian Galbach wrote:

Here's a new file with a very compact and simple code for each tiling. It has several sections separated by semicolons, which I will explain below.

Each code starts with a single capital letter representing the uniformity of the tiling. A is 1-uniform, B is 2-uniform, etc.

Next, we have a letter representing the vertex type for each vertex class in the tiling. These are as follows: 

A: 3.3.3.3.3.3
B: 3.3.3.3.6
C: 3.3.3.4.4
D: 3.3.4.3.4
E: 3.3.4.12
F: 3.3.6.6
G: 3.4.3.12
H: 3.4.4.6
I: 3.4.6.4
J: 3.6.3.6
K: 3.12.12
L: 4.4.4.4
M: 4.6.12
N: 4.8.8
O: 6.6.6

Following the vertex type designations, we have alternating sections:

The first section describes the classes connected to class A. The number of connections must of course be the same as the number of polygons in class A. And each connected class must be from A to the nth letter of the alphabet, where our tiling is n-uniform. (Important: Do not confuse the vertex type, which is A to O, with the vertex class, which is A, B, or C in a 3-uniform tiling, for example.)

The second section describes the orientation of each of those vertices connected to class A. The letter, whether it is uppercase or lowercase, gives us the edge of the connected vertex that is connected to the current edge. A or a is the first edge, B or b is the second edge, etc. And uppercase means that the direction of rotation of the connected vertex is the same as the current vertex, while lowercase means that the direction of rotation is reversed.

Then we repeat the above two sections for class B, class C, etc.

That's it. Let's do an example just so this is clear. I'll pick a line pretty much at random. Okay, this one: 

C;FJO;BABC;BBAA;AABB;CADC;ACC;DCB

So we have a 3-uniform tiling (C). The three vertex classes have the vertex types 3.3.6.6, 3.6.3.6, and 6.6.6 (FJO).

Now let's look at vertex class A. It has connected to it vertex classes B, A, B, and C. And the edges connected from each of those vertices are edge 2, edge 2, edge 1, and edge 1. And since these are all uppercase letters, there is no reversing of the direction of rotation relative to the direction of our central vertex.

Class B has connected to it vertex classes A, A, B, and B. And the connected edges are edge 3, edge 1, edge 4, and edge 3, and no direction reversal.

Finally, class C has connected to it vertex classes A, C, and C. And the connected edges from each of those vertices are edge 4, edge 3, and edge 2.

Simple algorithm

Step 1

Start with a vertex in the center. By default, it can be class A, position 0, rotation 0, flip 0 (going counterclockwise). Every vertex you store should have a class, rotation, and a flip. (But the rotation and flip are not necessarily uniquely determined since the tiling may have some symmetries that allow various values with the same resulting tiling. This is unimportant though, as long as you store only one possible rotation and flip for the vertex.) So to start, you have (1,0,0,0) for class A, 0 position, rotation 0, flip 0. If you want to instead start with class B at position 2+3i, rotation 90 degrees, and rotating counterclockwise around the origin, then store (2,2+3i,90,1) instead. You'll end up with the same tiling regardless, just positioned and oriented differently.

Step 2

Now as you step through each vertex currently in the tiling, you calculate new potential vertex locations based on the class, position, rotation, and flip of the vertex. Say we have a 4.6.12 vertex, position 1+i, rotation 60, flip 1 (clockwise). Then our three potential new locations are 1+i + (e^(i * (60, 330, 210)/180*pi))). (The first is at 60 degrees a unit away from the vertex location, the second is at 330 degrees, which is 90 degrees clockwise away from 60 (square), and the third is at 210, which is another 120 degrees clockwise (hexagon).)

Shells

Now, here's a trick I learned from reading about how others calculated coordination sequences. Have "shells" that can store the first and last vertex you create in each step away from the original vertex. At the start, have the two shells (1,1) and (1,1). When you calculate the connected vertices from the central vertex, you'll define the third shell as the minimum and maximum new vertex you create. So say your central vertex is 3^6. Then your next shell will be (2,7) since you've created six new vertices. Now after you complete each step away from the vertex, throw away the first of your three shells.

So you had (1,1) and (1,1), and then created (2,7) for three shells. Throw away the first one so now you have (1,1) and (2,7). Now in the next step, you find each of the vertices connected to each of vertex 2 through vertex 7. Each time you calculate a new vertex location, compare it against the locations of the vertices in your two previous shells. If you get a new location, that's a new vertex. Let's assume we find 10 new vertices in this step. Then our next shell will be (8,17). Throw away (1,1) to now have just (2,7) and (8,17). (The whole purpose of this is to save much computation time as the number of vertices grows, since you don't have to compare a new potential vertex against all previous vertices, but rather only the vertices from the last two shells.)

Step 3

Now, every time you find a new vertex location that's different from anything you had before, you must calculate and store its new class, location, rotation, and flip. These are as follows:

3.c

CLASS: This is simple. Just use the class given in the code.

3.l

LOCATION: Again simple. Just use the location calculated in the step 2.

3.f

FLIP: This will be the exclusive or (xor) of the flip of the current vertex and the flip specified in the code. So take our above 4.6.12 example. Since our current vertex is flipped, then if we have a new connected vertex that is specified as being flipped (lowercase in the code), then that vertex will now be NOT flipped (0), or counterclockwise. So say our three connections are lowercase, uppercase, lowercase (0,1,0 flips). Then the connected vertices will be 1, 0, 1 (flipped, not flipped, flipped).

3.r

ROTATION: This is the trickiest one to get right. It depends on the angle of the current vertex edge we're using to get to the new vertex, the flip orientation of the new vertex, and the angle of the edge connected from the new vertex. Let's define the following variables: 

A1 = Angle of the current edge
F = Flip orientation of the new vertex
a2 = Angle of the new vertex connected edge relative to default position

A1 was calculated in step 2 when we were finding the new vertex location. So just use that value. For example, if we're looking at the vertex connected to edge 2, that's at angle 330 degrees. F was calculated in step 3.f as the exclusive or of the current vertex flip and the connected flip from the code. So again in our example, we'd be looking at xor (1,1) = 0 so not flipped (counterclockwise). a2 is the rotation of the particular edge of the new vertex if it were in default position. So for example, if the connected vertex type is also 4.6.12, the default angles are 0, 90, and 210. If we're connecting edge 2 of the new vertex, then a2=90.

Now the rotation R of the new vertex is as follows: 

R = A1 - (1-2*F) * a2 + 180

The reason for the 180 degree addition is because as we're going out of the current vertex along the edge, we're going along the same edge in the opposite direction from the new vertex.

So in our example above, R = 330 - (1-2*0) * 90 + 180 = 330 - 90 + 180 = 420. Mod by 360 to get R=60.

Step 4

Store all of the edges. In step 3, you only need to compute class, location, rotation, flip for a new vertex location. Whether or not you've hit a previously calculated location, you still can create a new edge in the tiling. To not duplicate edges, only store an edge if the new vertex really is new, or if the current vertex ID is lower than the previously created new vertex ID.

Step 5

Iterate steps 2, 3, and 4 for as many steps (shells) as you like. Or if you want to fill a rectangular region, simply store only the points that are within that rectangle. Eventually, all new vertices will be outside the box, and then you stop.

Retrieved from "http://teherba.org/tehowiki/index.php?title=OEIS/Tilings&oldid=655"