Advanced Recursion with Line Drawings

Site Index

Purpose

This lab provides practice designing and analyzing relatively sophisticated recursive algorithms. “Relatively sophisticated” here means algorithms in which a single arm of the main conditional sends multiple recursive messages.

Prerequisites

Understanding of chapter 15 (“Exponential Growth”) of Algorithms and Data Structures: The Science of Computing, through section 15.2. Exercises 15.16 and 15.17 in the book are closely related to the problems in this lab, and can be good practice for it.

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.” At least one of these algorithms (one that draws skylines) requires understanding of Java’s mathematical function and random number library classes.

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.

Random Numbers

The “Skylines” exercise below requires generating random numbers, and other exercises (e.g., “Bushes”) could involve them. Java provides a library class named Random that represents random number generators. Using this class to generate random numbers involves three steps:

1. Import the class into the client program
2. Create a random number generator object
3. Send the random number generator appropriate messages to produce random numbers.

Import the Class

The Random class is defined in a package named java.util, so the statement

    import java.util.Random;

must appear near the beginning of any program that uses random number generators.

Create a Random Number Generator

Random number generators are objects, and so must be created via the new operator. The easiest way to initialize a random number generator is to use Random’s parameterless constructor, for example

    Random generator = new Random();

Beware, however, that this constructor initializes the random number generator based on the current time, as measured by System.currentTimeMillis. Two random number generators created during the same clock tick will therefore generate exactly the same sequence of numbers (since algorithmic random number generators do not generate truly random sequences of numbers, they generate fixed sequences that have statistical properties similar to truly random ones). The easiest way to avoid this problem is to design programs so that they only need one random number generator object.

Send Messages

A random number generator can generate random numbers in many different ways, depending on what messages are used to request random numbers. Each message returns a single random-looking number. A single random number generator can receive any mixture of the following messages.

• To generate a random integer, use the nextInt message. This message takes an integer, n, as its parameter, and returns an integer uniformly distributed between 0 and n-1 (i.e., each integer in that range is equally likely to be returned). For example

        int coinFlip = generator.nextInt( 2 );

• To generate a uniformly distributed real number, use the nextDouble message. This message returns a random double value, uniformly distributed between 0 and 1. For example

        double probability = generator.nextDouble();

• Many random values arising in nature have a so-called “normal” or “Gaussian” distribution. Roughly speaking, Gaussian random numbers cluster around some average value, with numbers close to the average being more likely than numbers far from it. To generate numbers from a Gaussian distribution, send a random number generator a nextGaussian message. This message returns a random number from a Gaussian distribution with average 0; while any real number could theoretically be returned, there is a roughly 70% chance that the number will be between -1 and +1. The returned value is of type double. For example

        double gauss = generator.nextGaussian();

The nextGaussian message is the one most likely to be useful in this lab.

More Information

A Tutorial on Java’s random number generators is available on the Web, at http://cs.geneseo.edu/~baldwin/reference/random.html. The information given above is based on material in that tutorial.

For complete information on Java random number generators, see the on-line Documentation for the Random Class, at http://java.sun.com/j2se/1.4.2/docs/api/index.html.

Mathematical Functions

The “Skylines” exercise below requires mathematical operations more complicated than Java’s built-in arithmetic operators. In particular, that exercise requires computing square roots and arctangents. Static methods that compute these functions are available in Java’s Math class.

Method Math.sqrt calculates the square root of its argument. Both the argument and result are double-precision real numbers. For example

    double length = Math.sqrt( y );

The Math.atan method calculates the arctangent of its argument. The argument and result are both double-precision real numbers. The result is implicitly in radians, and is always between -π/2 and +π/2. For example

    double angle = Math.atan( 1.0 );
    // angle is about 0.785 after the above statement,
    // because the angle whose tangent is 1.0 is 45 degrees, or 0.785 radians

To convert radians to degrees (which LineDrawing uses for all its angles), multiply by 180/π. The Math class provides a definition for π, in constant Math.PI. For example, the following code calculates an angle in degrees equivalent to angle a in radians:

    double angleInDegrees = a * 180.0 / Math.PI;

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.

Bushes

Define a bush of complexity 0 to be nothing (i.e., an empty picture), while a bush of complexity c > 0 is a fan of lines, each of which has a bush of complexity c-1 at its end. For example, here are bushes of complexity 1, 2, and 3:

Design and code a fractal bush algorithm that takes the bush’s complexity as a parameter. Assume as preconditions that the complexity is a natural number, and that the pen is positioned at the base of the bush (i.e., the point from which the lines fan out).

Note that many properties of a bush aren’t specified by the above definition: the number of lines in the “fan” of lines, the angle between those lines, the lengths of the lines, or their colors, among other things. Choose values for these properties in any way that yields aesthetically pleasing bushes, or make them additional parameters to the bush message. (In the above examples, there are 3 lines in a fan, they are separated by 20 degrees, the lines from a complexity c bush are 10c pixels long, and lines are black, unless they are in a complexity 1 bush, in which case they are green.)

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.

Skylines

One of the oldest uses of fractals in graphics is to generate terrains. In two dimensions, the idea works as follows (the idea generalizes to three dimensions by displacing the centers of flat surfaces rather than the midpoints of straight lines):

Start with a straight line:

Move the midpoint of this line upward by a random amount. While the exact value of this displacement is random, the range of possible values should be proportional to the length of the line (i.e., a long line can have its midpoint displaced by a greater amount than a short line):

Recursively repeat the same process with each of the two shorter lines that result. In other words, randomly displace their midpoints to get two shorter segments, then displace their midpoints, etc. Stop when the individual segments are too short to be worth splitting. Draw only these shortest segments. The final result will look something like a silhouette or skyline of a hill or valley:

Note that it should be possible to have either upward or downward displacements at any time in the recursion. If the first displacement is upward, the resulting skyline will look generally mountainous; if the first displacement is downward the skyline will look more like a valley.

Define the complexity of a skyline by saying that a straight line is a complexity 0 skyline. Carrying out the displace-the-midpoint process through c levels of recursion produces a complexity c skyline. (The finished skyline above has complexity 8.)

The skyline algorithm requires drawing lines to displaced midpoints. But the LineDrawing class doesn’t have messages to draw lines between points, it has messages to draw lines of a certain length and a certain heading. However, headings and distances for drawing skylines can be calculated from initial line lengths and displacements. Specifically, suppose that a baseline of length x should have its midpoint displaced by distance d, as shown here:

The line to the displaced midpoint (the sloping red line in the diagram) is the hypotenuse of a right triangle whose other sides have length x/2 and d. The length of this line can thus be calculated using the Pythagorean Theorem. Furthermore, the angle it makes with the original line (Θ in the above diagram) has tangent d/(x/2), so the amount by which to change the pen’s heading is tan^-1( d/(x/2) ).

Design and code a fractal skyline algorithm that takes the complexity of the skyline, and the length of the baseline, as its 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, and other properties as needed.

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

Turn in your solution to this exercise as directed by your instructor.

Copyright © 2004 Charles River Media. All rights reserved.

Revised Aug. 8, 2005 by Doug Baldwin

Site Index