Fractals

CS 106B: Programming Abstractions

Spring 2021, Stanford University Computer Science Department

Lecturer: Chris Gregg, Head CA: Chase Davis

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

Slide 2

Announcements

  • Assignment 2 is due end-of-day today (Friday); the grace period for submission extends through end-of-day Sunday.
  • Assignment 3 will be released tomorrow.
    • After much discussion among the course staff and section leaders, we will allow pair programming on assignment 4, and potentially future assignments.
    • We will have details about pair programming, but it will require students to work absolutely together for all parts of the assignment. You will still have individual IGs, as well.

Slide 3

Observations about recursion

  • The base case represents the simplest possible instance of the problem you are solving.
    • Example: How many people are behind you, including you? Answer? 1, it's just me!
    • Example: What is x^n? Answer: x^0 = 1
    • Solve the Towers of Hanoi Answer: 1 ring is easy!
  • The recursive case represents how you can break down the problem into smaller instances of the same problem.
    • Example: How many people are behind you, including you? Answer? 1 + the number behind me
    • Example: What is x^n? Answer: x * x^(n-1)
    • Solve the Towers of Hanoi Answer: N-1 disks to aux, 1 disk to target, N-1 disks to target

Slide 4

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 5

Fractal Examples in Nature

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

  • Many natural phenomena generate fractal patterns:
    • earthquake fault lines
    • animal color patterns
    • clouds
    • mountain ranges
    • snowflakes
    • crystals
    • coastlines
    • DNA

Slide 6

The Cantor Fractal

  • We can create many fractals programmatically, and because fractals are self-similar, we can do so recursively!
  • The first fractal we will code is called the "Cantor" fractal, named after the late-19th century German mathematician Georg Cantor.

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

  • The Cantor fractal is a set of lines (indeed, a "Cantor Set" of lines) where there is one main line, and below that there are two other lines, each 1/3rd of the width of the original line, one on theleft, and one on the right (with a 1/3 separation of white space between them)
  • Below each of the other lines is an identical situation: two 1/3rd lines.
  • This repeats until the lines are no longer visible.

Slide 7

The Cantor Fractal

An image of the cantor fractal using just line segments

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

---------------------------
---------         ---------
---   ---         ---   ---
- -   - -         - -   - -
  • Parts of a cantor set image … are Cantor set images!

Slide 8

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

  • The Cantor fractal above has six levels.
  • Every individual line segment is its own 1-level Cantor fractal

Slide 9

How to draw a level 1 Cantor fractal

A single line, going across the whole screen

Slide 10

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 11

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 12

Let's code!

The Cantor fractal and the Qt Logo

Slide 13

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 14

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 15

Depth 1 Snowflake: A line

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

Slide 16

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 17

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 18

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 19

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 20

Let's Code a Snowflake!

A partial snowflake and the Qt logo