< Back

Lecture 21 - Fractals

As usual, create a directory to hold today's activities: 

$ mkdir ~/cs170/labs/lab21 
$ cd ~/cs170/labs/lab21

Fractals

Fractals are mathematicals structures that exhibit self-similarity on an astonishing scale. The beauty of the fractal isn't always the incredibly complicated pattern that arises. Many times the real beauty of the fractal is the really elegant and simple recursive definition that generates it.

mainwindow.cpp
Lab Activity 1
Sierpinski Triangles

The Sierpinski triangle (or the Sierpinski Gasket) is a fractal that is probably fairly familiar to you, especially if you happen to be a gamer. The real Sierpinski Triangle has an infinite depth. Our version of a Sierpinski Triangle will have a fixed, finite depth.

Details

Construction of a Sierpinski Triangle is very straight forward:

  1. Draw a triangle.

  2. Draw another triangle by connecting the midpoints of the three sides of your original triangle. This will split your triangle into four smaller triangles: one in the center, and three around the outside.

  3. Repeat step 2 for each of the outside triangles.

You might want to draw a few rounds of this on paper, just to see how it works.

Using Qt Creator, create a project called Sierpinski. This program should draw a sierpinski triangle that fills as much of a Qt window as possible. You will want to define a global constant DEPTH, which is how deep your recursive process should continue. Let's define the depth of a sierpinski triangle as the number of directly nested triangles at the deepest point. So a triangle is a sierpinski triangle of depth 0. When you draw the first internal triangle you have a depth of 1, etc. A DEPTH of 8 or 9 gives a nice looking triangle in a reasonable amount of time.

Try changing the colors of your triangles and the location of the starting verticies, to create a more interesting fractal. When you are happy with your fractal, take a screen shot and save the image in your directory.

Example

Hint

  • The midpoint of a line segment can be calculated using linear interpolation. In order to find a point that is some fraction between two points \((x_1, y_1)\) and \((x_2, y_2)\) the following equation can be used:

    \[ \begin{eqnarray} x_i &=& t \times x_2 + (1 - t) \times x_1\\ y_i &=& t \times y_2 + (1 - t) \times y_1 \end{eqnarray} \]

    Where t is a floating point value between 0 and 1 that represents the fraction of the distance between points 1 and 2 that \((x_i, y_i)\) is located. For the midpoint, you want t = 0.5.

  • On the surface, it might not seem like the order you specify the points matters. However, it really does. You should always specify the points for your triangle in the same order, in the same direction. I suggest clock-wise starting with the northern most point.

 

Challenge

Seeing the triangle generated is one thing. However, seeing all of the steps of the generation is really interesting, to see how each recursive step changes. Add a QSlider widget to your program, which controls the maximum depth that the triangle gets drawn to. You should make sure that the triangle gets updated with every change of the scale.

Lab Activity 2
Koch Snowflake

The Koch snowflake (sometimes called the Koch curve or Koch Star) is one of the earliest known fractals. Similar to the Sierpinski Triangle, it starts off with a triangle shape. However, instead of recursing towards the inside of the triangle, the snowflake grows outwards. The concept of the snowflake is easy, but you will need to spend some time thinking about where your should be performing certain tasks.

Details

Once again, the formal definition recurses infinitely. We will want to create a global constant DEPTH, which is going to represent how deep we generate the snowflake.

The snowflake begins by using 3 line segments to form a triangle (This is a Koch snowflake of order 0). The algorithm for generating higher order fractals involves splitting each line segment into three equal segments, then replacing the middle segment by two line segments that protrude outwards. The same algorithm is then recursively applied to each of the 4 new line segments. See the diagram below:

The actual amount that the point \((x_3, y_3)\) protrudes is up to you, but a value that is about one third of the original segment length produces a nice looking fractal.

You can use trigonometry to figure out the (x3, y3) point, but that begins to become very complex as the line segment sizes get very low. Instead, you can compute this protrusion directly using the following equations:

\[ \begin{eqnarray} x_3 &=& x_1 + \frac{\Delta x}{2} - \Delta y \times p\\ y_3 &=& y_1 + \frac{\Delta y}{2} + \Delta x \times p \end{eqnarray} \]

where

\[ \begin{eqnarray} \Delta x &=& x_5 - x_1\\ \Delta y &=& y_5 - y_1 \end{eqnarray} \]

and p is a value between -1 and 1 that is the percent length of the original segment that the protrusion will be. That is, if p is 0.5 then the protrusion would be half the size of the segment from \((x_1, y_1)\) to \((x_5, y_5)\). If p is -0.5 then it would also be half the size of the segment, but protrude off of the other side of the segment.

Try changing the color of the triangles and the location and number of original line segments. Also play around with the amount of protrusion you are using. When you are happy with your fractal, take a screen shot of it and save it in your directory.

Example

Hint

  • In order to calculate the four line segments that represent the transformation of the segment defined by the points (x1, y1) and (x5, y5) the points that divide the segment into thirds, (x2, y2) and (x4, y4), must be calculated. These can be calculated using interpolation and the equations from earlier.

  • It may seem counter-intuitive, but the only place you want to perform any drawing is your base case. If you draw in a different location, you are going to end up with line segments you need to erase, which is going to make your code quite ugly.

 

Challenge

The typical definition of the koch snowflake uses triangles. However, triangles are a little played out. Instead of using triangles, let's use a different polygon, like a square. For each line segment in the original shape, instead of protruding out to a point, create a square with the protrusion. How different does the curve look afterwards?

Play around with different types of polygons. Do any of them create interesting shapes?