Algorithm of the day -

Koch Snowflake Algorithm

Summary

The Koch Snowflake Algorithm iteratively transforms a simple triangle into a detailed, snowflake-like fractal pattern by repeatedly replacing each line segment with a series of smaller segments.

Use Case

A practical use is generating a decorative, fractal-based snowflake shape for a Christmas-themed game or holiday screen saver, providing a visually appealing winter element.

Steps

  1. Start with an equilateral triangle.
  2. For each line segment, divide it into three equal parts.
  3. Replace the middle segment with two segments forming an equilateral bump (creating a 'peak').
  4. Repeat the process for each newly created line segment as many times as desired.

Complexity

Time Complexity: O(4^n), Space Complexity: O(4^n), where n is the number of iterations.

Code Example

import turtle

def koch_segment(t, length, order):
    if order == 0:
        t.forward(length)
    else:
        length /= 3.0
        koch_segment(t, length, order - 1)
        t.left(60)
        koch_segment(t, length, order - 1)
        t.right(120)
        koch_segment(t, length, order - 1)
        t.left(60)
        koch_segment(t, length, order - 1)

# Example usage: draw a Koch Snowflake
screen = turtle.Screen()
screen.bgcolor("#F0F8FF")  # Light blue background for a winter feel

pen = turtle.Turtle()
pen.speed(0)
pen.color("#2F4F4F")  # Dark Slate Gray color for snowflake lines

order = 3  # Increasing this will create a more detailed snowflake
length = 300

# Move to a good starting position
pen.penup()
pen.backward(length/2)
pen.left(60)
pen.backward((length*3**0.5)/6)
pen.right(60)
pen.pendown()

for _ in range(3):
    koch_segment(pen, length, order)
    pen.right(120)

pen.hideturtle()
screen.mainloop()