Advanced Recursion with Line Drawings

Purpose

Background

This lab consists of a number of exercises about designing, coding, and analyzing algorithms that generate various recursive line drawings of a sort loosely known as “fractals.”

Fractals

Mathematically, a fractal is a curve in which small parts, magnified, look just like the whole in terms of jaggedness, general shape, etc. For example, coastlines are often described as having this property — the coastline of an entire continent has features (bays, peninsulas, etc.) that appear in a similar way, but on a smaller scale, in the coastline of a small region of the continent. In a mathematical fractal, unlike a coastline, this “self-similarity” repeats to infinitely fine levels of detail.

Algorithmically, some startlingly beautiful patterns can be generated by borrowing fractals’ self-similarity at multiple scales. Typically, one starts by thinking of some simple figure, and then recursively embeds smaller versions of that figure in the original. Because of their relationship to mathematical fractals, the resulting images are often called “fractal” images.

Line Drawings

This lab uses a class named LineDrawing, that represents drawings made from colored line segments. This class is formally introduced in chapter 15 of Algorithms and Data Structures: The Science of Computing. For a summary of its abilities, see the sidebar entitled “A Line Drawing Class” in that chapter. Full documentation is available as described in the “Final Details” section of this document.

Programs that use the LineDrawing class need to include a file named LineDrawing.java. See the “Final Details” section below for information on where to find this file.

Any Java source file that refers to the LineDrawing class should “import” it, via the statement

    import geneseo.cs.sc.LineDrawing;

at the beginning of the file.

Exercise

Design algorithms that draw each of the fractal shapes described below. Code each algorithm in Java, as a method for a subclass of LineDrawing. Finally, derive expressions for the number of movePen messages each algorithm sends, as a function of the complexity of the shape (the “complexity” of each kind of shape is defined in the descriptions of the shapes, below).

“T”s

Define a “fractal T” to be a shape inspired by the letter “T,” but with the cross-line at the top made of smaller fractal Ts. More precisely,

• A fractal T of complexity 0 and length n is a straight line n pixels long.
• A fractal T of complexity c > 0 and length n is a straight line n pixels long, joined at one end to two fractal Ts of complexity c-1 and length n/2.

For example, here are fractal Ts of complexities 0, 1, 2, and 3:

Design and code a fractal T algorithm that takes the complexity and length of the T as parameters. Assume as preconditions that the complexity is a natural number, and that the length is a positive real number. Adopt additional preconditions on the pen’s position, heading, color, etc. as needed.

Stars

Define a “fractal star” as follows:

• A star of complexity 0 is nothing (i.e., no lines or other image)
• A star of complexity c > 0 is a set of 5 lines radiating from a central point, with a complexity c-1 star centered at the end of each line.

Note that the lines in the recursive complexity c-1 stars are shorter than the lines in the complexity c star. Also note that although the above definition says stars have 5 lines, one can actually use different numbers, and get different appearances. Coloring the lines differently for each complexity level can also make the stars visually more interesting (the examples below illustrate this idea).

For example, here are stars of complexity 1 (on the left) and 3 (on the right):

To show how ornate a star can become, here is a complexity 5 star based on 7 rather than 5 lines:

Design and code a fractal star algorithm that takes the complexity of the star as a parameter. The algorithm may also take other parameters if desired, for instance the number or length of the lines. Assume as preconditions that the complexity is a natural number, and the pen is positioned at the point from which the lines should radiate.

Final Details

The Line Drawing Class

LineDrawing.java can be downloaded from the Web.

Documentation on the LineDrawing class is also available on the Web. The main documentation page is an index to documentation for all the Java classes written for use with Algorithms and Data Structures: The Science of Computing. To see the documentation for a specific class, click on that class’s name in the left-hand panel of the page.

Submitting Your Work

This lab is due no later than 5:00 PM on Monday, May 3. Turn in a printout of your subclass, and the derivations of the number of movePen messages each algorithm sends. The derivations may be on a separate sheet of paper, or in comments within the subclass.

Copyright © 2004. Charles River Media. All rights reserved.

Revised Apr. 22, 2004