Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004 (Now published by Cengage Learning)
The LineDrawing library class provides simple virtual-pen line
drawings, loosely inspired by the drawing capabilities of the Logo programming
language. These drawings can be a base for a number of exercises in introductory
object oriented programming.
The LineDrawing class facilitates a number of exercises in, and
demonstrations of, concepts from Parts I and II of Algorithms and Data
Structures: The
Science of Computing. In this respect, the class is an alternative to
the Robot class. Line
drawings
support
richer graphics than robots do. Richer graphics leads to more interesting
theorems that can be proved about line drawing algorithms (e.g., that a certain
algorithm always draws a closed figure, that an algorithm correctly draws a regular
polygon, etc.) On the other hand, robots provide better step-by-step animation
as algorithms execute, and are specifically designed to be easy to do timing
experiments with. Line drawings are thus the best choice for exercises that use
line graphics to motivate students, or that try to raise questions
that require non-trivial mathematical proofs to answer.
Line drawings illustrate a number of object oriented programming concepts.
Simply creating one or more LineDrawing objects and sending them
messages to do simple tasks illustrates creation and use of objects. Defining
subclasses
of LineDrawing with methods for tasks other than those provided
by LineDrawing (e.g.,
drawing a polygon instead of a single line segment) demonstrates the use of
subclasses to extend the functionality of their superclass. These demonstrations
readily
expand to include such features as method overriding (have the subclass redefine
one of the standard LineDrawing messages) or polymorphism (define two or more
subclasses that handle the same message(s) in different ways), etc.
Simple drawing algorithms can illustrate any of the standard control structures. There are also a number of natural recursive drawing algorithms, ranging from tail recursions for drawing curves or polygons, to complex recursions for, e.g., fractal patterns.
Correctness proofs and performance analyses of the above algorithms illustrate theoretical analysis of various control structures and recursions. Experimental confirmation of the theoretical results provides a number of examples of experimentation.
LineDrawing objects are visual: each LineDrawing object
appears as a window on the computer screen. The contents of each LineDrawing window
depends on the messages it has been sent.
The coordinate system for a line drawing always has its origin at the center of the drawing’s window, and extends indefinitely in all directions. Coordinates are real-valued, and measured in units of pixels. A drawing that uses coordinates beyond the bounds of its window will be partially visible; users can resize the window to see more of such a drawing.
A file named LineDrawing.java,
which defines the LineDrawing class,
can be downloaded from the Web. Documentation for the class
is also available on the Web. Chapter 15 of Algorithms and Data Structures:
The Science of Computing uses the LineDrawing class
to draw recursive trees; a sidebar entitled “A Line Drawing Class” in
that chapter provides additional brief documentation on the class.
The LineDrawing class is part of
the geneseo.cs.sc package.
Source files that use the class thus usually import it from that package.
Copyright © 2004 Charles River Media. All rights reserved.
Revised Aug. 9, 2005 by Doug Baldwin