%!

% Kyle Touhey - 54116025
% MATH 308 - Term Project 2002
% Draws a Sierpinski Gasket by showing a series of recursive construction steps.


% setup the scaling and font conditions for the pages
/beginpage {
   gsave
   72 dup scale
   1 72 div setlinewidth
   4.125 5.5 translate
   /Helvetica findfont
   0.25 scalefont
   setfont
}def

% draw the page and restore the conditions
/endpage {
   grestore
   showpage
} def


% call with:   "x y size n sierpinski"
% creates a path for a equilateral Serpinski Gasket.
% x & y are the 2D coordinates for the bottom left corner. 
% size is the length of a side of the gasket (or subgasket).
% n is the 'degree' of the depth of recursion. Since an actual
% 	Sierpinski Gasket is infinitely recursed, so need to
% 	set a depth of recursion for drawing purposes.
/sierpinski { 5 dict begin
       % NOTE: it is inefficient to use a dict for recursion but since only need
       % a relatively small number of depth of recursion to make the point, 
       % readability is more important. Otherwise complicated stack manipulation
       % is required.
	/n exch def
	/size exch def
	/y exch def
	/x exch def
	
	/h size dup mul size 2 div dup mul sub sqrt def
	% h is height of the equilateral triangle.
	% from pythagoras: b^2 = c^2 - a^2.
	% so: h = b, b = sqrt(c^2 - a^2)
	% with: c = size, a = size/2
	
	% draws the triangle
	x y moveto	% bottom left vertex
	x size add y lineto	% bottom right vertex
	x size 2 div add y h add lineto	% top vertex
	closepath		% finish back at bottom-left vertex
	
	n 0 gt {
		% split the triangle into separate subtriangles.
		% so three separate recursive calls are needed.
		% the size of each is half that of it's recursed original.
		% the n-counter is decreased for each recursive call 
		% to finally be 0; since the recursion needs a base case.

		% bottom-left subtriangle:
		% at (x, y)
		x	
		y
		size 2 div 
		n 1 sub 
		sierpinski 

		% bottom-right subtriangle:
		% at ((x + size/2), y) 
		x size 2 div add
		y
		size 2 div
		n 1 sub
		sierpinski	

		% top subtriangle:
		% at ((x + size/4), (y + h/2))
		x size 4 div add
		y h 2 div add
		size 2 div
		n 1 sub
		sierpinski 
	} if 

end } def

/counter {
	dup 0 gt {
		1 sub counter dup dup add add
	}{ 
		3
	} ifelse
} def


%-------------------------------------------------------------------

% To show the way the Sierpinski gasket is built, I show a series of pages with
% gaskets of incrementing 'degree', from zero to N. An actual
% Sierpinski Gasket is infinitely recursed but N is sufficient at smaller #'s due to the
% accuracy of the display and the human eye.

/N 8 def 		% N any larger could crash the system!!!!!
		% Also, the # of paths display, displays #paths
		% with the cvs function. Since num paths is caculated
		% exponentially, the value quickly become too large for
		% the cvs function to work. Ex: 3^8 = 19683 but cvs
		% only accepts numbers with <= 4 digits.
		% this is simply a limitation of PostScript - not the algorithm!
/size 8 def   	% size is arbitrarily chosen for visibility. 

% choose initial bottom-left points to centre the gasket.
/x0 size 2 div neg def
/y0 size 3 div neg def

0 1 N {
	/i exch def

	beginpage
	
	% text label on each page:
	-1.7 y0 0.5 sub moveto
	(A Sierpinski Gasket of degree ) show
	i 1 add (     ) cvs show
	(.) show

	% draw a new gasket of degree 'i' on each page.
	newpath
	  x0 y0 size i sierpinski
	stroke

	-3.5 size 3 div moveto
	(# of paths: ) show
	i 7 le {
	   i counter (    ) cvs show
	}{
	   (>9999) show
	} ifelse

	endpage
} for 

% EOF