Laboratory Exercise

Last Lab! — Advanced Recursion with Line Drawings

Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004

Purpose

Prerequisites

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

Exercise

Design algorithms that draw 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).

Koch Curves

Exercise 15.16 in Algorithms and Data Structures: The Science of Computing defines a kind of jagged curve called a “Koch Curve.” Define a Koch curve’s complexity to be its order (the text defines a Koch curve’s “order” precisely).

Design and code an algorithm for drawing Koch curves. Your algorithm should take the order of the curve and length of each “line segment” as parameters. Note that for anything except an order 0 Koch curve, each “line segment” will really be a lower order Koch curve. Assume as preconditions that the order 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

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).

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

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 on Monday, May 2. Turn in a printout of your subclass, and your derivations of the number of movePen messages each of your algorithms sends. These derivations can be comments in your code, or they can be on a separate sheet of paper.

In addition to your code and derivations, hand in a couple of sentences discussing whether you think the algorithms developed in this lab are practical for drawing high-complexity figures. Base your comments on your mathematical derivations and any informal impressions you formed of your methods’ execution times as you tested the methods. These sentences can appear as comments in your code, or on a separate sheet of paper.