Recursively repetitive figures arise naturally and in a variety of pattern and design work. Such figures are called fractals. The essence of a fractal is that is has the same kind of micro structure as it has a macro structure.
For instance, if the West coast of British Columbia, Canada is viewed from outer space, it has an irregular shape with numerous inlets folded into the larger outline throughout this length. Looked at from a lower altitude airplane, these larger inlets themselves have an irregular and folded structure, and if one were to look closer still down on the ground, these too would be seen to have inlets and folds. That is to say, a fractal is recursive, at least to some number of levels. (In the case of the coastline, the recursion would break down to some extent after one began looking at individual grains of sand under sufficient magnification.)
A number of standard fractal designs can be constructed using recursive drawing techniques, and these are detailed below.
One of the easiest types of fractals to draw is a snowflake.
The snowflake fractal shown in figure 18.5 is based on triangles and has four levels of recursion or sizes of triangle. Assuming that the drawing starts at the lower left corner and with the direction to the right or East, the drawing of this fractal could be formulated in terms of pseudocode for a three sided figure as follows:
draw fractal =
select standard coordinates
select levelsofrecursion
select mainlength
select starting point on screen
calculate turn angle based on number of sides (60 degrees for triangles)
drawfigure
drawfigure (mainlength, recursionlevel) =
save current position and direction
turnby -60 degrees; (* turn out and away first *)
drawsegment (sidelen, curreclevel); (* go draw a side *)
for count := 2 to numsides - 1
do (* then turn and draw each successive side except the last *)
turnby 120 degrees; (* turn back in *)
drawsegment (sidelen, curreclevel);
end;
if curreclevel < recursionlevel
then (* fill in the missing side -- central third *)
turnto (olddir);
moveto (oldx, oldy);
lineto (curx, cury);
else (* go draw the last side *)
turnby 120 degrees;
drawsegment (sidelen, curreclevel);
end;
drawsegment (dist, curreclevel) =
disttodraw := dist / 3.0;
if curreclevel = 0
then
lineby (dist);
else
drawsegment (disttodraw, curreclevel - 1);
drawfigure (disttodraw, curreclevel - 1);
drawsegment (disttodraw, curreclevel - 1);
end;
The basic idea is that drawing a figure (say, a triangle) consists of drawing three successive segments with the appropriate angle between. Drawing each segment consists of drawing a third of that segment, then drawing the original figure at one third size as the middle third (unless one is past the appropriate number of recursion levels) then drawing the last third of the segment. In the code that follows, however, this has been modified to allow for the angle to be calculated for the number of sides. The number of recursion levels and number of sides is initially set to reproduce the drawing above, but both can easily be changed. Here is the code:
MODULE Snowflake;
(* by R. Sutcliffe 1996 01 29
to illustrate Macintosh quickdraw
revised by Joel Schwartz and R. Sutcliffe to depend on GraphPaper.
This program draws a recursive snowflake with a specified number of sides and level of recursion. Last revision 1998 06 16 *)
FROM GraphPaper IMPORT
LineBy, LineTo, TurnTo, MoveTo, GetDimensions, SetCoordSystem, CoordSystem, GetLocation;
CONST
(* set up these first two constants; the rest depend on them. *)
recursionLevel = 3;
numSides = 3;
degreesAvailable = 180 * (numSides - 2);
(* how many degrees around and back *)
turnAngle = degreesAvailable DIV numSides;
(* turn for each corner *)
VAR
curDir : INTEGER;
curX, curY : INTEGER; (* to globally store position and direction *)
dimX, dimY : INTEGER; (* the dimensions *)
PROCEDURE DrawSegment (dist : REAL; curRecLevel : INTEGER); FORWARD;
(* omit if compiler is multi pass *)
PROCEDURE DrawFigure (sideLen : REAL; curRecLevel :INTEGER);
VAR
oldX, oldY : INTEGER;
oldDir : INTEGER;
count : CARDINAL;
BEGIN
(* store current directions *)
oldX := curX;
oldY := curY;
oldDir := curDir;
curDir := curDir - turnAngle;
TurnTo (FLOAT (curDir)); (* turn out and away first *)
DrawSegment (sideLen, curRecLevel); (* go draw a side length *)
FOR count := 2 TO numSides - 1
DO (* then turn and draw each successive one but the last *)
curDir := curDir - turnAngle + 180;
TurnTo (FLOAT (curDir));
DrawSegment (sideLen, curRecLevel);
END;
IF curRecLevel < recursionLevel
THEN (* fill in the missing side -- central third *)
curDir := oldDir; (* go back to old position *)
TurnTo (FLOAT (curDir));
MoveTo (oldX, oldY);
LineTo (curX, curY); (* and draw to new one *)
ELSE (* draw another side like the ones in the loop above *)
curDir := curDir - turnAngle + 180;
TurnTo (FLOAT (curDir));
DrawSegment (sideLen, curRecLevel);
END;
END DrawFigure;
PROCEDURE DrawSegment (dist : REAL; curRecLevel : INTEGER);
(* recursively draw a third of the segment as another one
then a third size figure on the next segment
then another segment after that. *)
VAR
distToDraw : REAL;
BEGIN
distToDraw := dist / 3.0;
IF curRecLevel = 0
THEN
LineBy (TRUNC(dist));
GetLocation (curX, curY); (* reset local storage of position *)
ELSE
DrawSegment (distToDraw, curRecLevel - 1);
DrawFigure (distToDraw, curRecLevel - 1);
DrawSegment (distToDraw, curRecLevel - 1);
END;
END DrawSegment;
VAR
mainLength : INTEGER;
BEGIN (* main *)
(* calculate a length that will fill the screen nicely *)
SetCoordSystem (MacWin);
GetDimensions (dimX, dimY);
mainLength := 3 * dimY/(2 * numSides); (* arrived at by experimenting *)
(* starting point is "lower left" of first level recursive figure. *)
curDir := 0;
curX := (dimX - mainLength) / 2;
curY := (dimY + mainLength) / 2;
(* above formula not bad except for three sides, so adjust *)
IF numSides = 3
THEN
curY := curY - 75;
END;
MoveTo (curX, curY);
DrawFigure (FLOAT (mainLength), recursionLevel);
END Snowflake.
The program in this section recursively draws a tree fractal. The idea is that it draws a trunk in the current direction, then two trees at half size at forty-five degrees on either side of the top of the trunk, then a tree at three-quarters size in the same direction as the original trunk. After the first vertical trunk, the remaining trees can be thought of as branches. Recursion is exited if the length of the trunk is less than two units.
MODULE DrawTree;
(* Program by R. Sutcliffe
to illustrate GraphPaper
revised 1998 06 16
recursively draws a fractal based tree. *)
FROM GraphPaper IMPORT
MoveTo, LineBy, Turn, TurnTo, GetLocation;
PROCEDURE DrawATree (trunkLength : CARDINAL);
VAR
baseX, baseY : INTEGER;
BEGIN
IF trunkLength < 2
THEN
RETURN
END (* if *);
LineBy (trunkLength);
GetLocation (baseX, baseY);
Turn (45.0);
DrawATree (trunkLength DIV 2); (* 1/2 current size right *)
MoveTo (baseX, baseY);
Turn (-90.0);
DrawATree (trunkLength DIV 2); (* 1/2 current size left *)
MoveTo (baseX, baseY);
Turn (45.0);
DrawATree (3 * (trunkLength DIV 4)); (* 3/4 current size up *)
MoveTo (baseX, baseY);
END DrawATree;
BEGIN
(* Find a good place to start drawing the tree. *)
MoveTo (0,-250);
TurnTo (90.0);
DrawATree (128);
END DrawTree.
Here is a screen shot of the tree that is drawn:
The tree fractal was drawn in a different way than the snowflake that preceded it. Rather than use a pair of mutually recursive procedures, it employed only a single procedure that drew segment-right fractal-left fractal-central fractal. Snowflakes can be drawn in a similar manner, without the filled in sides, and by using a singly-recursive procedure as in the following:
MODULE DrawFractal;
(* Program to draw a fractal
by R. Sutcliffe
revised 1998 06 16 *)
FROM GraphPaper IMPORT
LineBy, Turn, TurnTo, MoveTo;
TYPE
CardArray = ARRAY [0..12] OF CARDINAL;
CONST
order = 6; (* fits on most screens *)
(* make a constant array with the powers of two for the line lengths. *)
Power = CardArray {1,2,4,8,16,32,64,128,256,512,1024,2048,4096};
PROCEDURE Fractal (level: CARDINAL);
(* Recursive drawing of levelth fractal *)
BEGIN
Turn (-60.0);
(* at all but the outer level, we do segment-fractal-segment *)
LineBy (Power [level]);
IF level > 1
THEN
Fractal (level - 1);
END; (* if *)
LineBy (Power [level]);
Turn (120.0);
LineBy (Power [level]);
IF level > 1
THEN
Fractal (level - 1);
END; (* if *)
LineBy (Power [level]);
(* at the outer level we complete the figure so it is closed *)
IF level = order
THEN
Turn (120.0);
LineBy (Power [level]);
IF level > 1
THEN
Fractal (level - 1);
END; (* if *)
LineBy (Power [level]);
END;
Turn (-60.0);
END Fractal;
VAR
ch : CHAR;
BEGIN (* DrawFractal *)
(* orient on the page the way we want *)
TurnTo (180.0);
MoveTo (100, -50);
Fractal (order);
END DrawFractal.
This program produces the following version of the snowflake fractal:
The most basic form of the fractal known as Sierpinski's curve consists of a square with squares on its corners in the manner shown in figure 18.8. Assuming standard coordinates with the origin at the centre, and given that the basic length on one of the corners is dist, drawing is done in four steps starting from the indicated point. (Recall that Line draws to a point with the given displacement from the current point.)
top: Line (dist, -dist); Line (2 * dist, 0); Line (dist, dist);
followed by Line (dist, -dist) to glue to the next piece
right: Line (-dist, -dist); Line (0, -2 * dist); Line (dist, -dist);
followed by Line (-dist, -dist) to glue to the next piece
bottom: Line (-dist, dist); Line (-2 * dist, 0); Line (-dist, -dist);
followed y Line (-dist, dist) to glue to the next piece
left: Line (dist, dist); Line (0, 2 * dist); Line (-dist, dist);
followed by Line (dist, dist) to glue to the next piece
That is, each procedure has three steps that draw a copy (in one of four rotations) of what is shown in figure 18.9, followed by a connector to the next part.
The fun begins when this process is made recursive, in the sense that the prototype procedure Top becomes:
Top =
IF level > 0
THEN
Top (level - 1); Line (dist, -dist);
Right (level - 1); Line (2 * dist, 0);
Left (level - 1); Line (dist, dist);
Top (level - 1)
END
If this is drawn at level two, the top (including the glue) becomes figure 18.10, and this pattern can be replicated around the basic square using the other three procedures in turn.
With a careful calculation of starting points, the level two diagram can be superimposed on top of the level one diagram, and indeed as many levels can be drawn as desired. In the code that is given below, three levels have been drawn by the main loop. Care must be taken not to ask for too many levels, or one could find the program in an infinite loop unable to compute the next smaller side length.
MODULE Sierpinski;
(* Heavily adapted from a version in Wirth's PIM-2
by R. Sutcliffe to illustrate GraphPaper
last revision: 1998 06 22 *)
FROM GraphPaper IMPORT
Line, LineTo, MoveTo;
CONST
size = 512; (* use a power of two that fits on screen. *)
numOfLevels = 3; (* set to number smaller than the power in the last line; if 512; use 8 or less here *)
VAR
dist : INTEGER;
(* Each of the mutually recursive procedures draws one side of the basic square figure in the orientation given by its name. At the lowest level, this is an angled part, a straight part, and then an angled part, concluding with a "larger" copy of itself at a lower level to glue to the next piece. *)
PROCEDURE Top (level: CARDINAL);
BEGIN
IF level > 0
THEN
Top (level - 1); Line (dist, -dist);
Right (level - 1); Line (2 * dist, 0);
Left (level - 1); Line (dist, dist);
Top (level - 1)
END
END Top;
PROCEDURE Right (level: CARDINAL);
BEGIN
IF level > 0
THEN
Right (level - 1); Line (-dist, -dist);
Bottom (level - 1); Line (0, -2 * dist);
Top (level - 1); Line (dist, -dist);
Right (level - 1)
END
END Right;
PROCEDURE Bottom (level: CARDINAL);
BEGIN
IF level > 0
THEN
Bottom (level - 1); Line (-dist, dist);
Left (level - 1); Line (-2 * dist, 0);
Right (level - 1); Line (-dist, -dist);
Bottom (level - 1)
END
END Bottom;
PROCEDURE Left (level: CARDINAL);
BEGIN
IF level > 0
THEN
Left (level - 1); Line (dist, dist);
Top (level - 1); Line (0, 2 * dist);
Bottom (level - 1); Line (-dist, dist);
Left (level - 1);
END
END Left;
VAR
level : CARDINAL;
startX, startY : INTEGER;
BEGIN
dist := size DIV 4; (* initial segment distance *)
startX := 0;
startY := dist;
level := 0;
(* The following loop draws the level one figure and then overlays it with the level two figure, and so on until the number of specified levels have all been drawn. *)
REPEAT
INC (level); (* begin at one and work up to max set. *)
DEC (startX, dist); (* set up new corner to start *)
dist := dist / 2; (* and basic distance for next level *)
INC (startY, dist);
MoveTo (startX, startY);
(* We end up d units left and d/2 units up from last start for next one.*)
(* In the main program the figure is drawn with the four "sides" in succession, each followed by a line segment to glue to the next piece. *)
Top (level); Line (dist, -dist);
Right (level); Line (-dist, -dist);
Bottom (level); Line (-dist, dist);
Left (level); Line (dist, dist);
UNTIL level = numOfLevels
END Sierpinski.
When this version of the code was compiled and run, the following figure was produced.
Careful examination will reveal the three levels drawn. More can be called for, but the diagram becomes somewhat cluttered for illustrative purposes.