% tiling.mp

% Truchet’s problem: macros

%==================================================

% D. Roegel’s solution for Denis Girou’s pstricks competition.

% This solution is written in METAPOST.

% The source file may be formatted using the mft program.

% (the program used for volumes B and E of Computers & Typesetting) % Send comments and improvements to roegel@loria.fr. % ————————————————————————-

% \underline{History}:

% 9-10 June 1995 (lines) % 13-14 June 1995 (surfaces)

% 16 June 1995 (comments and restructuring) % 21 June 1995 (some more formatting for mft)

% 26 June 1995 (some simplifications)

% 9 July 1995 (macros and examples were split and code better organized)

%

% This is my first “large” METAPOST program. I’m still learning! % Therefore lots of things are clumsy and I don’t pretend this

% is an example of good METAPOST programming.

% I had however great fun writing it!

%

% \underline{Some highlights}:

% The coloring of lines worked after circa 4 hours …

% The only real problem I met was that an infinite loop occured

% when follow line was following a cyclic path.

%

% Concerning the coloration of surfaces, I needed some time

% until I noticed that two colors were sufficient!

% Once you notice this and draw all the conclusions, the task is trivial.

% ————————————————————————-

%

% A tiling Nx × Ny is a matrix of tiles indexed by x

% ranging between

% 0 and Nx − 1 and y ranging between 0 and Ny − 1.

% Two kinds of tiles are considered. We will refer to them as ‘tile 0’

% and ‘tile 1’. Each tile has three parts, marked *, + and x. % %

 %
% Tile 0:            Tile 1:
%
%
%
%

%

% ————————————————————————— % %—————————————————————————– % Tiling orientation and color initialization: BEGINNING %—————————————————————————–

% We define the tiling randomly.

def init tiling(expr nx, ny) =

for i := 0 upto nx − 1:

for j := 0 upto ny − 1:

tile[i][j] := coin; % we throw a coin for each tile. endfor;

endfor; enddef;

% The ‘coin’ macro behaves like a coin and yields randomly 0 or 1.

% This is used for the initial tiling.

def coin = floor(uniformdeviate 2) enddef;

% We let − 1 mean “no color yet”.

def init colors =

for i := 0 upto Nx − 1: for j := 0 upto Ny − 1: tilecolor[i][j][0] := −1; % right tilecolor[i][j][1] := −1; % up tilecolor[i][j][2] := −1; % left tilecolor[i][j][3] := −1; % down

endfor; endfor; enddef;

def init partcolors =

for i := 0 upto Nx − 1:

for j := 0 upto Ny − 1: tilepartcolor[i][j][0] := −1; % up left or up right tilepartcolor[i][j][1] := −1; % middle tilepartcolor[i][j][2] := −1; % down right or down left

endfor; endfor; enddef;

% The macro TileColors allows to define or redefine the colors. % Only two colors are necessary.

def TileColors(expr ca, cb) =

def partcolor(expr c) = if c = 0: ca

else: cb

fi enddef; enddef;

% The default colors are red and (1, 1, 0) (in RGB coordinates)

TileColors(red, (1, 1, 0));

% A useful color. We might also have used the ċolor type.

def yellow = (1, 1, 0) enddef; % RGB definition

% The basic pattern is the following quartercircle;

% It is used later on, shifted and rotated.

def define basetile(expr u) = path upperleft;

upperleft := ((0, 0.5){right} . . {up}(0.5, 1)) scaled u; enddef;

% Here, we define the paths corresponding to the upper left and middle % parts of the tile 0.

def define basetilepart(expr u) =

path tilepart[];

% left upper corner of a standard tile

tilepart_{0} := ((0, 0.5){right} . . {up}(0.5, 1) - - (0, 1) - - cycle) scaled u;

% middle part of the standard tile

tilepart_{1} := ((0, 0.5){right} . . {up}(0.5, 1) - - (1, 1) - -

(1, 0.5){left} . . {down}(0.5, 0) - - (0, 0) - - cycle) scaled u;

enddef;

% The external frame is drawn outside the rectangle (0,0) – (nx*u,ny*u).

% Guess why ?

vardef draw boundaries(expr nx, ny) = numeric u, delta; u = TilingUnit; delta = .5mm; pickup pencircle scaled (2 ∗ delta); draw(0 − delta, 0 − delta) - - (0 − delta, ny ∗ u + delta) - -

(nx ∗ u + delta, ny ∗ u + delta) - - (nx ∗ u + delta, 0 − delta) - - cycle;

for i := 1 upto nx − 1: draw(i ∗ u, 0) - - (i ∗ u, ny ∗ u); endfor; for i := 1 upto ny − 1: draw(0, i ∗ u) - - (nx ∗ u, i ∗ u); endfor;

enddef;

%—————————————————————————–

% Tiling orientation and color initialization: END

%—————————————————————————– % %—————————————————————————–

% Computation of line colors: BEGINNING

%—————————————————————————– % The macro compute linecolors ‘computes’ the colors of the lines.

% As a matter of fact, all what it does is going through all % the tiles, choose a not yet colored line, and follow it on

% both directions, and simultaneously coloring it.

% For each line a new color is used.

%

vardef compute linecolors = numeric k; init colors; for i := 0 upto Nx − 1:

for j := 0 upto Ny − 1:

forever:

k := not colored direction(i, j); % choose a non colored line. exitif k = −1; % there is none, go to the next tile. follow line(i, j, k, nextcolor); % Follow this line and color it with

% nextcolor.

k := dual(i, j, k); % Get the opposite direction. if tilecolor[i][j][k] = −1: % If it is not yet colored,

follow line(i, j, k, nextcolor); % follow the line.

fi;

nextcolor := nextcolor + 1; endfor;

endfor; endfor;

enddef;

% This macro gives a direction not yet colored.

% If there is none, it yields − 1.

def not colored direction(expr x, y) = if tilecolor[x][y][0] = −1: 0 elseif tilecolor[x][y][1] = −1: 1 elseif tilecolor[x][y][2] = −1: 2 elseif tilecolor[x][y][3] = −1: 3 else: −1 fi

enddef;

% Colour a line and follow it.

% Notice that for each tile except the first one, two directions

% must be colored.

%

vardef follow line(expr x, y, d, c) = % x,y are the beginning coordinates

% d is the direction in which we advance

% c is the color used

tilecolor[x][y][d] := c; xx := x; yy := y; dd := d;

forever:

exitif last tile(xx, yy, dd); % are we at an edge ? next tile; % get the new values of xx, yy and dd. du := dual(xx, yy, dd); exitif tilecolor[xx][yy][du] > −1; % are we in a cycle ? tilecolor[xx][yy][du] := c; tilecolor[xx][yy][dd] := c;

endfor; enddef;

% This macro gives the direction dual to d in a tile.

def dual(expr x, y, d) =

(((2 ∗ tile[x][y]) + if d = 0: 3 elseif d = 1: 2 elseif d = 2: 1 else: 0 fi) mod 4) enddef;

% This macro is true if a line goes outside the rectangle.

def last tile(expr x, y, d) =

if (x = 0) and (d = 2)or (x = Nx − 1) and (d = 0)or (y = 0) and (d = 3)or (y = Ny − 1) and (d = 1): true

else: false

fi; enddef;

def next tile = if dd = 0: xx := xx + 1; dd := (1 + 2 ∗ tile[xx][yy]) mod 4; elseif dd = 1: yy := yy + 1; dd := (0 + 2 ∗ tile[xx][yy]) mod 4; elseif dd = 2: xx := xx − 1; dd := (3 + 2 ∗ tile[xx][yy]) mod 4; else: yy := yy − 1; dd := (2 + 2 ∗ tile[xx][yy]) mod 4; fi

enddef;

%—————————————————————————–

% Computation of line colors: END

%—————————————————————————– % %—————————————————————————–

% Drawing of the colored lines: BEGINNING

%—————————————————————————–

% For each tile, we color the lines.

vardef draw coloredlines(expr nx, ny) = save u; u = TilingUnit; pickup pencircle scaled TilingLineWidth; for i := 0 upto nx − 1:

for j := 0 upto ny − 1:

color thetile(i, j); % here we draw the colored tiles. endfor;

endfor; enddef;

% This macro just draws the left and right part of a tile.

def color thetile(expr x, y) = draw upperleft(x, y, tile[x][y] ∗ 90, tilecolor[x][y][2]); draw upperleft(x, y, 180 + 90 ∗ tile[x][y], tilecolor[x][y][0]);

enddef;

% The macro draw upperleft draws the upperleft path, rotated by angle a, % and with a color depending on c.

def draw upperleft(expr x, y, a, c) =

draw upperleft shifted (−.5u, −.5u) rotated a shifted (.5u, .5u) shifted ((x, y) ∗ u) withcolor(linecolor(c));

enddef;

% The kind of line color is chosen here; this may be changed.

def linecolor(expr c) = (c/nextcolor)[red, green] enddef;

%—————————————————————————–

% Drawing of the colored lines: END

%—————————————————————————– % %—————————————————————————–

% Computation of tile colors: BEGINNING

%—————————————————————————–

% In order to color the tiling, we need only two colors.

% These colors are numbered 0 and 1. % The whole tiling can be performed at once.

def compute partcolors = init partcolors; for i := 0 upto Nx − 1:

for j := 0 upto Ny − 1:

fill tile(i, j);

endfor; endfor;

enddef;

% This macro collects the colors of the neighbours (only down and left)

% and updates the current tile, where possible.

%

def fill tile(expr x, y) = init neighbours(x, y); % get the color of the neighbouring tiles if tile[x][y] = 0:

handle edges(7)(x, y, 0); handle edges(5, 6)(x, y, 1); handle edges(4)(x, y, 2);

else:

handle edges(5, 6)(x, y, 2); handle edges(4, 7)(x, y, 1);

fi; complete tile(x, y);

enddef;

% Neighbours are initialized in an obvious way.

% The numbering of the neighbours is dual to the numbering

% of edges (see below).

% (commented lines are just given for sake of completeness;

% they are not actually used) %

def init neighbours(expr x, y) = for i := 0 upto 7: neighbour edgecolors[i] := −1; endfor; if x > 0:

neighbour edgecolors[7] := edge color(x − 1, y, 2); neighbour edgecolors[6] := edge color(x − 1, y, 3);

fi;

% if x < Nx − 1: neighbour edgecolors[2] := edge color(x + 1, y, 7);

% neighbour edgecolors[3] := edge color(x + 1, y, 6); fi;

if y > 0:

neighbour edgecolors[5] := edge color(x, y − 1, 0); neighbour edgecolors[4] := edge color(x, y − 1, 1);

fi;

% if y < Ny − 1: neighbour edgecolors[0] := edge color(x, y + 1, 5);

% neighbour edgecolors[1] := edge color(x, y + 1, 4); fi;

enddef;

% This macro spreads the colors of the neighbours in the list e % onto the part f of tile [x, y].

%

def handle edges(text e)(expr x, y, f) =

forsuffixes s := e:

if neighbour edgecolors[s] > −1:

tilepartcolor[x][y][f] := neighbour edgecolors[s]; fi;

endfor; enddef;

% The macro edge color gives the color of an edge, if any. % There are eight edges, and they are numbered from 0 to 7.

% % %

                                                                %  *0 0 0 1 1 1*
                                                                %  7           2
                                                                %  7           2
                                                                %  7           2
                                                                %  6           3
                                                                %  6           3
                                                                %  6           3
                                                                %  *5 5 5 4 4 4*

% %

def edge color(expr x, y, e) =

if tile[x][y] = 0:

if (e = 0) or (e = 7): tilepartcolor[x][y][0]; elseif (e = 3) or (e = 4): tilepartcolor[x][y][2]; else: tilepartcolor[x][y][1]; fi;

else:

if (e = 1) or (e = 2): tilepartcolor[x][y][0]; elseif (e = 5) or (e = 6): tilepartcolor[x][y][2]; else: tilepartcolor[x][y][1]; fi;

fi; enddef;

% Since two colors are enough, as soon as one part of a tile

% is colored, we can immediately color the others.

def complete tile(expr x, y) =

if tilepartcolor[x][y][0] > −1: tilepartcolor[x][y][1] := 1 − tilepartcolor[x][y][0]; tilepartcolor[x][y][2] := tilepartcolor[x][y][0];

fi; if tilepartcolor[x][y][1] > −1:

tilepartcolor[x][y][0] := 1 − tilepartcolor[x][y][1]; tilepartcolor[x][y][2] := 1 − tilepartcolor[x][y][1];

fi; if tilepartcolor[x][y][2] > −1:

tilepartcolor[x][y][1] := 1 − tilepartcolor[x][y][2]; tilepartcolor[x][y][0] := tilepartcolor[x][y][2];

fi; if tilepartcolor[x][y][0] = −1: % this part is only used at

% the very beginning of a

tiling, and

% serves as initialization.

tilepartcolor[x][y][0] := 0; tilepartcolor[x][y][1] := 1; tilepartcolor[x][y][2] := 0;

fi; enddef;

%—————————————————————————–

% Computation of tile colors: END

%—————————————————————————– % %—————————————————————————–

% Drawing of tile colors: BEGINNING

%—————————————————————————–

% For each tile, we color the three parts.

vardef draw coloredparts(expr nx, ny) = save u; u = TilingUnit; for i := 0 upto nx − 1:

for j := 0 upto ny − 1:

fill tilepart(i, j, 1); fill tilepart(i, j, 2); fill tilepart(i, j, 3);

endfor; endfor;

enddef;

% fill tilepart fills part part at position x, y.

def fill tilepart(expr x, y, part) =

if part = 1:

colorpart(x, y, 0, −90 ∗ tile[x][y], partcolor(tilepartcolor[x][y][0])); elseif part = 2:

colorpart(x, y, 1, 90 ∗ tile[x][y], partcolor(tilepartcolor[x][y][1]));

else:

colorpart(x, y, 0, 180 − 90 ∗ tile[x][y], partcolor(tilepartcolor[x][y][2])); fi;

enddef;

% colorpart colors a part p (0 is corner, 1 is middle)

% at position x, y, using the fundamental

% tilepart[p] pattern, rotated by a degrees and colored according to c.

vardef colorpart(expr x, y, p, a, c) =

fill(tilepart[p] shifted (−.5u, −.5u) rotated a shifted (.5u, .5u) shifted ((x, y) ∗ u))withcolor(c);

enddef;

%—————————————————————————–

% Drawing of tile colors: END

%—————————————————————————– % %—————————————————————————–

% Main definition

%—————————————————————————–

% This is the main definition.

% Two cases are considered: either the lines are colored, and the surfaces % are not filled, or the surfaces are colored, but the lines are not.

vardef TruchetTiling(expr x, y) = save Nx, Ny; Nx = x; Ny = y; init tiling(Nx, Ny); draw boundaries(Nx, Ny);

if not TruchetTilingFill:

define basetile(TilingUnit); numeric nextcolor, tilecolor[][][]; nextcolor := 0; compute linecolors; % the colors of the lines are computed here,

% but not drawn;

draw coloredlines(Nx, Ny);

else:

define basetilepart(TilingUnit); numeric tilepartcolor[][][], neighbour edgecolors[]; compute partcolors; draw coloredparts(Nx, Ny);

fi; enddef;

%—————————————————————————–

% Global variables and default values

%—————————————————————————–

numeric tile[][]; boolean TruchetTilingFill; TruchetTilingFill = false; numeric TilingUnit, TilingLineWidth;

% default values

TilingUnit := 1cm; TilingLineWidth := 1mm;

%—————————————————————————–

% End of file tiling.mp

%—————————————————————————–