DS Sierpinski Triangle

Section 4.8 Sierpinski Triangle

Another fractal that exhibits the property of self-similarity is the Sierpinski triangle. An example is shown in Figure 4.8.1. The Sierpinski triangle illustrates a three-way recursive algorithm. The procedure for drawing a Sierpinski triangle by hand is as follows: Start with a single large triangle. Divide this large triangle into four new triangles by connecting the midpoint of each side. Ignoring the middle triangle that you just created, apply the same procedure to each of the three corner triangles. Each time you create a new set of triangles, you recursively apply this procedure to the three smaller corner triangles. You can continue to apply this procedure indefinitely if you have a sharp enough pencil. Before you continue reading, you may want to try drawing the Sierpinski triangle yourself, using the method described.

Listing 4.8.2 shows the Java program to produce this drawing.

import java.awt.Color;
import java.awt.geom.Point2D;

public class SierpinskiTriangles {

    public static void drawTriangle(Point2D.Double[] points, Color color,
      Turtle t) {
        t.penUp();
        t.goTo(points[0].x, points[0].y);
        t.penDown();
        t.setColor(color);
        t.beginFill();
        t.goTo(points[1].x, points[1].y);
        t.goTo(points[2].x, points[2].y);
        t.goTo(points[0].x, points[0].y);
        t.endFill();
    }

    public static Point2D.Double midpoint(Point2D.Double p1,
      Point2D.Double p2) {
        return new Point2D.Double((p1.x + p2.x) / 2.0, (p1.y + p2.y) / 2.0);
    }

    public static Color[] colorMap = {
        Color.BLUE, Color.RED, Color.GREEN,
        Color.WHITE, Color.YELLOW, Color.MAGENTA, Color.ORANGE};

    public static void sierpinski(Point2D.Double[] points, int level,
      Turtle t) {
        drawTriangle(points, colorMap[level], t);

        if (level > 0) {
            Point2D.Double[] triangle1 = {
                points[0], midpoint(points[0], points[1]),
                midpoint(points[0], points[2]) };

            sierpinski(triangle1, level -1, t);

            Point2D.Double[] triangle2 = {
                points[1], midpoint(points[0], points[1]),
                midpoint(points[1], points[2])
            };

            sierpinski(triangle2, level -1, t);

            Point2D.Double[] triangle3 = {
                points[2], midpoint(points[2], points[1]),
                midpoint(points[0], points[2])
            };

            sierpinski(triangle3, level -1, t);
        }
    }

    public static void main(String[] args) {
        World habitat = new World(400, 400);
        Turtle t = new Turtle(habitat);

        t.setDelay(0.05);

        Point2D.Double[] points = {
            new Point2D.Double(-180, -150),
            new Point2D.Double(0, 150),
            new Point2D.Double(180, -150)
        };

        sierpinski(points, 5, t);
        t.hide();
    }
}

Listing 4.8.2. Program for Sierpinski Triangle

Note 4.8.3. Java Note.

This program takes advantage of Java’s AWT by using the Point2D.Double class to represent points with an x and y property. It is a subclass of the Point2D class; importing java.awt.geom.Point2D will give you access to it.

Listing 4.8.2 follows the ideas outlined above. The first thing sierpinski does is draw the outer triangle. Next, there are three recursive calls, one for each of the new corner triangles we get when we connect the midpoints.

Look at the code and think about the order in which the triangles will be drawn. While the exact order of the corners depends upon how the initial set is specified, let’s assume that the corners are ordered lower left, top, lower right. Because of the way the sierpinski function calls itself, sierpinski works its way to the smallest allowed triangle in the lower-left corner and then begins to fill out the rest of the triangles working back. Then it fills in the triangles in the top corner by working toward the smallest, topmost triangle. Finally, it fills in the lower-right corner, working its way toward the smallest triangle in the lower right.

Sometimes it is helpful to think of a recursive algorithm in terms of a diagram of method calls. Figure 4.8.4 shows that the recursive calls are always made going to the left. The active functions are outlined in black, and the inactive function calls are in gray. The farther you go toward the bottom of Figure 4.8.4, the smaller the triangles. The function finishes drawing one level at a time; once it is finished with the bottom left it moves to the bottom middle, and so on.

Figure 4.8.4. Call Tree for Sierpinski Triangle

The sierpinski method relies heavily on the midpoint method. midpoint takes as arguments two endpoints and returns the point halfway between them. In addition, Listing 4.8.2 has a drawTriangle method that draws a filled triangle using the beginFill and endFill turtle methods. (beginFill tells the turtle to store all subsequent movements as a path to be filled in the specified color. endFill marks the end of the path, at which point the path is filled with the color.)

You have attempted of activities on this page.

Prev Top Next