The Heighway dragon curve can be defined as follows: Starting with a line segment of length L:
45
degrees left or right
If you repeat the process with each new line segment, alternating the turning direction for each adjacent line segment, over and over again (an infinite number of times) you get the Heighway dragon curve. The dragon curve is mathematically interesting because it is an infinitely long curve that occupies a finite area. It was one of many known fractal curves.
Here is an example of constructing a dragon curve (by
Guillaume Jacquenot).
We can use the Turtle
class to generate the dragon curve.
If everytime the turtle moves forward you repeat the above steps then you will generate
the dragon curve. The key to making this work is to encapsulate the above steps in a method,
and have the method call itself. Such a method is called a recursive method,
and we will be studying these in greater detail later in the course. For now, use the
program below to test your Turtle
class. You should get the following output:
The main method of the program creates 4 Turtle
objects (3 of them
using a copy construtor). Each turtle is responsible for drawing one dragon curve.
The important methods in this program are the dragon
and reverseDragon
methods which
draw a dragon curve for each turtle they are given. The methods implement the algorithm
described above except that every move forward step is replaced with another pair of
invocations of dragon
and reverseDragon
. We cannot do this forever without running out
of memory, so an additional method parameter (n
) is used to control the number of times
we recursively invoke the methods. By decreasing n
each time
we invoke the methods we eventually reach the case where n == 0
at which point we finally tell the turtle to move forward and draw the line.
package eecs2030.lab3; import java.awt.Color; import java.util.ArrayList; import java.util.List; public class DragonCurve { private static void dragon(List<Turtle> turtles, double length, int n) { if (n == 0) { for (Turtle t : turtles) { t.move(length); } } else { for (Turtle t : turtles) { t.turn(-45.0); } dragon(turtles, length / Math.sqrt(2.), n - 1); for (Turtle t : turtles) { t.turnLeft(); } reverseDragon(turtles, length / Math.sqrt(2.), n - 1); for (Turtle t : turtles) { t.turn(45.0); } } } private static void reverseDragon(List<Turtle> turtles, double length, int n) { if (n == 0) { for (Turtle t : turtles) { t.move(length); } } else { for (Turtle t : turtles) { t.turn(-45.0); } dragon(turtles, length / Math.sqrt(2.), n - 1); for (Turtle t : turtles) { t.turnRight(); } reverseDragon(turtles, length / Math.sqrt(2.), n - 1); for (Turtle t : turtles) { t.turn(45.0); } } } public static void main(String[] args) { List<Turtle> turtles = new ArrayList<Turtle>(); turtles.add(new Turtle(new Point2(0.5, 0.5))); for (int i = 1; i < 4; i++) { Turtle u = new Turtle(turtles.get(i - 1)); u.turnLeft(); turtles.add(u); } turtles.get(1).setPenColor(Color.RED); turtles.get(2).setPenColor(Color.BLUE); turtles.get(3).setPenColor(Color.GRAY); dragon(turtles, 0.5, 12); } }