Lecture 4/24: Fractals


April 24, 2020

📂Associated files

Fractals

CS 106B: Programming Abstractions

Spring 2020, Stanford University Computer Science Department

Lecturers: Chris Gregg and Julie Zelenski

An impressive fractal, demonstrating how a very few basic parts to an image can be beautiful


Slide 2

Announcements


Slide 3

Observations about recursion


Slide 4

Another recursion example

An image showing how Google will perform math for you. Inside the search bar is '((1+3)*(2*(4+1)))

An image showing how the Google calculator solution to '((1+3)*(2*(4+1))), which is 95


Slide 5

The Challenge


Slide 6

Anatomy of a mathematical expression


Slide 7

Anatomy of a mathematical expression

An image showing a 'tree' representing the solution to the above evaluation. First, we break each expression up into its component parts, and when we get to an expression with just numbers, we calculate those results. We have the '+' separating the two main expressions, (1*17) and (2*(3+(4*9))). Etc. This text is repeated below.


Slide 8

Is it recursive? Yes!


Slide 9

Solution in Pseudocode

"((1*3)+(2*4))"

int evaluate(expression):


Slide 10

The solution

int evaluate(string exp) {
    // base case
    if (stringIsInteger(exp)) {
        return stringToInteger(exp);
    } else {
        char op = getOperator(exp);
        string left = getLeftExp(exp);
        string right = getRightExp(exp);

        // recursive case #1
        int leftResult = evaluate(left);

        // recursive case #2 (!)
        int rightResult = evaluate(right);

        if (op == '+') {
            return leftResult + rightResult;
        } else {
            return leftResult * rightResult;
        }
    }
}

Slide 11

Helper function

int getOppIndex(string exp){
    int parens = 0; 
    // ignore first left paren
    for (int i = 1; i < exp.length(); i++) {
        char c = exp[i];
        if (c == '(') {
            parens++;
        } else if (c == ')') {
            parens--;
        }
        if (parens == 0 && (c == '+' || c == '*')) {
            return i;
        }
    }
    return -1;
}

Slide 12

Fractals

A fractal is a recurring graphical pattern. Smaller instances of the same shape or pattern occur within the pattern itself.

An image showing many fractals. The patterns are incredible -- they repeate again and again in each image, getting (in general) smaller each time. One image is of a programatically-generated tree with the main trunk branching off to smaller copies of itself, each with its own smaller copies, as well. Another example is the Sierpinski triangle, with three triangles encompassed inside a larger triangle. Each smaller triangle is itself made of three smaller triangles, and this keeps going to infinity.


Slide 13

Fractal Examples in Nature

Images of a broccoli-like plant, a fern, a snow-covered mountain, and a coastline -- all examples of natural fractals


Slide 14

The Cantor Fractal

An image of an Egyptian architectural column, with a Cantor fractor built into the column

An image of a tattoo of the Cantor fractal on someone's arm


Slide 15

The Cantor Fractal

An image of the cantor fractal using just line segments

In text, a 4-level Cantor fractal would look like this:

---------------------------
---------         ---------
---   ---         ---   ---
- -   - -         - -   - -

Slide 16

The Cantor Fractal

An image of a six-level cantor fractal using just line segments, showing that the left third of the diagram under the original line is a Cantor set, and so is the right third of the diagram under the original line


Slide 17

How to draw a level 1 Cantor fractal

A single line, going across the whole screen


Slide 18

How to draw a level n Cantor fractal

A single line, going across the whole screen. Underneath, on the left, is a space where it says 'draw a cantor of size n-1', and on the right, it says 'draw a cantor of size n-1'

  1. Draw a line from start to finish.
  2. Underneath, on the left third, draw a Cantor of size n - 1.
  3. Underneath, on the right third, draw a Cantor of size n - 1.

Slide 19

Graphics in C++ with the Stanford library: GPoint

An image showing an x/y axis with the origin in the top left. There is a single point labeled 'GPoint a', and some code that says, GWindow w; GPoint a(100, 100); cout << a.getX() << endl;


An image showing an x/y axis with the origin in the top left. There are now two points labeled 'GPoint a' and 'GPoint b', and some code that says, GWindow w; GPoint a(100, 100); GPoint b(20, 20); w.drawLione(a, b);


Slide 20

Let's code!

The Cantor fractal and the Qt Logo


Slide 21

Snowflake Fractal

A 'snowflake' fractal which is made up of lines and triangles. It has the apperance of a snowflake with six 'sides' of the snowflake, with each side made up of an infinite number of smaller line/triangle segments. See below on how we are going to draw it


Slide 22

Let's break this down to a smaller part

A part of the 'snowflake' fractal that has been sliced such that only a horizontal section remains


Slide 23

Depth 1 Snowflake: A line

To start drawing a snowflake, you draw a line all the way across the screen


Slide 24

Depth 2 Snowflake: The line has a triangle break

To draw a depth 2 snowflake, you split the line from level 1 at the 1/3 and 2/3 marks, and draw a triangle between those two points that is at the middle and above the line.


Slide 25

Depth 3 Snowflake: In progress

A level 3 snowflake starts by taking the original 1/3 of the level 1 snowflake and splitting that into thirds, with the 1/3 and 2/3 points of that smaller line creating a vertical triangle as with a level 2 snowflake


Slide 26

Depth 3 Snowflake: In progress

To continue a level 3 snowflake, you break the left part of the level 2 triangle into thirds, and the points at 1/3 and 2/3 of that smaller line are drawn out and to the right (at an angle such that the point in the middle creates an equilateral triangle with the slanted edge.


Slide 27

Depth 3 Snowflake: Finished

A finished level three snowflake has another two side triangles drawn as in the previous two drawings. There are a total of four new triangle 'bumps' on the level 2 snowflake.


Slide 28

Let's Code a Snowflake!

A partial snowflake and the Qt logo