[ Current revision | Download | Description | PostScript code | References ]
Kochflake.ps
The kochflake.ps PostScript program illustrates how to write compact recursive code for the display of graphics, in this case the Koch »snowflake» fractal. The program employs plain tail recursion directly in PostScript Level 2.
Current revision
Revision 1.0, created 14/08/1996. Copyright © Fredrik Jonsson 1996-2010, under GPL
Download
kochflake.ps [7.2 kB]
The PostScript [1] code constituting the program.
[ download |
view source ]
Description
The Koch snowflake is one of the earliest described fractal curves, appearing in the 1904 article Sur une courbe continue sans tangente, obtenue par une construction géeométrique élémentaire, written by the Swedish mathematician Helge von Koch (1870-1924). In this application example, we employ the »snowflake» variant of the Koch fractal (merely for the sake of its beauty). The Koch snowflake fractal is constructed recursively using the following algorithm.
Algorithm A (Construction of the Koch snowflake fractal).
- A1. [Create initiator.] Draw three line segments of equal length so that they form an equilateral triangle.
- A2. [Line division.] Divide each of the line segments into three segments of equal length.
- A3. [Replace mid segment by triangle.] Draw an equilateral triangle that has the middle segment from step one as its base.
- A4. [Remove base of triangle.] Remove the line segment that is the base of the triangle from step A3.
- A5. [Recursion step.] For each of the line segments remaining, repeat steps A2 through A4.
Figure 1. Graphical output of the kochflake.ps PostScript program, for recursion levels ranging from 1 to 8. This output is similar to the one using the C programming language in the BoxCount estimate of the fractal dimension, with the difference that here the PostScript itself is formulated recursively. Download PDF image | [191 kB]
The triangle resulting after step A1 is denoted as the initiator of the fractal. After the first iteration of steps A1-A4, the result should be a shape similar to the Star of David; this is called the generator of the fractal. The Koch fractal resulting of the infinite iteration of the algorithm of construction has an infinite length, since each time the steps above are performed on each line segment of the figure there are four times as many line segments, the length of each being one-third the length of the segments in the previous stage. Hence, the total length of the perimeter of the fractal increases by 4/3 at each step, and for an initiator of total length L the total length of the perimeter at the nth step of iteration will be (4/3)nL. The fractal dimension is hence D = ln(4)/ln(3)≈1.26, being greater than the dimension of a line (D = 1) but less than, for example, Peano's space-filling curve (D = 2). The Koch fractal is an example of a curve which is continuous, but not differentiable anywhere. The area of the Koch snowflake is 8/5 that of the initial triangle, so an infinite perimeter encloses a finite area. The stepwise construction of the snowflake fractal is illustrated in Fig. 1.
For the computing of the fractal dimension by the box-counting algorithm, see the separate CWEB program BoxCount, in which the documentation includes the example of the Koch fractal.
PostScript code
Listing of the kochflake.ps PostScript code, as used when creating the image in the above example:
%!PS-Adobe-2.0
%%Creator: Fredrik Jonsson <http://jonsson.eu>
%%Title: kochflake.ps
%%BoundingBox: 0 0 595 842
%%DocumentPaperSizes: a4
%%CreationDate: 14-Aug-96
%%EndComments
/sqrtthree {3.0 sqrt} bind def % Global definition
/xc 300 def % Global default page x-coordinate of origo in pt (1/72 in)
/yc 450 def % Global default page y-coordinate of origo in pt (1/72 in)
/scalefac 100 def % Scale in points per dimensionless unit in plot
/pagecoord { % x y (as we enter)
scalefac % x y scalefac
mul % x y*scalefac
yc % x y*scalefac yc
add % x yc+y*scalefac
exch % yc+y*scalefac x
scalefac % yc+y*scalefac x scalefac
mul % yc+y*scalefac x*scalefac
xc % yc+y*scalefac x*scalefac xc
add % yc+y*scalefac xc+x*scalefac
exch % xc+x*scalefac yc+y*scalefac
} bind def
/strcat { % str1[] str2[] (as we enter)
2 % str1[] str2[] 2
copy % str1[] str2[] str1[] str2[]
length % str1[] str2[] str1[] strlen(str2[])
exch % str1[] str2[] strlen(str2[]) str1[]
length % str1[] str2[] strlen(str2[]) strlen(str1[])
add % str1[] str2[] {n=strlen(str2[])+strlen(str1[])}
string % str1[] str2[] newstr[n]
dup % str1[] str2[] newstr[n] newstr[n]
dup % str1[] str2[] newstr[n] newstr[n] newstr[n]
4 3 roll % newstr[n] newstr[n] newstr[n] str1[] str2[]
4 index % newstr[n] newstr[n] newstr[n] str1[] str2[] newstr[n]
length % newstr[n] newstr[n] newstr[n] str1[] str2[] n
exch % newstr[n] newstr[n] newstr[n] str1[] n str2[]
putinterval
3 1 roll
exch
0
exch
putinterval
} bind def
/kochsegment { % Stack: xa ya xb yb depth maxdepth (as we enter)
6 dict begin % Dictionary for 6 args, active until 'end' statement
/maxdepth exch def
/depth exch def
/yb exch def
/xb exch def
/ya exch def
/xa exch def
depth maxdepth eq % Is depth equal to maxdepth?
{
xb yb pagecoord lineto % If so, draw line segment to (xb,yb)
} if
depth maxdepth lt % Otherwise, if depth less than maxdepth,
{ % then construct refined Koch segments.
/xba {xb xa sub 3.0 div} def % (xb-xa)/3.0
/yba {yb ya sub 3.0 div} def % (yb-ya)/3.0
/xca {xa xba add} def % xa+(xb-xa)/3.0
/yca {ya yba add} def % ya+(yb-ya)/3.0
/xcb {xb xba sub} def % xb-(xb-xa)/3.0
/ycb {yb yba sub} def % yb-(yb-ya)/3.0
/xcc {xa xb add 2.0 div yb ya sub 2.0 div sqrtthree div sub} def
/ycc {ya yb add 2.0 div xb xa sub 2.0 div sqrtthree div add} def
xa ya xca yca depth 1 add maxdepth kochsegment % Recursion here, ...
xca yca xcc ycc depth 1 add maxdepth kochsegment % ... here, ...
xcc ycc xcb ycb depth 1 add maxdepth kochsegment % ... here, ...
xcb ycb xb yb depth 1 add maxdepth kochsegment % ... and here.
} if
end
} bind def
/kochflake {
1 dict begin % Dictionary for 1 arg, active until 'end' statement
/yc exch def % Alters the GLOBAL definition of xc
/xc exch def % Alters the GLOBAL definition of yc
/maxdepth exch def
clear
.025 setlinewidth
2 setlinecap
2 setlinejoin
/Helvetica findfont 9 scalefont setfont
maxdepth 0 le
{
-0.7 0 pagecoord moveto
(Please increase maxdepth to at least 1) show
} if
maxdepth 0 gt
{
-0.35 0 pagecoord moveto
(Recursion level ) maxdepth 2 string cvs strcat show
0.0 1.0 pagecoord moveto % Start at the "top of the pyramid"
0.0 1.0 sqrtthree 2.0 div -0.5 1 maxdepth kochsegment
sqrtthree 2.0 div -0.5 sqrtthree neg 2.0 div -0.5 1 maxdepth kochsegment
sqrtthree neg 2.0 div -0.5 0.0 1.0 1 maxdepth kochsegment
stroke
} if
end
} bind def
/title {
/Helvetica-Bold findfont 10 scalefont setfont
80 740 moveto (Recursion in PostScript: The Koch snowflake fractal) show
/Courier findfont 9 scalefont setfont
80 728 moveto (http://jonsson.eu/programs/postscript/koch/) show
} def
%
% Main program: For each level, enter the maximum depth, x- and y-coordinates
% to the stack and single calls to the kochflake routine.
%
title
1 180 620 kochflake % Recursion level 1 centered at (180 pt, 620 pt)
2 420 620 kochflake % Recursion level 2 centered at (420 pt, 620 pt)
3 180 400 kochflake % Recursion level 3 centered at (180 pt, 400 pt)
4 420 400 kochflake % Recursion level 4 centered at (420 pt, 400 pt)
6 180 180 kochflake % Recursion level 6 centered at (180 pt, 180 pt)
8 420 180 kochflake % Recursion level 8 centered at (420 pt, 180 pt)
showpage
References
[1] For information on the PostScript programming language, see for example the PostScript area on the website of Adobe Systems Inc., at http://www.adobe.com/products/postscript/ or the reference book "PostScript Language - Tutorial and Cookbook" (Adison-Wesley, Reading, Massachusetts, 1985), ISBN 0-201-10179-3.