%!

% 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"
% IMPORTANT!!!:  notice how this implementation of the Sierpinski Gasket is different
% from the previous one. In the previous one, a path was formed around the edges of the
% recursed subtriangles. In this implementation, the triangles are formed by actually doing
% the opposite and instead filling in the subtriangle which is NOT recursed upon. 
/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

	% fills the middle inverted triangle
	x size 4 div add y h 2 div add moveto	% top left vertex
	x size 4 div 3 mul add y h 2 div add lineto	% top right vertex
	x size 2 div add y lineto	% bottom 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

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

% To show the way the Sierpinski gasket is built, I show a series of pages with
% gaskets of incrementing 'degree', from zero to N + 1. 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 9 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
/h size dup mul size 2 div dup mul sub sqrt def

beginpage	
	newpath
		x0 y0 moveto
		x0 size add y0 lineto
		x0 size 2 div add y0 h add lineto
		closepath
	0 0 0 setrgbcolor
	fill
	% text label on each page:
	-1.7 y0 0.5 sub moveto
	(A Sierpinski Gasket of degree 1.) show
endpage

0 1 N {
	/i exch def

	beginpage
	
	newpath
		x0 y0 moveto
		x0 size add y0 lineto
		x0 size 2 div add y0 h add lineto
		closepath
	0 0 0 setrgbcolor
	fill

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

	% draw a new gasket of degree 'i' on each page.
	1 0 0 setrgbcolor
	newpath
	  x0 y0 size i sierpinski
	fill


	endpage
} for 

% EOF