Case Study: Fractals

Using recursion is ideal for displaying fractals, because fractals are inherently recursive. A fractal is a geometrical figure, but unlike triangles, circles, and rectangles, fractals can be divided into parts, each of which is a reduced-size copy of the whole. There are many interesting examples of fractals. This section introduces a simple fractal, the Sierpinski triangle, named after a famous Polish mathematician.

A Sierpinski triangle is created as follows:

1. Begin with an equilateral triangle, which is considered to be a Sierpinski fractal of order (or level) 0, as shown in Figure below (a).
2. Connect the midpoints of the sides of the triangle of order 0 to create a Sierpinski triangle of order 1 (Figure below (b)).
3. Leave the center triangle intact. Connect the midpoints of the sides of the three other triangles to create a Sierpinski triangle of order 2 (Figure below (c)).
4. You can repeat the same process recursively to create a Sierpinski triangle of order 3, 4, . . . , and so on (Figure below (d)).

The problem is inherently recursive. How do you develop a recursive solution for it? Consider the base case when the order is 0. It is easy to draw a Sierpinski triangle of order 0. How do you draw a Sierpinski triangle of order 1? The problem can be reduced to drawing three Sierpinski triangles of order 0. How do you draw a Sierpinski triangle of order 2? The problem can be reduced to drawing three Sierpinski triangles of order 1, so the problem of drawing a Sierpinski triangle of order n can be reduced to drawing three Sierpinski triangles of order n - 1.

The code below gives a program that displays a Sierpinski triangle of any order, as shown in Figure above. You can enter an order in a text field to display a Sierpinski triangle of the specified order.

package application;
import javafx.application.Application;
import javafx.geometry.Point2D;
import javafx.geometry.Pos;
import javafx.scene.Scene;
import javafx.scene.control.Label;
import javafx.scene.control.TextField;
import javafx.scene.layout.BorderPane;
import javafx.scene.layout.HBox;
import javafx.scene.layout.Pane;
import javafx.scene.paint.Color;
import javafx.scene.shape.Polygon;
import javafx.stage.Stage;

public class SierpinskiTriangle extends Application {
    @Override // Override the start method in the Application class
    public void start(Stage primaryStage) {
        SierpinskiTrianglePane trianglePane = new SierpinskiTrianglePane();
        TextField tfOrder = new TextField();
        tfOrder.setOnAction(e -> trianglePane.setOrder(Integer.parseInt(tfOrder.getText())));
        tfOrder.setPrefColumnCount(4);
        tfOrder.setAlignment(Pos.BOTTOM_RIGHT);

        // Pane to hold label, text field, and a button
        HBox hBox = new HBox(10);
        hBox.getChildren().addAll(new Label("Enter an order: "), tfOrder);
        hBox.setAlignment(Pos.CENTER);

        BorderPane borderPane = new BorderPane();
        borderPane.setCenter(trianglePane);
        borderPane.setBottom(hBox);

        // Create a scene and place it in the stage
        Scene scene = new Scene(borderPane, 200, 210);
        primaryStage.setTitle("SierpinskiTriangle"); // Set the stage title
        primaryStage.setScene(scene); // Place the scene in the stage
        primaryStage.show(); // Display the stage

        scene.widthProperty().addListener(ov -> trianglePane.paint());
        scene.heightProperty().addListener(ov -> trianglePane.paint());
    }

    public static void main(String[] args) {
        Application.launch(args);
    }

    /** Pane for displaying triangles */
    static class SierpinskiTrianglePane extends Pane {
        private int order = 0;

        /** Set a new order */
        public void setOrder(int order) {
            this.order = order;
            paint();
        }

        SierpinskiTrianglePane() {
        }

        protected void paint() {
            // Select three points in proportion to the pane size
            Point2D p1 = new Point2D(getWidth() / 2, 10);
            Point2D p2 = new Point2D(10, getHeight() - 10);
            Point2D p3 = new Point2D(getWidth() - 10, getHeight() - 10);
            this.getChildren().clear(); // Clear the pane before redisplay

            displayTriangles(order, p1, p2, p3);
        }

         private void displayTriangles(int order, Point2D p1,
         Point2D p2, Point2D p3) {
             if (order == 0) {
                 // Draw a triangle to connect three points
                 Polygon triangle = new Polygon();
                 triangle.getPoints().addAll(p1.getX(), p1.getY(), p2.getX(), p2.getY(), p3.getX(), p3.getY());
                 triangle.setStroke(Color.BLACK);
                 triangle.setFill(Color.WHITE);

                 this.getChildren().add(triangle);
             }
             else {
                 // Get the midpoint on each edge in the triangle
                 Point2D p12 = p1.midpoint(p2);
                 Point2D p23 = p2.midpoint(p3);
                 Point2D p31 = p3.midpoint(p1);

                 // Recursively display three triangles
                 displayTriangles(order - 1, p1, p12, p31);
                 displayTriangles(order - 1, p12, p2, p23);
                 displayTriangles(order - 1, p31, p23, p3);
             }
        }
    }
}

The initial triangle has three points set in proportion to the pane size (lines 62–64). If order == 0, the displayTriangles(order, p1, p2, p3) method displays a triangle that connects the three points p1, p2, and p3 in lines 74–79, as shown in Figure below (a). Otherwise, it performs the following tasks:

1. Obtain the midpoint between p1 and p2 (line 83), the midpoint between p2 and p3 (line 84), and the midpoint between p3 and p1 (line 85), as shown in Figure below (b).
2. Recursively invoke displayTriangles with a reduced order to display three smaller Sierpinski triangles (lines 88–90). Note that each small Sierpinski triangle is structurally identical to the original big Sierpinski triangle except that the order of a small triangle is one less, as shown in Figure below (b).

A Sierpinski triangle is displayed in a SierpinskiTrianglePane. The order property in the inner class SierpinskiTrianglePane specifies the order for the Sierpinski triangle. The Point2D Class, represents a point with x- and y-coordinates. Invoking p1.midpoint(p2) returns a new Point2D object that is the midpoint between p1 and p2 (lines 83–85).