48k disk or cassette

The Magic Of Tesselations
-Part II

by Allan Moose and Marian Lorenz

The theme of distorting a basic tile shape as it is drawn in successive rows forms the basic idea behind many of M.C. Escher's drawings,

A tesselation or tiling is the complete covering of a flat surface by one or more figures in a pattern, with no overlapping of the figures and no open spaces. As we discussed last month, tesselations are commmonly found in linoleum patterns, parquet floors or fabrics.

    All of the tilings we discussed, and many of the tilings found around one's home, share the property of being periodic. A tesselation is periodic if you can shift the drawing without rotation or reflection to a new position where all outlines again fit exactly. While there are an infinite number of shapes that will tesselate periodically, periodic tilings by no means exhaust all of the possible ways to cover a plane surface. In this article we will present two programs that illustrate more intricate tilings. The first draws a non-periodic tiling that has rotational symmetry. The second covers the screen with tiles that are gradually deformed as each successive row is drawn on the screen.
    One of the charming things about the study of tilings is that it bridges the gap between art and science. Mathematicians have related tilings to group theory, which is the abstract study of symmetry. Physicists study tesselations to gain insights into the formation of crystals, and, of course, the famous artist M. C. Escher made frequent use of tilings in his work. In developing our programs we drew upon ideas from all of these fields. In particular, we have made use of the ideas of translation and rotation of coordinates as a way of writing short programs that you may easily modify.
    In order to illustrate tesselations with rotational symmetry, the basic tile used is a diamond which is based on a 30-60-degree right triangle.




    Previously, we introduced the use of a "local coordinate system" (LCS). The idea behind a LCS is that if you want to repeatedly draw the same figure on the CRT screen, the most efficient way to do it is to represent the coordinates o£ the vertices of the figure (points A,B,C,D in Figure 1) in terms of a hypothetical coordinate system. Then to draw the figure on the screen all you do is position the origin of the LCS where you want it and draw. In this way, the same subroutine can draw all the tiles you need.
    In the LCS, the coordinates of the vertices of Figure 1 are:

A = 0, 0
B = 17.32, -10
C = 34.64, 0
D = 17.32, 10

To make a tesselation with rotational symmetry, we want to draw this diamond in a circular pattern so that the first row will look like:



    The next circular row must fit around this design. The algorithm for generating the pattern can be simply stated as:

    READ, ROTATE, TRANSLATE.

    That is, for each diamond, no matter where it is, the program first reads the data numbers, then rotates the figure into the proper position, and then translates the vertex of the diamond to the proper location.
    With this background, you should be able to follow the program of Listing 1. This program creates three rows of diamonds (Figure 3). You may easily modify it to add a fourth. Be sure to include a clipping routine to avoid the dreaded "cursor out of range" error!



    Of course, you will want to experiment with more than just diamond tiles. An excellent place to start is with triangle tilings. The reason is that each tile can be changed by distorting the legs. For example, change


to


by nending each leg from



    Actually you can be more imaginative than this because a triangle can be distorted in an infinite number of ways to yield a figure capable of being used in a rotational tesselation.
    The theme of distorting a basic tile shape as it is drawn in successive rows forms the basic idea behind many of M. C. Escher's drawings. For example, birds might gradually lose their shapes and become checkerboarded fields of hay or even metamorphose completely into fish as in "Sky and Water 1." Our second program illustrates this gradual metamorphosis of one shape into another. In addition to being indebted to M. C. Escher for inspiration, we also must credit Douglas Hofstadter who, several years ago, devoted a column of "Metamagical Themas" in Scientific American to "Parquet Deformations."
    The basic idea is that simple geometric shapes which can tile the plane are slowly deformed as they move across or down the plane. Deformations may be created with a number of simple techniques such as:
1. Lengthening or shortening a line.
2. Introducing a "hinge" into a line segment so that it can flex.
3. Rotating a line or a group of lines that form a natural sub-unit.
4. Introducing a small "bump" or tooth into a line segment.
By using one of these techniques and allowing it to continue long enough, such deformations can have unexpected results; one outcome being that tiles at the end of the work bear little or no resemblance to those at the beginning.
    In order to keep our program simple, we restricted it to drawing a diamond and flexing the sides of the tile "in" or "out" to deform it. There are, of course, many other methods of deforming tiles, just as there are many other shapes that lend themselves to deformation. Here is a chance to exercise your creativity by building upon the ideas in this program.
    It is evident that drawing a tesselation in which the shape of the tile is changed before each row is drawn is more involved than simply drawing the same tile many times. We have approached this problem by introducing what at first

Physicists study tesselations to
gain insights into the formation of
crystals,

glance may seem like an unnecessary complication. First, we note that many shapes which can tile a surface have some sort of rotational symmetry. This means that if you rotate the shape around its center through some fraction of a circle (1/2, 1/3, 1/6, etc.) you get back the original shape. If this is the case, and it certainly is with the diamond, then we need only specify part of the shape, say two sides, and let the computer rotate that part as often as necessary to close the shape. You should visualize this rotation as taking place in the LCS. The rotation routine necessary to do this is the same as the rotation subroutine in Listing 1, lines 140 and 150. If we must rotate the part of the shape N times to produce a closed figure, then the angles through which we must rotate it are multiples o£ 360/N. Having constructed the tile in a LCS, it may be easily translated to the proper positions and plotted on the screen.
    Introducing the extra step of putting a tile together by rotation gives us a way to deform the tiles. Conceptually, deforming a tile is rather simple. Just take each side of the tile in turn, keeping the end points stationary, move the midpoint alternately in toward the center or out away from the center one unit at a time. The problem is in determining where to move the midpoint to. That is, given the coordinates of the end points, what are the coordinates of the point one, two, or three units closer to, or farther from the tile's center than the line's midpoint? If the line happens to be horizontal or vertical, then there is no problem. For example, a horizontal line's midpoint has the same ycoordinate as its end points. It has an x-coordinate equal to the average of the x-coordinates of the ends. Moving the midpoint toward or away from the center is a matter of moving it up or down. That is, the x-coordinate stays the same and the y-coordinate increases or decreases by one. If the line is diagonal we can still find the midpoint easily enough. However, moving it is the hard part, as the distance and direction of movement depend entirely on the inclination of the line segment.
    It would be much easier for the purposes of this exercise if we could make each side horizontal long enough to deform it and then put it back where it belongs. Fortunately, we already have the tools available to do just that-local coordinates and rotation. In mathematical terms we want to:

• Translate each line segment to the origin.



• Rotate it onto positive x-axis,



• Deform it as explained above.



• Rotate and translate it back into position.



    For us the procedure is as follows:
1. Take each of the defined sides in turn. Pick one end point and call it X1, Y1. Call the other end X2, Y2.
2. If we shift the origin of the LCS to the point at X1, Y1 then the other point will have the coordinates (X2-X1), (Y2-Y1).
3. Find the inclination of the line or the angle theta which it makes with the xaxis. If the line is vertical, then THETA = 90. If the line slopes towards the right (x2 > x1), then THETA= ARCTAN ((Y2-Y1)/(X2-X1)). If the line slopes towards the left (X2<X1), then THETA = 180 +ARCTAN((Y2-Y1)/(X2-XI)).
4. Rotate both end points, in terms of their coordinates relative to the first point, through this angle. The point 0,0 will not move, of course, but the other point should now have a y-coordinate of 0, meaning the line is now lying horizontally on the x-axis.
5. Finding and deforming the midpoint is now trivial. Its x-coordinate will be half the length and its y-coordinate plus or minus 1, 2, 3, etc.
6. Now all we need do is move the deformed line back where it belongs. This is just a matter of rotating through an angle Theta and then adding X1, Y1 to the coordinates of each point.
    A moment's consideration will convince you that we will get back the original coordinates of our line plus the rotated and translated coordinates of the midpoint. By design, we will make all of these calculations once. Only for the sides of the tiles which are actually defined and only for the first tile of a row. The remainder of the first tile and all the other tiles in that row are derived from the defined sides by rotation and shifting as usual.
    The program in Listing 2 differs from our previous tiling programs by keep ing the coordinate values of the vertices in an array. Two arrays are maintained. The first stores the original vertex coordinates. The second, larger one, holds the coordinates of the deformed tile.
    The data necessary for drawing the tiles is given in lines 140 and 150. This means that to change the shape of your basic tile you need only change one or two program lines. In fact, it turns out that you don't have to change the tile shape in order to change the design drawn by the computer. Try specifying the diamond tile by two vertices and four rotations:


rather than by three vertices and two rotations. When the number of vertices is odd, line 850 will flex the sides alternately "in" or "out." When the number of vertices specified is even, all sides will be flexed "in."
    It is evident that changing the tiling produced by the second program is a simple task. Because of this the program is great for experimentation! Some suggestions are to try square, rectangular, or hexagonal tiles and change the type of deformations used.

Tesselations

Listing 1.
Basic

DX 10 REM ROTATIONAL TESSELATION
NV 20 REM BY ALLAN MOOSE AND MARIAN LOREN
   Z
BB 40 REM
JN 50 REM **** INITIALIZE SYSTEM ****
BD 60 REM
RX 70 GRAPHICS 24:COLOR 1
CS 80 DEG :A=0:B=0
OI 90 DATA 0,0,17.32,-10,34.64,0,17.32,10
   ,0,0
ON 100 GOTO 450
QO 110 REM
PJ 120 REM **** ROTATION SUBROUTINE ****
QS 130 REM
AH 140 XPRIME=X*COS(THETA)-Y*SIN(THETA)
WF 150 YPRIME=X*SIN(THETA)+Y*COS(THETA)
IG 160 SCRNX=160+XPRIME
VX 170 SCRNY=96-YPRIME
ZN 180 RETURN
WM 200 REM **** END ROTATION SUBROUTINE *
   ***
QP 210 REM
QJ 220 REM **** SET TRANSLATION DISTANCES
   FOR SECOND ROW ****
UK 230 A=17.32:B=10:RETURN
OT 240 A=0:B=20.32:RETURN
WJ 250 A=-17.32:B=10:RETURN
WO 260 A=-17.32:B=-10:RETURN
MD 270 A=0:B=-20.32:RETURN
TR 280 A=17.32:B=-10:RETURN
ET 290 REM **** SET TRANSLATION DISTANCES
   FOR THIRD ROW ****
XN 300 A=34.64:B=0:RETURN
WZ 310 A=34.64:B=20:RETURN
WA 320 A=17.32:B=30:RETURN
EE 330 A=0:B=40:RETURN
XO 340 A=-17.32:B=30:RETURN
YU 350 A=-34.64:B=20:RETURN
XO 360 A=-34.64:B=0:RETURN
ZC 370 A=-34.64:B=-20:RETURN
YB 380 A=-17.32:B=-30:RETURN
WF 390 A=0:B=-40:RETURN
UJ 400 A=17.32:B=-30:RETURN
VL 410 A=34.64:B=-20:RETURN
QT 420 REM
CF 430 REM **** PLOT THE FIRST ROW ****
QX 440 REM
VY 450 FOR THETA=0 TO 360 STEP 60
US 460 READ X,Y:GOSUB 140:PLOT SCRNX,SCRN
   Y
QI 470 READ X,Y:GOSUB 140:DRAWTO SCRNX,SC
   RNY
QK 480 READ X,Y:GOSUB 140:DRAWTO SCRNX,SC
   RNY
QM 490 READ X,Y:GOSUB 140:DRAWTO SCRNX,SC
   RNY
PV 500 READ X,Y:GOSUB 140:DRAWTO SCRNX,SC
   RNY
TJ 510 RESTORE 90
TN 520 NEXT THETA
OW 530 REM
ZE 540 REM **** PLOT THE SECOND ROW ****
RA 550 REM
WB 560 FOR THETA=0 TO 360 STEP 60
MS 570 FOR J=1 TO 2
QU 580 I=I+1
CA 590 ON I GOSUB 280,230,230,240,240,250
   ,250,260,260,270,270,280
TI 680 RESTORE 90
QB 610 READ X,Y:GOSUB 140:PLOT SCRNX+A,SC
   RNY-B
CN 620 READ X,Y:GOSUB 140:DRAWTO SCRNX+A,
   SCRNY-B
CP 630 READ X,Y:GOSUB 140:DRAWTO SCRNX+A,
   SCRNY-B
CR 640 READ X,Y:GOSUB 140:DRAWTO SCRNX+A,
   SCRNY-B
CT 650 READ X,Y:GOSUB 140:DRAWTO SCRNX+A,
   SCRNY-B
GS 660 NEXT J
TY 670 NEXT THETA
FX 680 I=0
RJ 690 REM
NH 700 REM **** PLOT THE THIRD ROW ****
QU 710 REM
VV 720 FOR THETA=0 TO 360 STEP 60
NC 730 FOR J=1 TO 3
QO 740 I=I+1
QE 750 ON I GOSUB 410,300,310,310,320,330
   ,330,340,350,350,360,370,370,380,390,3
   90,400,410
TV 760 RESTORE 90
QO 770 READ X,Y:GOSUB 140:PLOT SCRNX+A,SC
   RNY-B
DA 780 READ X,Y:GOSUB 140:DRAWTO SCRNX+A,
   SCRNY-B
DC 790 READ X,Y:GOSUB 140:DRAWTO SCRNX+A,
   SCRNY-B
CL 800 READ X,Y:GOSUB 140:DRAWTO SCRNX+A,
SCRNY-B
CN 810 READ X,Y:GOSUB 140:DRAWTO SCRNX+A,
   SCRNY-B
CN 820 NEXT J
TS 830 NEXT THETA
RB 840 REM
MK 850 REM **** SCREEN DUMP ****
RF 860 REM
MZ 870 DIM GRAF$(200)
RS 875 GOSUB 1000
AC 880 GRAF$(1)=CHR$(0):GRAF$(200)=CHR$(0
   ):GRAF$(2)=GRAF$
MO 890 LPRINT CHR$(27);CHR$(65);CHR$(8)
GR 900 SCRNMEM=PEEK(88)+PEEK(89)*256
LU 910 MEMLOC=SCRNMEM+40*191
TF 920 HIBYTE=INT(ADR(GRAF$)/256)
EW 930 LOBYTE=ADR(GRAF$)-HIBYTE*256
EP 940 POKE 203,LOBYTE:POKE 204,HIBYTE
AQ 950 FOR SCRNCOL=MEMLOC TO MEMLOC+39
CL 960 DUMP=USR(1536,SCRNCOL)
EH 970 LPRINT CHR$(27);CHR$(75);CHR$(200)
   ;CHR$(0);GRAF$
KB 980 NEXT SCRNCOL
OQ 990 END
JE 1000 RESTORE 1040
HD 1010 FOR K=0 TO 43
BY 1020 READ ML:POKE 1536+K,ML
FU 1030 NEXT K
NZ 1040 DATA 104,104,141,15,6,104,141,14,\
   6,160,4,162,192,173,0,0,202,240,24
EF 1050 DATA 145,203,200,216,173,14,6,56,
   233,40,141,14,6
ZX 1060 DATA 144,3,76,13,6,206,15,6,76,13
   ,6,96
AU 1070 RETURN


Listing 2.
Basic

SS 10 REM **** ESCHER VERSION 5 ****
NV 20 REM BY ALLAN MOOSE AND MARIAN LOREN
   Z
BB 40 REM
NI 50 GOTO 140
FW 60 REM **** ROTATION SUBROUTINE ****
BE 70 REM
MN 80 XPRIME=X*COS(THETA)-Y*SIN(THETA)
IL 90 YPRIME=X*SIN(THETA)+Y*COS(THETA)
YX 100 RETURN
QO 110 REM
XK 120 REM **** INITIALIZE SYSTEM, VARIAB
   LES, ARRAYS ****
QS 130 REM
DL 140 DATA 3,2
BD 150 DATA 0,-8,8,0,0,8
NT 160 GRAPHICS 24:DEG :COLOR 1
IJ 170 READ NUMVERTS,NUMROTS
NP 180 DIM ARRAY1(NUMVERTS,2),ARRAY2(NUMV
   ERTS*2-1,2)
LE 190 THETAINC=360/NUMROTS
HN 200 FOR VERTEX=1 TO NUMVERTS
QV 210 READ XCOORD,YCOORD
IV 220 ARRAY1(VERTEX,1)=XCOORD:ARRAY1(VER
   TEX,2)=YCOORD
ZX 230 NEXT VERTEX
SP 240 REM **** DETERMINE HEIGHT AND WIDT
   H OF TILE ****
HX 250 FOR VERTEX=1 TO NUMVERTS
CD 260 IF ABS(ARRAY1(VERTEX,1))>XMAX THEN
    XMAX=ABS(ARRAY1(VERTEX,1))
II 270 IF ABS(ARRAY1(VERTEX,2))>YMAX THEN
    YMAX=ABS(ARRAY1(VERTEX,2))
AH 280 NEXT VERTEX
BJ 290 HEIGHT=2*YMAX:WIDTH=2*XMAX
SI 300 MAXCOLS=INT(320/WIDTH)-1
UJ 310 MAXROWS=INT(192/HEIGHT)-1
SR 320 INITIALX=XMAX+5:INITIALY=YMAX+5
QU 330 REM
YF 340 REM **** PLOT THE FIRST ROW OF TIL
   ES ****
QY 350 REM
HD 360 FOR COL=1 TO MAXCOLS
UP 370 FOR THETA=0 TO 360 STEP THETAINC
IE 380 FOR VERTEX=1 TO NUMVERTS
ZU 390 X=ARRAY1(VERTEX,1):Y=ARRAY1(VERTEX
   ,2)
VO 400 GOSUB 80
LV 410 SCRNX=INITIALX+(COL-1)*WIDTH+XPRIM
   E
RM 420 SCRNY=INITIALY-YPRIME
KH 430 IF VERTEX=1 THEN PLOT SCRNX,SCRNY:
   GOTO 450
PL 440 DRAWTO SCRNX,SCRNY
AD 450 NEXT VERTEX
TU 460 NEXT THETA
UN 470 NEXT COL
RF 480 REM
LY 490 REM **** DRAW SUCCEEDING ROWS OF T
   ILES ****
QQ 500 REM
NA 510 FOR ROW=2 TO MAXROWS
TQ 520 YOFFSET=YOFFSET+1
UU 530 GOSUB 730
HB 540 FOR COL=1 TO MAXCOLS
UN 550 FOR THETA=0 TO 360 STEP THETAINC
SP 560 FOR VERTEX=1 TO NUMVERTS*2-1
BJ 570 X=ARRAY2(VERTEX,1):Y=ARRAY2(VERTEX
   ,2)
WF 580 GOSUB 80
MM 590 SCRNX=INITIALX+(COL-1)*WIDTH+XPRIM
   E
EQ 600 SCRNY=INITIALY+(ROW-1)*HEIGHT-YPRI
   ME
PI 610 IF VERTEX=1 THEN PLOT SCRNX,SCRNY:
   GOTO 660
YA 620 REM CLIPPING ROUTINE
KP 630 IF SCRNX<0 OR SCRNX>319 THEN GOTO
   940
JU 640 IF SCRNY<0 OR SCRNY>191 THEN GOTO
   940
PP 650 DRAWTO SCRNX,SCRNY
AH 660 NEXT VERTEX
TY 670 NEXT THETA
UR 680 NEXT COL
FP 690 NEXT ROW
QG 700 GOTO 940
QU 710 REM
GL 720 REM **** SUBROUTINE TO CREATE AN A
   RRAY OF DEFORMED TILES ****
QY 730 REM
HQ 740 FOR I=1 TO NUMVERTS-1
TP 750 X1=ARRAY1(I,1):ARRAY2(2*I-1,1)=ARR
   AY1(I,1)
MP 760 X2=ARRAY1(I+l,1)
XP 770 Y1=ARRAY1(I,2):ARRAY2(2*I-1,2)=ARR
   AY1(I,2)
NR 780 Y2=ARRAY1(I+1,2)
CH 790 X=X2-X1:Y=Y2-Y1
UE 800 IF X=0 THEN THETA=(-1)*SGN(Y)*98:G
   OTO 850
QO 810 THETA=ATN(Y/X)
OA 828 IF X<0 THEN THETA=180+THETA
FM 830 THETA=-THETA:REM ROTATE TOWARD X-A
   XIS
WA 840 GOSUB 80
XL 850 X=XPRIME/2:Y=YOFFSET*(-1)^(I+1)
LX 860 THETA=-THETA:REM ROTATE BACK INTO
   POSITION
WG 870 GOSUB 80
FD 880 ARRAY2(2*I,1)=XPRIME+X1:ARRAY2(2*I
   ,2)=YPRIME+Y1
GO 890 NEXT I
IV 900 REM **** COMPLETE ARRAY2 ****
SU 910 FOR J=1 TO 2:ARRAY2(2*NUMVERTS-1,J
   )=ARRAY1(NUMVERTS,J):NEXT J
ZJ 920 RETURN
MH 930 REM **** SCREEN DUMP ****
UY 940 GOSUB 1080
MW 950 DIM GRAF$(200)
ZZ 960 GRAF$(1)=CHR$(0):GRAF$(200)=CHR$(0
   ):GRAF$(2)=GRAF$
ML 970 LPRINT CHR$(27);CHR$(65);CHR$(8)
HH 980 SCRNMEM=PEEK(88)+PEEK(89)*256
MK 990 MEMLOC=SCRNMEM+40*191
MZ 1000 HIBYTE=INT(ADR(GRAF$)/256)
FW 1010 LOBYTE=ADR(GRAF$)-HIBYTE*256
MY 1020 POKE 203,LOBYTE:POKE 204,HIBYTE
MP 1030 FOR SCRNCOL=MEMLOC TO MEMLOC+39
PW 1040 DUMP=USR(1536,SCRNCOL)
RG 1050 LPRINT CHR$(27);CHR$(75);CHR$(200
   ):CHR$(0);GRAF$
AK 1060 NEXT SCRNCOL
FI 1070 END
JL 1080 RESTORE 1120
IB 1090 FOR K=0 TO 43
BU 1100 READ ML:POKE 1536+K,ML
FO 1110 NEXT K
NV 1120 DATA 104,104,141,15,6,104,141,14,
   6,160,4,162,192,173,0,0,202,240,24
EB 1130 DATA 145,203,200,216,173,14,6,56,
   233,40,141,14,6
ZT 1140 DATA 144,3,76,13,6,206,15,6,76,13
   ,6,96
AQ 1150 RETURN