% {\tt tiling.mp} % {\bf Truchet's problem: macros} %================================================== % D. Roegel's solution for Denis Girou's {\tt pstricks} competition. % This solution is written in {\tt METAPOST}. % The source file may be formatted using the {\tt mft} program. % (the program used for volumes B and E of {\it Computers \& Typesetting\/}) % Send comments and improvements to {\tt roegel@loria.fr}. % ------------------------------------------------------------------------- % \underbar{History}: % 9-10 June 1995 (lines) % 13-14 June 1995 (surfaces) % 16 June 1995 (comments and restructuring) % 21 June 1995 (some more formatting for {\tt mft}) % 26 June 1995 (some simplifications) % 9 July 1995 (macros and examples were split and code better organized) % % This is my first large'' {\tt METAPOST} program. I'm still learning! % Therefore lots of things are clumsy and I don't pretend this % is an example of good {\tt METAPOST} programming. % I had however great fun writing it! % % \underbar{Some highlights}: % The coloring of lines worked after circa 4 hours $\ldots$ % 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| $\times$ |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 {\tt*}, {\tt+} and {\tt x}. % {\catcode\.=13\gdef\os{\obeyspaces\tt\frenchspacing % \catcode\.=13\def.{\char124 }}} % {\os % Tile 0: |" ------ "| Tile 1: |" ------ "| % |".* . ."| |". . * ."| % |"._/ + _."| |"._ +\ _."| % |". /x."| |".x\ ."| % |".___.__."| |".__.___."|} % % --------------------------------------------------------------------------- %\vfill\eject %----------------------------------------------------------------------------- % 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 \.{color} 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 tilepart0:=((0,0.5){right}..{up}(0.5,1)--(0,1)--cycle) scaled u; % middle part of the standard tile tilepart1:=((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 %----------------------------------------------------------------------------- %\vfill\eject %----------------------------------------------------------------------------- % 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 %----------------------------------------------------------------------------- %\vfill\eject %----------------------------------------------------------------------------- % 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 %----------------------------------------------------------------------------- %\vfill\eject %----------------------------------------------------------------------------- % 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 x0: neighbour_edgecolors[5]:=edge_color(x,y-1,0); neighbour_edgecolors[4]:=edge_color(x,y-1,1); fi; % |if y-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|. % % %{\os *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 %----------------------------------------------------------------------------- %\vfill\eject %----------------------------------------------------------------------------- % 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 %----------------------------------------------------------------------------- %\vfill\eject %----------------------------------------------------------------------------- % 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 %-----------------------------------------------------------------------------