11: Recursion

Advanced Search Quick Index Instructor's Page Home Blackboard Schedule Syllabus Room Policies Help FAQ's How To's Links Español Chinese Japanese Hide Navigation
Edward Parrish © 2002-2006

11: Recursion
What We Will Cover

Reminders:

Please silence all cell phones and pagers

When class is over, please shut down your computer if it is on.

Continuations

11.1: Recursion

11.1.1: About Recursion

11.1.2: Implementing Recursive Methods

11.1.3: Factorial: Classic Recursion

11.1.4: Recursion and the Call Stack

11.1.5: Recursion Versus Iteration

11.1.6: Iteration to Recursion

11.1.7: Summary

Exercise 11.1

11.2: Introduction to Graphics

11.2.1: Screen Hardware and Layout

11.2.2: Pixels, Colors and Bit Depth

11.2.3: Rendering to Pixels

11.2.4: Creating a Drawing Area

11.2.5: Creating and Drawing Shapes

11.2.6: Filling and Stroking

11.2.7: A Few Words About Drawing Text

11.2.8: Displaying Images

11.2.9: Summary

Exercise 11.2

11.3: Turtle Graphics

11.3.1: About Turtle Graphics

11.3.2: Designing a Turtle

11.3.3: Implementing the Turtle Methods

11.3.4: Creating a Turtle Application

11.3.5: Exploring Turtle Graphics

11.3.6: Drawing Fractals

11.3.7: Summary

Exercise 11.3

Wrap Up

Assignments Due Next: A9-Card Games Redux (4/28/10)
A10-Graphics and Recursion (5/5/10)

Illuminations

Questions from last class?

Homework Questions?

A9-Card Games Redux (4/28/10)

Homework Discussion Questions

How difficult was writing the equals() method for the Card class?

What challenges did you run into using a linked list?

Did anyone test the speed differences between an array, ArrayList and LinkedList?

^ top

11.1: Recursion

Learner Outcomes

At the end of the lesson the student will be able to:

Use recursive algorithms to solve problems

Implement recursive solutions in Java

"To understand recursion, one must first understand recursion."
-- Unknown

^ top

11.1.1: About Recursion

Recursion: when an algorithm is defined in terms of itself.

Recursion is a natural approach to some problems

It allows us to break down a problem into one or more subproblems similar in form to the original problem

Sounds circular, but in practice is not

Recursion divides the problem into two parts:

Recursive step

Base case

The recursive step solves part of the problem

Then it calls the method again and passes it the smaller problem

Eventually the smaller problem becomes easy enough to just solve

The easy-to-solve problem is known as the base case

For Example: Many Hands Make Light Work

What if you were asked to do some repetitive task like: folding the clothes?

You look at the laundry basket and realize you have better things to do

So you fold one item and then ask someone else to fold the clothes

Then you leave as soon as possible

The next person notices your actions and decides to do the same

They fold one item and then ask someone else to fold the clothes

This sequence repeats until all the clothes are folded

Writing this as an algorithm, we have:

Algorithm For Folding Clothes

If the basket is empty, do nothing

Else:

Fold one item

Ask someone else to fold the clothes

Recursive Elements

Notice the recursive nature of the algorithm

The "else" clause contains a reference to itself

To fold the clothes, we ask someone else to fold the clothes

To make sure this algorithm is not an endless passing of the buck, each person does some work

This makes the job passed to the next person smaller

When all the clothes are folded, the chain of asking someone else to fold the clothes is broken

^ top

11.1.2: Implementing Recursive Methods

Recursion is an easy and powerful way of tackling many difficult computing problems

You implement recursion using methods that call themselves

Like a loop, a recursive method must have some way to end

Usually the base case is written first and the recursive step second

Recursive Method Structure
returnType recursiveMethod(parameters) {
    If (stopping condition) { // base case
        // Problem is very easy
        // so solve it and return
    } else { // recursive step
        // Solve part of the problem
        // leaving a smaller problem
        recursiveMethod(arguments);
    }
}
For Example
import java.util.Scanner;

public class FoldClothes {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        System.out.print("How many clothes to fold? ");
        int count = input.nextInt();
        fold(count);
    }

    // The recursive method
    static void fold(int count) {
        if (count == 0) {
            System.out.println("Done folding clothes");
            return;
        } else {
            System.out.print("Folding one item; ");
            count = count - 1;
            System.out.println("number reamining: "
                + count);
            fold(count);
        }
    }
}
^ top

11.1.3: Factorial: Classic Recursion
To develop a recursive algorithm, we must find a way to do the following:

Use a solution to a smaller or easier version of a problem to arrive at the solution itself

Know when the problem is small enough to solve directly

As another example of recursion, let us look at factorials

Recall that a factorial, which is written n!, has the following definition:

When n = 0

n! = 1

And for values of n greater than 0:

n! = n * (n-1) * (n-2) * (n-3) * ... * 1

We can use this definition to write a Java method that implements factorial

One version in psuedocode is:

If n is 0, return 1

Else:

Get the factorial of n - 1

Multiply n time factorial of n - 1
Once we have the psuedocode, conversion to Java code is straightforward:
long factorial(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
}
Note how the method calls itself
Instrumenting the Code

Often improves understanding to print the method calls and returns

However, it does "clutter" the code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.Scanner;

public class FactorialApp {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        FactorialApp app = new FactorialApp();

        System.out.println("I calculate factorials");
        System.out.print("Size of factorial: ");
        int n = input.nextInt();
        System.out.println("main() calls factorial("
            + n + ")");
        long result = app.factorial(n);
        System.out.println("main() gets " + result);
    }

    long factorial(int n) {
        if (n <= 0) {
            System.out.println("factorial(" + n
                + ") " + "returns 1");
            return 1;
        } else {
            System.out.println("factorial(" + n + ") "
                + "calling " + "factorial(" + (n - 1)
                + ")");
            long fact = n * factorial(n - 1);
            System.out.println("factorial(" + n + ") "
                + "returns " + fact);
            return fact;
        }
    }
}
Tracing the Execution
Here is the output of the instrumented code for factorial(3)
Added indentations to see the method calls and returns more easily
main() calls factorial(3)
    factorial(3) calling factorial(2)
        factorial(2) calling factorial(1)
            factorial(1) calling factorial(0)
                factorial(0) returns 1
            factorial(1) returns 1
        factorial(2) returns 2
    factorial(3) returns 6
main() gets 6
Note that the first half makes successive method calls

Until the base case is reached

Second half returns the values of the recursive case
^ top

11.1.4: Recursion and the Call Stack

To understand how Java makes recursive method calls, we must consider a data structure known as a stack

A stack is like a pile of dishes

When a dish is placed on the stack, it is usually placed on top

Known as pushing the dish onto the stack

Similarly, when a dish is removed from the stack, it is taken from the top

Known as popping the dish off the stack

The last dish put on the stack is the first dish removed from the stack

Otherwise you get a lot of broken dishes

Method Call Stack

When a program calls a method, it must know how to return to its caller

To make this possible, it pushes all the information it needs to remember onto a stack:

Return address

Local variables

This stack is known as the method call stack

The information saved is known as the activation record or stack frame

Every method call creates a new activation record

Every time a method returns, its data is popped off the stack

Call Stack for factorial(3)

^ top

11.1.5: Recursion Versus Iteration

All recursive algorithms or methods can be rewritten without recursion

Methods rewritten without recursion usually have loops, so they are called iterative methods

Iteration

Uses repetition structures (for, while or do-while)

Repetition through explicit use of repetition structure

Terminates when the loop-condition fails

Controls repetition by using a counter or similar mechanism

Recursion

Uses selection structures (if, if-else or switch)

Repetition through repeated method calls

Terminates when base case is satisfied

Controls repetition by a parameter reaching the base case

Recursion vs Iteration

Recursion has more overhead than iteration

Recursion is more memory intensive than iteration

Recursion often can be implemented with only a few lines of code

Iterative statements generally run faster and use less memory space
When should you use recursion?

When efficiency is not important and it makes the code easier to understand

^ top

11.1.6: Iteration to Recursion
Common practice is to convert recursive methods to iterative code

Often improves performance

Similarly, you can convert any iterative structures to recursive methods

Not often useful in practice, but a good way to learn about recursion
As an example, we will convert the following program to use recursion:
import java.util.Scanner;

public class SumNums {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        System.out.println("I sum from 1 through n");
        System.out.print("Enter n: ");
        int n = input.nextInt();

        int counter = 1;
        int sum = 0;
        while (counter <= n) {
            //loop body
            sum = counter + sum;
            counter++;
        }
        System.out.println("Total sum = " + sum);
    }
}
General steps are:

Determine what variables the loop uses

Write a recursive method header with one parameter for each variable

Use the condition that causes the termination of the iterative loop as the base case

Develop expressions representing how each variable changes from one iteration to the next and make the recursive call using these expressions

Replace the original iterative loop with a call to the recursive method, using the initial value of each of the variables as arguments

Lets follow these steps with our example
1. Determine the Variables the Loop Uses

Within the loop we see three variables used:

int counter: loop counter for counter-controlled repetition

int n: the upper end of the summation range

int sum: accumulator for the summation

2. Write the Method Header
The method parameter list must include each of our identified variables

Also need to specify a return type for returning the result of our recursion

Since we need the sum as an int value, we specify an int return type
One possible method header is:
int calcSum(int n, int counter, int sum)
3. Write the Base Case
Use the condition that causes the loop termination as the base case
You usually need to negate the condition to get the correct test:
if (counter > n) {
    return sum;
}
4. Write the Recursive Call
Determine how each variable changes from one iteration to the next

Develop expressions that represent the changes

Use the expressions in the recursive call
In our case, we see two changes for each iteration:
sum = counter + sum;
count++;
We can use these statements directly before our recursive call:
sum = counter + sum;
count++;
return calcSum(n, sum, counter);
We see we can convert these simple statements to expressions
Thus we can make the recursive call a "one liner":
return calcSum(n, counter + sum, ++counter);
Why did we change to prefix increment operator for count?
Putting the entire method together, we have:
int calcSum(int n, int sum, int counter) {
    if (counter > n) {
        return sum;
    } else {
        return calcSum(n, counter + sum, ++counter);
    }
}
5. Call the Recursive Method
Replace the original iterative loop with a call to the recursive method

Use the initial value of each of the variables as arguments
For our example, need to call the recursive method with one value:
int sum = calcSum(n, 0, 1;
Two of the arguments are constant values
Common for recursive practitioners to hide the details using another function call:
int calcSum(int n) {
    return calcSum(n, 0, 1);
}
All Together Now

Converting our original program into a recursive program:
import java.util.Scanner;

public class SumNumsRec {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        SumNumsRec app = new SumNumsRec();

        System.out.println("I sum from 1 through n");
        System.out.print("Enter n: ");
        int n = input.nextInt();

        int sum = app.calcSum(n);
        System.out.println("Total sum = " + sum);
    }

    int calcSum(int n) {
        return calcSum(n, 0, 1);
    }

    int calcSum(int n, int sum, int counter) {
        if (counter > n) {
            return sum;
        } else {
            return calcSum(n, counter + sum, ++counter);
        }
    }
}
^ top

11.1.7: Summary

Recursion is when an algorithm is defined in terms of itself

Allows us to define subproblems in similar form to the original

Recursion always has two parts:

Base case

A problem that is closer to the solution

Eventually, the base case is always called

Without the base case, you would have infinite recursion

Since recursion is more computationally expensive, it is common to convert recursion to iteration

To aid our understanding of recursion, we developed a procedure to convert iteration to recursion

Five-Step Procedure

Determine what variables the loop uses

Write a recursive method header with one parameter for each variable

Use the condition that causes the termination of the iterative loop as the base case

Develop expressions representing how each variable changes from one iteration a the next and make the recursive call using these expressions

Replace the original iterative loop with a call to the recursive method, using the initial value of each of the variables as arguments

More Information

For the definition of recursion, see recursion :)

Recursion: from Wikipedia

Check Yourself

What is recursion?

What is a base case?

What happens if you do not have a base case?

How can you tell if a method uses recursion?

What are the steps for converting an iterative algorithm to a recursive algorithm?

^ top

Exercise 11.1

Take two minutes to convert the following iterative code to recursive code:
1
2
3
4
5
6
7
8
public class CountDown {
    public static void main(String[] args) {
        int count;
        for (count = 5; count > 0; count--) {
            System.out.println(count);
        }
    }
}
Five-Step Procedure

Determine what variables the loop uses

Write a recursive method header with one parameter for each variable

Use the condition that causes the termination of the iterative loop as the base case

Develop expressions representing how each variable changes from one iteration a the next and make the recursive call using these expressions

Replace the original iterative loop with a call to the recursive method, using the initial value of each of the variables as arguments

One possible answer

^ top

11.2: Introduction to Graphics

Learner Outcomes

At the end of the lesson the student will be able to:

Discuss video hardware and screen layout

Describe how various colors are created

Explain how images and shapes are rendered to pixels

Create a drawing area on a video screen

Draw simple shapes

Use strokes and fills with shapes

Display text using various fonts

Move, rotate and scale shapes

^ top

11.2.1: Screen Hardware and Layout

To create effective graphics, we need to understand how graphics are displayed

There are two parts to a display screen: the video card and the monitor

The video card stores what to display on the screen in its memory

In addition, the video card tells the monitor what to display and when to display it

The monitor just displays what the video card tells it to

The monitor's screen is divided into tiny little color dots called pixels

Every single pixel is the same size and has an x-coordinate and y-coordinate

The x and y coordinates start from the upper-left corner of the drawing area

Note that coordinates are positive numbers

Video Resolution

How many pixels that can be displayed is known as the video resolution

Resolution depends on the capabilities of the video card and monitor

Older computers had a resolution of 640x480

Today, most computers have a resolution of at least 800x600 and commonly 1024x768 or more

Newer computers have resolutions of 1280x1024, 1600x1200 or 1920x1200

Older CRT monitors can display several resolutions with the same quality

However, newer LCD (liquid crystal display) monitors have a single native resolution that produces the best results

Using non-native resolutions can make the display look fuzzy or blocky

Refresh Rate

Even though an image on your monitor looks solid, each pixel actually fades away after a few milliseconds

Because of this, the monitor has to continuously refresh the display to keep it from fading

The refresh rate is how frequently the monitor refreshes the display

Refresh rate is measured in Hertz (Hz) which means cycles per second

Refresh rates between 75 Hz and 85 Hz are suitable for the human eye on CRT monitors

LCD Monitor Refresh Rate

Unlike CRT monitors, LCD monitor pixels do not just fade away in a few milliseconds

Instead of a refresh rate, LCD monitors have what is known as a refresh cycle

The refresh cycle is how often the capacitor at the designated pixel receives a charge

Charging the capacitors drives the transistors which in turn determines the pixel data at each location

More Information

Browser Display Statistics: Shows the display resolution and color depth reported by Web browsers for people visiting W3 Schools

How Computer Monitors Work

^ top

11.2.2: Pixels, Colors and Bit Depth

Most screens use a color model known as RGB (Red, Green, Blue)

On CRT monitors, three different color dots are excited at different intensities

On LCD monitors, three different transistors are used to control how much light for each color is let through

The number of colors that a monitor can display depends on the number of bits stored for each pixel

Bit depth is the number of bits assigned to each pixel

The most common bit depths are 8, 16, 24 and 32 bits:

8-bit: also known as VGA (Video Gate Array) color, only 2⁸ = 256 colors can be displayed. However only 216 colors are "web-safe".

16-bit: Red = 5, Green = 5, Blue = 6, for a total of 2¹⁶ = 65,536 colors

24-bit: Red = 8, Green = 8, Blue = 8, for a total of 2²⁴ = 16,777,216 colors

32-bit: Same as 24 bit with 8 bits of padding for 32-bit computer word boundaries

Since the human can see only about 10 million colors, 24-bit color is more than enough

16-bit color is a little faster but has less accuracy

Color Coding
Java Supports the standard RGB color model using the Color class

Colors are created from red, green and blue (RGB) values
For example:
Color brown = new Color(204, 102, 0);
RGB values can be specified as either type float (0.0 to 1.0) or type int (0 to 255):
Color(float r, float g, float b) // 0.0 - 1.0
Color(int r, int g, int b)       // 0 - 255
The Color class has several static color constants that you can use in place of numbers, like:
Color.RED
More Information

Class Color: from the Java API

Color Theory Overview and Tutorial

A Standard Default Color Space for the Internet - sRGB

^ top

11.2.3: Rendering to Pixels

Render: calculate and store pixel data

Graphics Context: an object that contains drawing properties and rendering methods for the drawing area

Java can draw images, geometric shapes or text

Every image, shape or text drawn on a screen must be rendered into pixels

To render pixels to a screen or other device, you use an object of:

class java.awt.Graphics

class java.awt.Graphics2D

You use the same rendering methods whether the output device is a screen or a printer

Graphics vs. Graphics2D

Note that class Graphics2D extends class Graphics to support more graphics attributes and provide new rendering methods

The reason for the two classes is historical

Class Graphics was released in the original Java libraries

Provided graphics suitable for most devices of that time

Class Graphics2D was added in Java 1.2 to provide more advanced capabilities

Using inheritance made sure that old code worked with the newer Java versions

While Graphics methods are more straightforward to use, you are much more limited in what you can do with them

You can see some of the methods of both objects listed below

We will look at how to use these methods in the following sections

Some Graphics Methods

Method Description

setColor(someColor) Change the color of the drawing pen.

setFont(someFont) Change the font used for drawing text.

drawLine(...) Draw a line between two points.

drawRect(...) Draw the outline of a rectangle.

fillRect(...) Draw a solid rectangle.

drawRoundRect(...) Draw the outline of a rectangle with rounded corners.

fillRoundRect(...) Draw a solid rectangle with rounded corners.

drawOval(...) Draw the outline of an oval.

fillOval(...) Draw a solid oval.

drawPolygon(...) Draw the outline of a closed polygon.

fillPolygon(...) Draw a filled polygon.

Some Additional Graphics2D Methods

Method Description

setPaint(fillColorOrPattern) Set the fill color or pattern for a shape.

setStroke(penThicknessOrPattern) Set the pen thickness or pattern for a shape.

setRenderingHint(hintKey, hintValue) Set the value for a rendering preference such as whether or not to use anti-aliasing.

setComposite(someAlphaComposite) Set the alpha compositing rules for combining source and destination colors to achieve blending and transparency effects.

translate(...) Move the coordinate system.

rotate(...) Spin the coordinate system.

scale(...) Stretch or shrink the coordinate system evenly in the x or y direction.

shear(...) Stretch or shrink the coordinate system unevenly.

setTransform(someAffineTransform) Change the coordinate system as a combination of translations, scales, flips, rotations, and shears.

draw(someShape) Draw the outline of the shape using the current stroke.

fill(someShape) Fills the interior of a shape using the current fill color or pattern.

^ top

11.2.4: Creating a Drawing Area
In order to draw images, shapes or text, you need a drawing window on the screen
A JFrame provides a suitable window
JFrame frame = new JFrame();
However, you get better results if you do not draw on a JFrame directly

Instead, you usually add another Component, such as a JPanel, to the JFrame

Then you draw on the added component

To draw an image, shape or text, you need to get the graphics context

Note that you cannot simply construct a Graphics object

To get the graphics context, you can use inheritance and override the paintComponent() method as shown in the following example
Drawing with Java 2D
To draw with Java2D, you need an instance of Graphics2D

Graphics2D is subclass of Graphics with more capabilities
To access Graphics2D in paintComponent(), you need to downcast from Graphics
public void paintComponent(Graphics g) {
    super.paintComponent(g);
    Graphics2D g2d = (Graphics2D)g;
    // do something with g2d
}
The following program demonstrates drawing with Java2D shapes
Example Code for a DrawingPanel Using Inheritance
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import java.awt.*;
import java.awt.geom.*;
import javax.swing.*;

public class DrawingPanel extends JPanel {
    static final int WIDTH = 400, HEIGHT = 300;
    static final int FONT_SIZE = 24;
    static final int H = 100, W = 75;
    static final int SP = 15;
    static final int X1 = SP;
    static final int X2 = X1 + W + SP;
    static final int X3 = X2 + W + SP;
    static final int Y1 = 30, Y2 = 50, Y3 = 75;

    public static void main(String args[]) {
        // Setup JFrame
        JFrame frame = new JFrame();
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        // Create a drawing canvas and add it to the frame
        DrawingPanel panel = new DrawingPanel();
        panel.setBackground(Color.BLUE);
        frame.add(panel);

        // Set the frame size and make it visible
        frame.setSize(WIDTH, HEIGHT);
        frame.setVisible(true);
    }

    public void paintComponent(Graphics g) {
        super.paintComponent(g);
        Graphics2D g2 = (Graphics2D) g;

        // Draw text
        g2.setColor(Color.YELLOW);
        Font f = new Font("Serif", Font.BOLD | Font.ITALIC,
                          FONT_SIZE);
        g2.setFont(f);
        g2.drawString("Hello Graphics World!", X1, Y1);

        // Draw simple line
        g2.drawLine(X1, Y2, X3 + X2, Y2);

        // 2D ellipse filled with red-yellow gradient
        g2.setPaint(new GradientPaint(X1, Y2, Color.RED, X2,
            Y3, Color.YELLOW, true));
        Ellipse2D ellipse =
            new Ellipse2D.Double(X1, Y3, W, H);
        g2.fill(ellipse);

        // Draw 2D rectangle in red
        g2.setPaint(Color.RED);
        g2.setStroke(new BasicStroke(8));
        Rectangle2D rect =
            new Rectangle2D.Double(X2, Y3, W, H);
        g2.draw(rect);

        // Draw 2D lines in green and yellow
        g2.setPaint(Color.GREEN);
        Line2D solidLine =
            new Line2D.Double(X3 + W, Y3, X3, Y3 + H);
        g2.draw(solidLine);

        // Draw 2D line using dashed stroke
        g2.setPaint(Color.YELLOW);
        float[] dashPattern = {10};
        BasicStroke dashed = new BasicStroke(4,
            BasicStroke.CAP_ROUND, BasicStroke.JOIN_ROUND,
            10, dashPattern, 0);
        g2.setStroke(dashed);
        g2.draw(new Line2D.Double(X3, Y3, X3 + W, Y3 + H));
    }
}
Overriding Methods
One of the things we did in the above example is override the paintComponent() method

A JPanel has a paintComponent() method

Both the JPanel and our subclass have the same method with the same signature

The method from the subclass overrides (replaces) the superclass method

The new method does not override the superclass method if the parameters are different

Note that overriding and overloading are different concepts as shown below
Also note that you can still call an overridden method using the keyword super
public void paintComponent(Graphics g) {
    super.paintComponent(g);
    // other statements here
}
Overriding Verses Overloading

Overriding Overloading

Same method name

Same method name

Same signature
One method in superclass, one in subclass

Different signature
Both methods can be in same class

More Information

Painting in AWT and Swing

^ top

11.2.5: Creating and Drawing Shapes
Part of the example code above created geometric shapes like these:
Ellipse2D.Double ellipse =
    new Ellipse2D.Double(X1, Y3, W, H);
Rectangle2D.Double rect =
    new Rectangle2D.Double(X2, Y3, W, H);
Line2D.Double solidLine =
    new Line2D.Double(X3 + H, Y3, X3, Y3 + W);
Java has several classes for common geometric objects in the java.awt.geom package

These classes have two versions that store coordinates using either type double (ShapeClass.Double) or float (ShapeClass.Float)

Single precision coordinates may be slightly faster to work with on some platforms (like cell phones)

However, most modern computers have built-in math coprocessors

Thus, you may as well use the ShapeClass.Double version
Drawing and Filling Shapes
Once you create a Shape object, you pass it as an argument to the draw() or fill() methods:
g2.fill(ellipse);
g2.draw(rect);
g2.draw(solidLine);
Note that you can both create and draw a shape in one statement
For instance, to draw the dashed line we used:
g2.draw(new Line2D.Double(X3, Y3, X3 + H, Y3 + W));
Another shortcut way to draw shapes is to use the methods defined in the Graphics class
For example, we did this to draw the white line:
g2.drawLine(X1, Y2, X3 + X2, Y2);
The older methods in Graphics are now mostly convenience methods for drawing simple shapes
Drawing Arbitrary Shapes

To create more complicated geometry, such as polygons, polylines, or stars you use the class GeneralPath

You construct a GeneralPath from lines, quadratic curves and cubic curves

For more information see: Drawing Arbitrary Shapes

More Information

Package java.awt.geom: for a list of built-in shape classes

Drawing Geometric Primitives: from the Java Tutorial

Drawing Arbitrary Shapes: from the Java Tutorial

^ top

11.2.6: Filling and Stroking
Java lets you add fancy fills and outlines to the shapes

To fill a shape, you use the setPaint() method
For example, to fill the interior of a shape with the solid color red:
g2.setPaint(Color.RED);
You can fill a shape with a solid color, a color gradient or a texture
In our DrawingCanvas example we defined a gradient color using GradientPaint
g2.setPaint(new GradientPaint(X1, Y2, Color.RED, X2,
    Y3, Color.YELLOW, true));
The gradient starts with a color at one point and changes proportionally to another color at another point

Your can see this progression in the following diagram:

To fill with a texture you use an image, which we will discuss later
Applying Strokes
A stroke is a mark made by a writing implement such as a pen

Java lets you apply a fancy outline to a shape using a BasicStroke object

To apply a stroke, you use the setStroke() method
For example:
g2.setStroke(new BasicStroke(8));
The constructor of the BasicStroke lets you define several options including

line width: how wide to draw a line

join style: how two lines are joined when they meet

end-cap style: how the ending of a single line with drawn

dash style: how to apply the pattern of blank and filled line segments
In our DrawingCanvas example we defined a BasicStroke dash style:
float[] dashPattern = {10}; // dash pattern
BasicStroke dashed = new BasicStroke(4,
    BasicStroke.CAP_ROUND, BasicStroke.JOIN_ROUND,
    10, dashPattern, 0);
g2.setStroke(dashed);
More Information

Class BasicStroke: from the Java API

Stroking and Filling Graphics Primitives: from the Java Tutorial

^ top

11.2.7: A Few Words About Drawing Text
A font is a style of text

Class Font contains methods and constants for font control

A Font constructor takes three arguments:

Font name: Monospaced, SansSerif, Serif, etc.

Font style: Font.PLAIN, Font.ITALIC and Font.BOLD

Font size: measured in points (1/72 of inch)

Note that point sizes are only approximate
For example:
int FONT_SIZE = 24;
Font f = new Font("Serif",
                  Font.BOLD | Font.ITALIC,
                  FONT_SIZE);
g2.setFont(f);
Method setFont() in a Graphics object can be used to change the current font

Java guarantees that at least three fonts will be available:

Monospaced

SanSerif

Serif

Programs can use the drawString() method to display text on the screen

The first parameter tells which characters to display.

Last two parameters specify the starting location of the text
For example:
g2.drawString("Hello Graphics World", 20, 50);
Anti-Aliasing
The following is a twice-sized image of the message from the drawing canvas

Note that the edges appear jagged

Jagged edges are a common font problem and the solution is called anti-aliasing

Anti-aliasing works by blurring the edges so that the text color blends with the background color

This makes the edges appear sharper as shown in the following where anti-aliasing was applied

Java applies anti-aliasing using RenderingHints

Since RenderingHints are available only in Graphics2D, you must cast the Graphics object to Graphics2D
The following is a revised paintComponent() method for the DrawingCanvas showing how to apply anti-aliasing to text
public void paintComponent(Graphics g) {
    super.paintComponent(g);
    Graphics2D g2 = (Graphics2D) g;

    // Draw text
    g2.setRenderingHint(
        RenderingHints.KEY_TEXT_ANTIALIASING,
        RenderingHints.VALUE_TEXT_ANTIALIAS_ON);
    g2.setColor(Color.YELLOW);
    Font f = new Font("Serif", Font.BOLD | Font.ITALIC,
                      FONT_SIZE);
    g2.setFont(f);
    g2.drawString("Hello Graphics World!", X1, Y1);

    // other drawing code
}
More Information

Class Font

Displaying Antialiased Text by Using Rendering Hints

KEY_TEXT_ANTIALIASING

Lesson: Working with Text APIs

Controlling Rendering Quality

^ top

11.2.8: Displaying Images

You can display images in a JPanel as well as shapes

To display images, we need to:

Load images from a file into a suitable image object

Render the image object using the graphics context

Many methods of the Java API accept either an Image or BufferedImage object

BufferedImage is a subclass of Image, and therefore you can use it in place of Image

Thus, a good choice for storing an image in an object is BufferedImage

Loading a BufferedImage from a File
Let us look at how we can load image files into a BufferedImage object
The easiest way to load a BufferedImage object is using ImageIO.read():
BufferedImage im = ImageIO.read(fileName);
Note that ImageIO.read() is a static method that returns a BufferedImage object

ImageIO.read() can load BMP, GIF, JPEG and PNG files into a BufferedImage object

See Package javax.imageio Description for more information
To use this class and method, we need to import the following classes:
import java.awt.image.BufferedImage;
import java.io.IOException;
import javax.imageio.ImageIO;
Loading Images from JAR Files
A JAR file is a way of packaging code and resources together into a single, compressed file

Like a ZIP file

Resources can be almost anything, including images and sounds
To load images from a JAR, you need to modify how the image is loaded:
BufferedImage im =
    ImageIO.read(getClass().getResource(fileName));
To make loading a BufferedImage easy, we can write a loadImage() method like:
private BufferedImage loadImage(String fileName) {
    BufferedImage im = null;
    try {
        im = ImageIO.read(getClass().getResource(fileName));
    } catch (IOException e) {
        System.out.println("Error loading " + fileName);
    }
    return im;
}
Note the use of the try-catch statement

You need the try-catch statement because reading the image file can cause an error

For instance, if you try to read a file that does not exist

This code will load from either a JAR or a regular file

Thus you might as well use the latter code to allow you the most flexibility storing your images
Rendering the Image
To display the images, you use the drawImage() method of the Graphics class:
g.drawImage(image, x, y, null);
We ue this code as shown below

We can draw using this image:
Class to Draw Images
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.awt.*;
import javax.swing.*;
import java.awt.image.BufferedImage;
import java.io.IOException;
import javax.imageio.ImageIO;

public class ImagePanel extends JPanel {
    static final int WIDTH = 460, HEIGHT = 380;

    public static void main(String args[]) {
        // Setup JFrame
        JFrame frame = new JFrame();
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        // Create a drawing canvas and add it to the frame
        ImagePanel panel = new ImagePanel();
        frame.add(panel);

        // Set the frame size and make it visible
        frame.setSize(WIDTH, HEIGHT);
        frame.setVisible(true);
    }

    private BufferedImage loadImage(String fileName) {
        BufferedImage im = null;
        try {
            im = ImageIO.read(getClass().getResource(fileName));
        } catch (IOException e) {
            System.out.println("Error loading " + fileName);
        }
        return im;
    }

    public void paintComponent(Graphics g) {
        super.paintComponent(g);
        Graphics2D g2 = (Graphics2D) g;

        // Draw an image
        BufferedImage image = loadImage("rose.jpg");
        g2.drawImage(image, 0, 0, null);
    }
}
^ top

11.2.9: Summary
Java provides many graphical capabilities

In this section we looked at how to draw shapes and add color and fancy outlines

Drawing shapes and setting colors is done with the Graphics2D object

Drawing starts in the upper left-hand corner of the screen

One easy way to get access to the Graphics2D object is from a GUI component
A handy object to draw on is a JPanel:
public class DrawingPanel extends JPanel
Which we can add to a JFrame:
JFrame frame = new JFrame();
DrawingPanel panel = new DrawingPanel();
frame.add(canvas);
To draw on a JPanel, you override the paintComponent() method:
public void paint(Graphics g) {
    Graphics2D g2 = (Graphics2D) g;
    // add code here
}
Then you need to downcast the Graphics object to a Graphics2D object

Then you can use the methods of the Graphics2D object to draw a variety of shapes by creating Shape objects

Java has several classes for common geometric objects in the java.awt.geom package

These classes have two versions that store coordinates using either type double (ShapeClass.Double) or float (ShapeClass.Float)
To create these shapes, you use code like:
Ellipse2D.Double ellipse =
    new Ellipse2D.Double(X1, Y3, W, H);
Rectangle2D.Double rect =
    new Rectangle2D.Double(X2, Y3, W, H);
Line2D.Double solidLine =
    new Line2D.Double(X3 + H, Y3, X3, Y3 + W);
Once you create a Shape object, you pass it as an argument to the draw() or fill() methods:
g2.fill(ellipse);
g2.draw(rect);
g2.draw(solidLine);
You can set colors for the shapes by creating a Color object or using one of the predefined colors

To fill a shape, you use the setPaint() method
For example, to fill the interior of a shape with the solid color red:
g2.setPaint(Color.RED);
Also, you can create a fancy outline by creating a BasicStroke and calling the setStroke() method
For example, to create a solid line about 8/72 of an inch wide:
g2.setStroke(new BasicStroke(8));
We also looked at creating fonts and drawing text

In addition, we briefly covered how to transform shapes
Check Yourself

How is the memory for a computer screen organized?

Where is the origin point of the graphics screen?

How do you create a drawing area?

How are various colors created?

What data types does the constructor of the Color class take?

What is meant by the term "graphics context"?

What class do you use to render shapes?

What is meant by the term "anti-aliasing"?

How do you apply fancy outlines to a shape?

How do you apply colors to a shape?

How do you write anti-aliased text to a screen?

What does anit-aliasing do?

What is meant by transforming a shape?

How do you return a shape to its original "untransformed" condition?

^ top

Exercise 11.2

Take one minute to read over the following Quick Quiz questions before we discuss them.

Quick Quiz

Which of the following is NOT one of the basic colors combined to create colors in the Color class?

Red

Green

Blue

Magenta

You can draw shapes directly on a JFrame.
True
False

To render shapes to a screen, you use an object of the class Graphics or .

^ top

11.3: Turtle Graphics

Objectives

At the end of the lesson the student will be able to:

Design a turtle class

Use turtle graphics to create shapes

Draw simple fractals using turtle graphics

^ top

11.3.1: About Turtle Graphics

Turtle graphics were invented by Seymour Papert in the late 1960s

He invented turtle graphics to provide a simple graphics environment that people could use to learn programming

Turtle graphics were originally added to the Logo programming language

Since then, turtle graphics have been developed for many other programming languages

In this section, we will look at how to design a a simple turtle graphics program in Java

The Turtle Graphics Environment

A turtle exists in a graphics window often called the "world"

The turtle itself has a position int its world, an orientation and a pen on its tail

The pen has attributes such as color, width, up and down

The up and down attributes let the pen be retracted so that the turtle can either draw as it moves or not

A turtle draws by making lines, which makes it a vector-based system

To draw with a turtle, you reason about the turtle's motion by imagining that you are the turtle

Thus all turns are from the perspective of the turtle

A turtle has some simple commands as shown in the table below

Some Commonly Implemented Turtle Graphics Commands

Function Action Taken

forward amount Move the turtle forward the given amount in the direction it is heading.

left degrees Turn the turtle to the left (counter-clockwise) the given number of degrees from the current direction it is heading.

penDown Start drawing as the turtle moves.

penUp Stop drawing when the turtle moves.

More Information

Turtle graphics: article from Wikipedia

^ top

11.3.2: Designing a Turtle

In this section we start our design of a turtle

As with all things Java, we create our design using a class

Within the class we define the behaviors we want in a turtle

In addition we specify a private data structure that acts as a turtle's memory

You can see the first "stubbed out" version of our class listed below

First Design of a Turtle Class
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Turtle1 {
    private double angle;
    private double x, y;
    private boolean drawing;

    public Turtle1() { }
    public Turtle1(double x, double y, double angle) { }
    public void forward(double amount) { }
    public void left(double degrees) { }
    public void penDown() { }
    public void penUp() { }
    public String toString() { return "toString"; }

    // For unit testing
    public static void main(String[] args) {
        Turtle1 myrtle = new Turtle1();
        Turtle1 boggy = new Turtle1(100, 100, -90);
        myrtle.forward(50);
        myrtle.left(90);
        myrtle.penDown();
        myrtle.penUp();
    }
}
Unit Testing

When developing a class you should develop unit tests for the class

A unit is the smallest testable part of the program, which is a method

Unit testing verifies that the source code for the class is working correctly

Ideally, you should develop tests as you develop each method

Then you can have more confidence that your code is working correctly while you are developing or changing your code

The tests shown above are very simple

As you develop your methods, you can develop more comprehensive tests

^ top

11.3.3: Implementing the Turtle Methods
Now let us implement the methods of the Turtle
The constructors are straightforward:
Turtle() {
    drawing = true;
}

Turtle(double x, double y, double angle) {
    drawing = true;
    this.x = x;
    this.y = y;
    this.angle = angle;
}
Also, the penDown() and penUp() methods are easy:
public void penDown() {
    drawing = true;
}

public void penUp() {
    drawing = false;
}
The method left() requires us to add the degrees to the current angle
In addition, we clip the angle to 360 degrees:
public void left(int degrees) {
    angle = (angle + degrees) % 360;
}
Moving the turtle forward is more challenging

We need to draw a line, which will require a graphics context

The easy way to get the graphics context is to add it to the parameter list

Also, we need to remember our trigonometric functions and their relation to the unit circle

We can calculate the distance to move in the x and y directions using the sine and cosine of the angle

To work with sine and cosine, we need to convert the angle to radians, which we can do using Math.toRadians()
Putting all this together we have:
public void forward(double amount, Graphics2D g2) {
    double oldX = x;
    double oldY = y;
    x += amount * cos(toRadians(angle));
    y += amount * sin(toRadians(angle));
    if (drawing) {
        g2.draw(new Line2D.Double(oldX, oldY, x, y));
    }
The following lists a Turtle with all the methods implemented

Note that testing the forward() method is problematic because of the need for a graphics context

Providing unit tests in a graphics environment is more challenging
Turtle Class with Methods Implemented
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import java.awt.*;
import java.awt.geom.*;
import static java.lang.Math.*;

public class Turtle {
    private static final int FULL_CIRCLE = 360;
    private double angle;
    private double x, y;
    private boolean drawing;

    Turtle() {
        drawing = true;
    }

    Turtle(double posX, double posY, double startAngle) {
        drawing = true;
        x = posX;
        y = posY;
        angle = startAngle;
    }

    public void forward(double amount, Graphics2D g2) {
        double oldX = x;
        double oldY = y;
        x += amount * cos(toRadians(angle));
        y += amount * sin(toRadians(angle));
        if (drawing) {
            g2.draw(new Line2D.Double(oldX, oldY, x, y));
        }
    }

    public void left(double degrees) {
        angle = (angle + degrees) % FULL_CIRCLE;
    }

    public void penDown() {
        drawing = true;
    }

    public void penUp() {
        drawing = false;
    }

    public String toString() {
        return "(" + x + ", " + y + ") angle: " + angle
            + ", drawing: " + drawing;
    }

    // For unit testing
    public static void main(String[] args) {
        Turtle myrtle = new Turtle();
        System.out.println(myrtle);
        final Turtle BOGGY = new Turtle(100, 100, -90);
        System.out.println(BOGGY);
        final double ANGLE = 45;
        myrtle.left(ANGLE);
        System.out.println(myrtle);
        myrtle.penUp();
        System.out.println(myrtle);
        Frame test = new Frame();
        Graphics2D g2 = (Graphics2D) test.getGraphics();
        final int SIZE = 100;
        myrtle.forward(SIZE, g2);
        System.out.println(myrtle);
        myrtle.penDown();
        System.out.println(myrtle);
    }
}
^ top

11.3.4: Creating a Turtle Application
To create an application, we need a world for our Turtle to move within
We can extend a JPanel for drawing like we did for our other graphics program:
public class TurtleApp extends JPanel {
After setting the size and background, we add the JPanel to a JFrame
To draw, we override the paintComponent() method of our JPanel superclass
public void paintComponent(Graphics g) {
    super.paintComponent(g); // housekeeping
We want to work with the extended Graphics2D object, so we downcast the Graphics to Graphics2D:
Graphics2D g2 = (Graphics2D) g; // downcasting
Now we can set colors and line styles for drawing, just like we did before
To draw shapes with a Turtle, we can write methods such as:
public void drawSquare(double size, Graphics2D g2) {
    turtle.forward(size, g2);
    turtle.left(90);
    turtle.forward(size, g2);
    turtle.left(90);
    turtle.forward(size, g2);
    turtle.left(90);
    turtle.forward(size, g2);
    turtle.left(90);
}
You can see a complete Turtle application in the listing that follows
Example Turtle Application
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import java.awt.*;
import javax.swing.*;

public class TurtleApp extends JPanel {
    public static final int WIDTH = 640, HEIGHT = 640;
    private JFrame frame;
    private Turtle turtle;

    // Start the application
    public static void main(String[] args) {
        TurtleApp w = new TurtleApp();
    }

    // Constructor sets up the graphics environment
    public TurtleApp() {
        setBackground(Color.WHITE);
        setPreferredSize(new Dimension(WIDTH, HEIGHT));
        frame = new JFrame("Turtle TurtleApp");
        frame.setDefaultCloseOperation(frame.EXIT_ON_CLOSE);
        frame.add(this);
        frame.pack();
        frame.setVisible(true);
    }

    // Draw with the turtle
    public void paintComponent(Graphics g) {
        super.paintComponent(g); // housekeeping
        Graphics2D g2 = (Graphics2D) g; // downcasting
        // Clear the background
        g2.setColor(getBackground());
        g2.fillRect(0, 0, getWidth(), getHeight());
        // Set colors and strokes
        g2.setPaint(Color.BLACK);
        g2.setStroke(new BasicStroke(2));
        // Draw with the turtle
        turtle = new Turtle(WIDTH / 2, HEIGHT / 2, 0);
        drawSquare(100, g2);
    }

    // Draw a square
    public void drawSquare(double size, Graphics2D g2) {
        turtle.forward(size, g2);
        turtle.left(90);
        turtle.forward(size, g2);
        turtle.left(90);
        turtle.forward(size, g2);
        turtle.left(90);
        turtle.forward(size, g2);
        turtle.left(90);
    }
}
^ top

11.3.5: Exploring Turtle Graphics

Using a turtle, one can draw lines

From the lines, one can construct simple shapes such as squares and triangles

Also, with control flow and functions, one can draw circular shapes

To draw a circular shape, like a spiral, you move the turtle forward a small amount and then turn a small amount

Repeating this process many times produces circles, spirals and other curved shapes

The following program draws a spiral in two different ways

More Turtle Drawings
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.awt.*;
import javax.swing.*;

public class TurtleSpiral extends JPanel {
    public static final int WIDTH = 640, HEIGHT = 640;
    private JFrame frame;
    private Turtle turtle;

    // Start the application
    public static void main(String[] args) {
        TurtleSpiral w = new TurtleSpiral();
    }

    // Constructor sets up the graphics environment
    public TurtleSpiral() {
        setBackground(Color.WHITE);
        setPreferredSize(new Dimension(WIDTH, HEIGHT));
        frame = new JFrame("Turtle TurtleSpiral");
        frame.setDefaultCloseOperation(frame.EXIT_ON_CLOSE);
        frame.add(this);
        frame.pack();
        frame.setVisible(true);
    }

    // Draw with the turtle
    public void paintComponent(Graphics g) {
        super.paintComponent(g); // housekeeping
        Graphics2D g2 = (Graphics2D) g; // downcasting
        g2.setColor(getBackground());
        g2.fillRect(0, 0, getWidth(), getHeight());
        g2.setPaint(Color.RED);
        g2.setStroke(new BasicStroke(2));

        turtle = new Turtle(WIDTH / 2, HEIGHT / 2, 0);
        drawSpiral(3, g2);
        g2.setPaint(Color.BLUE);
        drawSpiralRec(3, g2);
    }

    // Loop-based spiral
    public void drawSpiral(double size, Graphics2D g2) {
        while (size < 30) {
            turtle.forward(size, g2);
            turtle.left(15);
            size = size * 1.02;
        }
    }

    // Recursive spiral
    public void drawSpiralRec(double size, Graphics2D g2) {
        if (size > 30) {
            return;
        } else {
            turtle.forward(size, g2);
            turtle.left(15);
            drawSpiralRec(size * 1.02, g2);
        }
    }
}
^ top

11.3.6: Drawing Fractals

Notice in the previous example the recursive version of the spiral

Combined with recursion, turtle graphics is a useful way to draw recursively defined shapes such as fractals:
A fractal is "a rough or fragmented geometric shape that can be split into parts, each of which is (at least approximately) a reduced-size copy of the whole"

Mandelbrot, B.B. (1982). The Fractal Geometry of Nature. W.H. Freeman and Company.. ISBN 0-7167-1186-9.

A fractal is often based on a recursively defined mathematical equation

As an example of a simple fractal, consider a shape based on the letter Y

Each of the branches of the Y can themselves be the base of another Y

Continue this branching, we soon see a tree appear

The following program draws this simple branching out to some specified number of branching levels

In addition, you can change the angle of the branches and the "growth" of the length of the branches

Turtle Branching
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import java.awt.*;
import javax.swing.*;

public class TurtleBranch extends JPanel {
    public static final int WIDTH = 640, HEIGHT = 640;
    private JFrame frame;
    private Turtle turtle;

    // Start the application
    public static void main(String[] args) {
        TurtleBranch w = new TurtleBranch();
    }

    // Constructor sets up the graphics environment
    public TurtleBranch() {
        setBackground(Color.WHITE);
        setPreferredSize(new Dimension(WIDTH, HEIGHT));
        frame = new JFrame("Turtle Branching");
        frame.setDefaultCloseOperation(frame.EXIT_ON_CLOSE);
        frame.add(this);
        frame.pack();
        frame.setVisible(true);
    }

    // Draw with the turtle
    public void paintComponent(Graphics g) {
        super.paintComponent(g); // housekeeping
        Graphics2D g2 = (Graphics2D) g; // downcasting
        g2.setColor(getBackground());
        g2.fillRect(0, 0, getWidth(), getHeight());
        Color forestGreen = new Color(34, 139, 34);
        g2.setPaint(forestGreen);

        turtle = new Turtle(WIDTH / 2, 600, 0);
        turtle.left(-90);
        drawTree(200, 45, 0.6, 10, g2);
    }

    // Draw a Y shape
    public void drawTree(double size, double angle,
            double growth, int level, Graphics2D g2) {
        if (level == 0) {
            turtle.forward(size, g2);
            turtle.forward(-size, g2);
        } else {
            turtle.forward(size, g2);
            turtle.left(angle);
            drawTree(size * growth, angle, growth,
                level - 1, g2);
            turtle.left(-angle);
            turtle.left(-angle);
            drawTree(size * growth, angle, growth,
                level - 1, g2);
            turtle.left(angle);
            turtle.forward(-size, g2);
        }
    }
}
More Information

Famous Fractals: fractals famous enough to have a name from thinkquest.org

Fractal: from Wolfram Research

Fractal: Wikipedia article

L-system: Wikipedia article on Lindenmayer systems

^ top

11.3.7: Summary

In this section we looked at how to implement turtle graphics in Java

Turtle graphics are a vector-based system based on drawing with lines

To draw with a turtle, you reason about the turtle's motion by imagining that you are the turtle

Thus all turns are from the perspective of the turtle

We developed a simple Turtle class that implemented the basic commands of turtle graphics

While developing the class, we developed simple unit tests as well

With unit testing, we had some confidence that our program worked

When we were done with our Turtle class, we created a simple application to draw with the turtle

Our graphics application was based on the drawing panel we developed previously

We simply added a Turtle to the drawing

With the turtle, we discovered how to draw shapes, including curved shapes

In addition, we explored recursively defined shapes such as fractals

Check Yourself

In the turtle environment, how does one reason about drawing?

What is unit testing?

Why is unit testing useful?

When should you develop unit tests?

How does one draw a square with turtle graphics?

How does one draw a curved shape with turtle graphics?

What is a fractal?

^ top

Exercise 11.3

Take one minute to prepare an answer the following question.

What methods to you call to draw an equilateral triangle with a turtle?

^ top

Wrap Up

Due Next:
A9-Card Games Redux (4/28/10)
A10-Graphics and Recursion (5/5/10)

^ top
Home | Blackboard | Schedule | Room Policies | Syllabus
Help | FAQ's | HowTo's | Links Last Updated: May 09 2010 @22:30:20

What We Will Cover

Illuminations

Questions from last class?

Homework Questions?

Homework Discussion Questions

11.1: Recursion

Learner Outcomes

11.1.1: About Recursion

For Example: Many Hands Make Light Work

Algorithm For Folding Clothes

Recursive Elements

11.1.2: Implementing Recursive Methods

Recursive Method Structure

For Example

11.1.3: Factorial: Classic Recursion

Instrumenting the Code

Tracing the Execution

11.1.4: Recursion and the Call Stack

Method Call Stack

Call Stack for factorial(3)

11.1.5: Recursion Versus Iteration

Iteration

Recursion

Recursion vs Iteration

11.1.6: Iteration to Recursion

1. Determine the Variables the Loop Uses

2. Write the Method Header

3. Write the Base Case

4. Write the Recursive Call

5. Call the Recursive Method

All Together Now

11.1.7: Summary

Five-Step Procedure

More Information

Check Yourself

Exercise 11.1

Five-Step Procedure

11.2: Introduction to Graphics

Learner Outcomes

11.2.1: Screen Hardware and Layout

Video Resolution

Refresh Rate

LCD Monitor Refresh Rate

More Information

11.2.2: Pixels, Colors and Bit Depth

Color Coding

More Information

11.2.3: Rendering to Pixels

Graphics vs. Graphics2D

Some Graphics Methods

Some Additional Graphics2D Methods

11.2.4: Creating a Drawing Area

Drawing with Java 2D

Example Code for a DrawingPanel Using Inheritance

Overriding Methods

Overriding Verses Overloading

More Information

11.2.5: Creating and Drawing Shapes

Drawing and Filling Shapes

Drawing Arbitrary Shapes

More Information

11.2.6: Filling and Stroking

Applying Strokes

More Information

11.2.7: A Few Words About Drawing Text

Anti-Aliasing

More Information

11.2.8: Displaying Images

Loading a BufferedImage from a File

Loading Images from JAR Files

Rendering the Image

Class to Draw Images

11.2.9: Summary

Check Yourself

Exercise 11.2

Quick Quiz

11.3: Turtle Graphics

Objectives

11.3.1: About Turtle Graphics

Call Stack for `factorial(3)`

`Graphics` vs. `Graphics2D`

Example Code for a `DrawingPanel` Using Inheritance

Loading a `BufferedImage` from a File

First Design of a `Turtle` Class

`Turtle` Class with Methods Implemented