Search:

[ 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).

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:




Deprecated: Function split() is deprecated in /storage/content/45/2011745/jonsson.eu/public_html/php/htmlicise.php on line 46
%!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.

Return to previous page

Leave a message

Your name:

Your email: (required)

Message:

Generated by ::emailform::

Last modified Saturday 10 Dec 2011