Fractals

A fractal is a geometric figure that often can be generated from a pattern repeated recursively an infinite number of times (Fig. 15.17). The figure is modified by applying the pattern to each segment of the original figure. Real geometric figures do not have their patterns repeated an infinite number of times, but after several repetitions appear as they would if repeated infinitely. We will look at a few such approximations in this section. [Note: We will refer to our geometric figures as fractals, even though they are approximations.] Although these figures had been studied before the 20th century, it was the Polish mathematician Benoit Mandelbrot who introduced the term "fractal" in the 1970s, along with the specifics of how a fractal is created and the practical applications of fractals. Mandelbrot's fractal geometry provides mathematical models for many complex forms found in nature, such as mountains, clouds and coastlines. Fractals have many uses in mathematics and science. Fractals can be used to better understand systems or patterns that appear in nature (e.g., ecosystems), in the human body (e.g., in the folds of the brain), or in the universe (e.g., galaxy clusters). Drawing fractals has become a popular art form. Fractals have a self-similar propertywhen subdivided into parts, each resembles a reduced-size copy of the whole. Many fractals yield an exact copy of the original when a portion of the original image is magnifiedsuch a fractal is said to be strictly self similar. Links are provided in Section 15.12 for various Web sites that discuss and demonstrate fractals.

Figure 15.17. Koch Curve fractal.

As an example, let us look at a popular strictly self-similar fractal known as the Koch Curve (Fig. 15.17). This fractal is formed by removing the middle third of each line in the drawing and replacing it with two lines that form a point, such that if the middle third of the original line remained, an equilateral triangle would be formed. Formulas for creating fractals often involve removing all or part of the previous fractal image. This pattern has already been determined for this fractalin this section we focus not on how to determine what formulas are needed for a specific fractal, but how to use those formulas within a recursive solution. Most formulas can be used to create fractals, but not all fractals will resemble objects in nature.

We start with a straight line (Fig. 15.17, Part a) and apply the pattern, creating a triangle from the middle third (Fig. 15.17, Part b). We then apply the pattern again to each straight line, resulting in Fig. 15.17, Part c. Each time the pattern is applied, we say that the fractal is at a new level, or depth (sometimes the term order is also used). Fractals can be displayed at many levelsfor instance, a fractal at level 3 has had three iterations of the pattern applied (Fig. 15.17, Part d). After only a few iterations, this fractal begins to look the same, like a portion of a snowflake (Fig. 15.17, Parts e and f). The applications of the pattern are now too small for the human eye to see a difference. Since this is a strictly self-similar fractal, each portion of the fractal contains an exact copy of the fractal. In Part f of Fig. 15.17, for example, we have highlighted a portion of the fractal with a dashed red box. If the image in this box were increased in size, it would look exactly like the entire fractal of Part f.

There is a similar fractal, the Koch Snowflake, which is the same as the Koch Curve but begins with a triangle rather than a line. The same pattern is applied to each side of the triangle, resulting in an image that looks like an enclosed snowflake. We have chosen to focus on the Koch Curve for simplicity. We will be moving on shortly to another fractal, but if the reader wishes to learn more about the Koch Curve and Koch Snowflake, see the links in Section 15.12.

We now demonstrate the use of recursion to draw fractals by writing a program to create a strictly self-similar fractal. We call this the "Lo fractal," named for Sin Han Lo, a Deitel & Associates colleague who created it. The fractal will eventually resemble one-half of a feather (see the outputs in Fig. 15.24). The base case, or fractal level of 0, begins as a line between two points, A and B (Fig. 15.18). To create the next higher level, we find the midpoint (C) of the line. To calculate the location of point C, use the following formula: [Note: The x and y to the left of each letter refer to the x-coordinate and y-coordinate of that point, respectively. For instance, xA refers to the x-coordinate of point A, while yC refers to the y-coordinate of point C. In our diagrams we denote the point by its letter, followed by two numbers representing the x- and y-coordinates.]

Figure 15.18'. "Lo fractal" at level 0.

(This item is displayed on page 766 in the print version)

To create this fractal, we also must find a point D that lies left of segment AC and creates an isosceles right triangle ADC. To calculate the location of point D, use the following formulas:

We continue the example in Fig. 15.18 by moving on to the next level (from level 0 to level 1) as follows: First, add points C and D (as in Fig. 15.19). Then, remove the original line and add segments DA, DC and DB. The remaining lines curve at an angle, causing our fractal to look like a feather. For the next level of the fractal, this algorithm is repeated on each of the three lines in level 1. For each line, the formulas above are applied, where the former point D is now considered to be point A, while the other end of each line is considered to be point B. Figure 15.20 contains the line from level 0 (now a dashed line) and the three added lines from level 1. We have changed point D to be point A, and the original points A, C and B to B1, B2 and B3 (the numbers are used to differentiate the various points). The preceding formulas have been used to find the new points C and D on each line. These points are also numbered 13 to keep track of which point is associated with each line. The points C1 and D1, for instance, represent points C and D associated with the line formed from points A to B1. To achieve level 2, the three lines in Fig. 15.20 are removed and replaced with new lines from the C and D points just added. Figure 15.21 shows the new lines (the lines from level 2 are shown as dashed lines for your convenience). Figure 15.22 shows level 2 without the dashed lines from level 1. Once this process has been repeated several times, the fractal created will begin to look like one-half of a feather, as shown in the output of Fig. 15.24. We will discuss the code for this application shortly.

Figure 15.19. Determining points C and D for level 1 of "Lo fractal."

Figure 15.20. "Lo fractal" at level 1, with C and D points determined for level 2. [Note: The fractal at level 0 is included as a dashed line as a reminder of where the line was located in relation to the current fractal.

(This item is displayed on page 767 in the print version)

Figure 15.21. "Lo fractal" at level 2, with dashed lines from level 1 provided.

(This item is displayed on page 767 in the print version)

Figure 15.22. "Lo fractal" at level 2.

(This item is displayed on page 768 in the print version)

Figure 15.23. Demonstrating the fractal user interface.

(This item is displayed on pages 768 - 770 in the print version)

Figure 15.24. Drawing "Lo fractal" using recursion.

(This item is displayed on pages 771 - 773 in the print version)

The application in Fig. 15.23 defines the user interface for drawing this fractal (shown at the end of Fig. 15.24). The interface consists of three buttonsone for the user to change the color of the fractal, one to increase the level of recursion and one to decrease the level of recursion. A JLabel will keep track of the current level of recursion, which is modified by calling method setLevel, to be discussed shortly. Lines 1516 specify constants WIDTH and HEIGHT to be 400 and 480 respectively for the size of the JFrame. The default color to draw the fractal will be blue (line 18). The user triggers an ActionEvent by clicking the Color button. The event handler for this button is registered in lines 3854. The method actionPerformed displays a JColorChooser. This dialog returns the selected Color object or blue (if the user presses Cancel or closes the dialog without pressing OK). Line 51 calls the setColor method in class FractalJPanel to update the color.

The event handler for the Decrease Level button is registered in lines 6078. In method actionPerformed, lines 6667 retrieve the current level of recursion and decrement it by 1. Line 70 checks to make sure that the level is greater than or equal to 0 (MIN_LEVEL). This is because the fractal is not defined for any recursion level lower than 0. The program allows the user to go up to any desired level, but it is important to note that at a certain point (level 10 and higher in this example) the rendering of the fractal becomes increasingly slower, as there is a lot of detail to be drawn. Lines 7274 reset the level label to reflect the changethe new level is set and the repaint method is called to update the image to show the fractal corresponding to the new level.

The Increase Level JButton works the same way as the Decrease Level JButton, except that the level is incremented rather than decremented to show more details of the fractal (lines 9091). When the application is first executed, the level will be set to 0, which will display a blue line between two points that were specified in the FractalJPanel class.

The FractalJPanel class in Fig. 15.24 specifies the dimensions of the drawing JPanel to be 400 by 400 (lines 1314). The FractalJPanel constructor (lines 1824) takes the current level as a parameter and assigns it to its instance variable level. Instance variable color is set to the default color blue. Lines 2223 change the background color of the JPanel to be white (for visibility of the colors used to draw the fractal), and set the new dimensions of the JPanel where the fractal will be drawn.

Lines 2750 define the recursive method that creates the fractal. This method takes six parameters: the level, four integers that specify the x and y coordinates of two points, and the Graphics object g. The base case for this method (line 31) occurs when level equals 0, at which time a line will be drawn between the two points given as parameters. Lines 3643 calculate (xC, yC), the midpoint between (xA, yA) and (xB, yB), and (xD, yD), the point that creates a right isosceles triangle with (xA, yA) and (xC, yC). Lines 4648 make three recursive calls on three different sets of points.

In method paintComponent, line 59 makes the first call to method drawFractal to start the drawing. This method call is not recursive, but all subsequent calls to drawFractal performed from the body of drawFractal are. Since the lines will not be drawn until the base case is reached, the distance between two points decreases on each recursive call. As the level of recursion increases, the fractal becomes smoother and more detailed. The shape of this fractal stabilizes as the level approaches 11. Fractals will stabilize at different levels based on the shape and size of the fractal.

Fig. 15.24 shows the development of the fractal from level zero to six. The last image shows the defining shape of the fractal at level 11. If we focus on one of the arms of this fractal, it would be identical to the whole image. This property defines the fractal to be strictly self-similar. See Section 15.12 for further resources on fractals.