Programming Assignment 5|
Due: Wednesday, 11:59pm
Write a program that can create ``H-tree'' patterns like the one on the back of this page (or, like this picture, if you're reading this online). Then develop a program that prints recursive patterns of your own design. The H-tree is another example of a fractal pattern like the Mandelbrot set, but it is also of practical interest as a mechanism for distributing information.
Though the H-tree pattern looks complex, it can be generated with a recursive program very similar (in fact, identical!) to the one that draws the pattern in Fig 5.12 in Algorithms in C (see the Exercises for Week 6). Your task is to make a file htree.c with a recursive function and a main driver that will call the recursive program once and output a Postscript program (in the manner to which we have become accustomed) to produce the desired effect. Think recursively: write a program that draws an H and calls itself 4 times (and includes a termination condition).
Define a constant D that controls the depth of the recursion. First, make sure that your program can draw a single H, with D set to 0. Then, check that it works for one level of recursion (draws five H's), when D is set to 1. That is, your program should produce the following PostScript code when D is 1.
%! 50 50 translate 2 setlinewidth 128 256 moveto 256 0 rlineto stroke 128 128 moveto 0 256 rlineto stroke 384 128 moveto 0 256 rlineto stroke 64 384 moveto 128 0 rlineto stroke 64 320 moveto 0 128 rlineto stroke 192 320 moveto 0 128 rlineto stroke 320 384 moveto 128 0 rlineto stroke 320 320 moveto 0 128 rlineto stroke 448 320 moveto 0 128 rlineto stroke 64 128 moveto 128 0 rlineto stroke 64 64 moveto 0 128 rlineto stroke 192 64 moveto 0 128 rlineto stroke 320 128 moveto 128 0 rlineto stroke 320 64 moveto 0 128 rlineto stroke 448 64 moveto 0 128 rlineto stroke showpage
Your program will be nearly (or completely) debugged when you get to this point. Check that it works for six levels of recursion, but (along with htree.c) submit a file htree3.ps that draws 25 H's (three levels of recursion).
Second, do another, different, recursive design. Experiment with implementing a different box routine, or with changing star. For example, you can have the regions represented by the recursive calls be rectangles of varying size, or you can have them overlap. Or, work with X's or S's instead of H's. Or, work with filled shapes like boxes (to fill a box, trace its' boundary, then use fill instead of stroke. Or, use five recursive calls and pentagons, or whatever. Try introducing some randomness. Originality and creativity in the design will be a factor in your grade.
Extra Credit: Write a program to make the pattern using a
``bottom-up'' method like Program 5.9. Or, write a recursive
PostScript program to produce your pattern.