A dive into geometry, recurring algorithms and triangles… lots of them!
Fractals are infinitely complex patterns that are self-similar across different scales. For example, a tree trunk splits into smaller branches. These in turn split into even smaller branches, and so on.
By generating fractals programmatically, we can turn simple shapes into complicated repeating patterns.
In this article I will be exploring how we can build impressive fractals in Python using some basic A-Level geometry and a little programming know-how.
Fractals play an important role in data science. For example, in fractal analysis the fractal characteristics of datasets are evaluated to help understand the structure of underlying processes. In addition, the recurring algorithm at the centre of fractal generation can be applied to a wide range of data problems, from the binary search algorithm to recurrent neural networks.
I want to write a program that can draw an equilateral triangle. On each side of the triangle it must then be able to draw a slightly smaller outward facing triangle. It should be able to repeat this process as many times as I would like, hopefully creating some interesting patterns.
I will be representing an image as a two dimensional array of pixels. Each cell in the pixel array will represent the colour (RGB) of that pixel.
To achieve this, we can use the libraries NumPy to generate the pixel array and Pillow to turn it into an image that we can save.
Now it’s time to get coding!
Firstly, I need a function that can take two sets of coordinates and draw a line between them.
The code below works by interpolating between two points, adding new pixels to the pixel array with each step. You can think of this process like colouring in a line pixel by pixel.
I have used the continuation character ‘\’ in each code snippet to help fit some longer lines of code in.
import numpy as np
from PIL import Image
import mathdef plot_line(from_coordinates, to_coordinates, thickness, colour, pixels):
# Figure out the boundaries of our pixel array
max_x_coordinate = len(pixels[0])
max_y_coordinate = len(pixels)
# The distances along the x and y axis between the 2 points
horizontal_distance = to_coordinates[1] - from_coordinates[1]
vertical_distance = to_coordinates[0] - from_coordinates[0]
# The total distance between the two points
distance = math.sqrt((to_coordinates[1] - from_coordinates[1])**2 \
+ (to_coordinates[0] - from_coordinates[0])**2)
# How far we will step forwards each time we colour in a new pixel
horizontal_step = horizontal_distance/distance
vertical_step = vertical_distance/distance
# At this point, we enter the loop to draw the line in our pixel array
# Each iteration of the loop will add a new point along our line
for i in range(round(distance)):
# These 2 coordinates are the ones at the center of our line
current_x_coordinate = round(from_coordinates[1] + (horizontal_step*i))
current_y_coordinate = round(from_coordinates[0] + (vertical_step*i))
# Once we have the coordinates of our point,
# we draw around the coordinates of size 'thickness'
for x in range (-thickness, thickness):
for y in range (-thickness, thickness):
x_value = current_x_coordinate + x
y_value = current_y_coordinate + y
if (x_value > 0 and x_value < max_x_coordinate and \
y_value > 0 and y_value < max_y_coordinate):
pixels[y_value][x_value] = colour
# Define the size of our image
pixels = np.zeros( (500,500,3), dtype=np.uint8 )
# Draw a line
plot_line([0,0], [499,499], 1, [255,200,0], pixels)
# Turn our pixel array into a real picture
img = Image.fromarray(pixels)
# Show our picture, and save it
img.show()
img.save('Line.png')
Now I have a function which can draw a line between two points, it’s time to draw the first equilateral triangle.
Given the centre point and side length of a triangle, we can work out the height using the handy formula: h = ½(√3a).
Now using that height, centre point and side length, I can figure out where each corner of the triangle should be. Using the plot_line function I made earlier, I can draw a line between each corner.
def draw_triangle(center, side_length, thickness, colour, pixels):# The height of an equilateral triangle is, h = ½(√3a)
# where 'a' is the side length
triangle_height = round(side_length * math.sqrt(3)/2)
# The top corner
top = [center[0] - triangle_height/2, center[1]]
# Bottom left corner
bottom_left = [center[0] + triangle_height/2, center[1] - side_length/2]
# Bottom right corner
bottom_right = [center[0] + triangle_height/2, center[1] + side_length/2]
# Draw a line between each corner to complete the triangle
plot_line(top, bottom_left, thickness, colour, pixels)
plot_line(top, bottom_right, thickness, colour, pixels)
plot_line(bottom_left, bottom_right, thickness, colour, pixels)
The stage is set. Almost everything I need is ready to create my first fractal in Python. How exciting!
However, this final step is arguably the trickiest. I want our triangle function to call itself for each side it has. For this to work, I need to be able to calculate the centre point of each of the new smaller triangles, and to rotate them correctly so they are pointing perpendicular to the side they are attached to.
By subtracting the offset of our centre point from the coordinates I wish to rotate, and then applying the formula to rotate a pair of coordinates, we can use this function to rotate each corner of the triangle.
def rotate(coordinate, center_point, degrees):
# Subtract the point we are rotating around from our coordinate
x = (coordinate[0] - center_point[0])
y = (coordinate[1] - center_point[1])# Python's cos and sin functions take radians instead of degrees
radians = math.radians(degrees)
# Calculate our rotated points
new_x = (x * math.cos(radians)) - (y * math.sin(radians))
new_y = (y * math.cos(radians)) + (x * math.sin(radians))
# Add back our offset we subtracted at the beginning to our rotated points
return [new_x + center_point[0], new_y + center_point[1]]
Now I can rotate a triangle, I must switch my focus to drawing a new smaller triangle on each side of the first triangle.
To achieve this, I extended the draw_triangle function to calculate, for each edge, the rotation and centre point of a new triangle with a side length reduced by the parameter shrink_side_by.
Once it has calculated the centre point and rotation of the new triangle it calls draw_triangle (itself) to draw the new, smaller triangle out from the centre of the current line. This will then in turn hit the same block of code that calculates another set of centre points and rotations for an even smaller triangle.
This is called a recurring algorithm, as our draw_triangle function will now call itself until it reaches the max_depth of triangles we wish to draw. It’s important to have this escape clause, because otherwise the function would theoretically continue recurring forever (but in practice the call stack will get too large, resulting in a stack overflow error)!
def draw_triangle(center, side_length, degrees_rotate, thickness, colour, \
pixels, shrink_side_by, iteration, max_depth):# The height of an equilateral triangle is, h = ½(√3a)
# where 'a' is the side length
triangle_height = side_length * math.sqrt(3)/2
# The top corner
top = [center[0] - triangle_height/2, center[1]]
# Bottom left corner
bottom_left = [center[0] + triangle_height/2, center[1] - side_length/2]
# Bottom right corner
bottom_right = [center[0] + triangle_height/2, center[1] + side_length/2]
if (degrees_rotate != 0):
top = rotate(top, center, degrees_rotate)
bottom_left = rotate(bottom_left, center, degrees_rotate)
bottom_right = rotate(bottom_right, center, degrees_rotate)
# Coordinates between each edge of the triangle
lines = [[top, bottom_left],[top, bottom_right],[bottom_left, bottom_right]]
line_number = 0
# Draw a line between each corner to complete the triangle
for line in lines:
line_number += 1
plot_line(line[0], line[1], thickness, colour, pixels)
# If we haven't reached max_depth, draw some new triangles
if (iteration < max_depth and (iteration < 1 or line_number < 3)):
gradient = (line[1][0] - line[0][0]) / (line[1][1] - line[0][1])
new_side_length = side_length*shrink_side_by
# Center of the line of the traingle we are drawing
center_of_line = [(line[0][0] + line[1][0]) / 2, \
(line[0][1] + line[1][1]) / 2]
new_center = []
new_rotation = degrees_rotate
# Amount we need to rotate the traingle by
if (line_number == 1):
new_rotation += 60
elif (line_number == 2):
new_rotation -= 60
else:
new_rotation += 180
# In an ideal world this would be gradient == 0,
# but due to floating point division we cannot
# ensure that this will always be the case
if (gradient < 0.0001 and gradient > -0.0001):
if (center_of_line[0] - center[0] > 0):
new_center = [center_of_line[0] + triangle_height * \
(shrink_side_by/2), center_of_line[1]]
else:
new_center = [center_of_line[0] - triangle_height * \
(shrink_side_by/2), center_of_line[1]]
else:
# Calculate the normal to the gradient of the line
difference_from_center = -1/gradient
# Calculate the distance from the center of the line
# to the center of our new traingle
distance_from_center = triangle_height * (shrink_side_by/2)
# Calculate the length in the x direction,
# from the center of our line to the center of our new triangle
x_length = math.sqrt((distance_from_center**2)/ \
(1 + difference_from_center**2))
# Figure out which way around the x direction needs to go
if (center_of_line[1] < center[1] and x_length > 0):
x_length *= -1
# Now calculate the length in the y direction
y_length = x_length * difference_from_center
# Offset the center of the line with our new x and y values
new_center = [center_of_line[0] + y_length, \
center_of_line[1] + x_length]
draw_triangle(new_center, new_side_length, new_rotation, \
thickness, colour, pixels, shrink_side_by, \
iteration+1, max_depth)
Below are some examples of different images we can generate by modifying the shrink_side_by and max_depth values input to our draw_triangle function.
It’s interesting how these large repeating patterns often create more complex shapes, such as hexagons, but with a mesmerising symmetry.
All images unless otherwise noted are by the author.
Fractals are great fun to play around with and can create beautiful patterns. Using a few simple concepts and a splash of creativity, we can generate very impressive structures.
In understanding the core properties of our fractals, and applying the recurring algorithm, we’ve created a solid foundation which can help us understand more complex fractal problems in data science.
Feel free to read and download the full code here. Let me know if you find ways to improve or extend it!
I wonder what you could create with a different shape?
A dive into geometry, recurring algorithms and triangles… lots of them!
Fractals are infinitely complex patterns that are self-similar across different scales. For example, a tree trunk splits into smaller branches. These in turn split into even smaller branches, and so on.
By generating fractals programmatically, we can turn simple shapes into complicated repeating patterns.
In this article I will be exploring how we can build impressive fractals in Python using some basic A-Level geometry and a little programming know-how.
Fractals play an important role in data science. For example, in fractal analysis the fractal characteristics of datasets are evaluated to help understand the structure of underlying processes. In addition, the recurring algorithm at the centre of fractal generation can be applied to a wide range of data problems, from the binary search algorithm to recurrent neural networks.
I want to write a program that can draw an equilateral triangle. On each side of the triangle it must then be able to draw a slightly smaller outward facing triangle. It should be able to repeat this process as many times as I would like, hopefully creating some interesting patterns.
I will be representing an image as a two dimensional array of pixels. Each cell in the pixel array will represent the colour (RGB) of that pixel.
To achieve this, we can use the libraries NumPy to generate the pixel array and Pillow to turn it into an image that we can save.
Now it’s time to get coding!
Firstly, I need a function that can take two sets of coordinates and draw a line between them.
The code below works by interpolating between two points, adding new pixels to the pixel array with each step. You can think of this process like colouring in a line pixel by pixel.
I have used the continuation character ‘\’ in each code snippet to help fit some longer lines of code in.
import numpy as np
from PIL import Image
import mathdef plot_line(from_coordinates, to_coordinates, thickness, colour, pixels):
# Figure out the boundaries of our pixel array
max_x_coordinate = len(pixels[0])
max_y_coordinate = len(pixels)
# The distances along the x and y axis between the 2 points
horizontal_distance = to_coordinates[1] - from_coordinates[1]
vertical_distance = to_coordinates[0] - from_coordinates[0]
# The total distance between the two points
distance = math.sqrt((to_coordinates[1] - from_coordinates[1])**2 \
+ (to_coordinates[0] - from_coordinates[0])**2)
# How far we will step forwards each time we colour in a new pixel
horizontal_step = horizontal_distance/distance
vertical_step = vertical_distance/distance
# At this point, we enter the loop to draw the line in our pixel array
# Each iteration of the loop will add a new point along our line
for i in range(round(distance)):
# These 2 coordinates are the ones at the center of our line
current_x_coordinate = round(from_coordinates[1] + (horizontal_step*i))
current_y_coordinate = round(from_coordinates[0] + (vertical_step*i))
# Once we have the coordinates of our point,
# we draw around the coordinates of size 'thickness'
for x in range (-thickness, thickness):
for y in range (-thickness, thickness):
x_value = current_x_coordinate + x
y_value = current_y_coordinate + y
if (x_value > 0 and x_value < max_x_coordinate and \
y_value > 0 and y_value < max_y_coordinate):
pixels[y_value][x_value] = colour
# Define the size of our image
pixels = np.zeros( (500,500,3), dtype=np.uint8 )
# Draw a line
plot_line([0,0], [499,499], 1, [255,200,0], pixels)
# Turn our pixel array into a real picture
img = Image.fromarray(pixels)
# Show our picture, and save it
img.show()
img.save('Line.png')
Now I have a function which can draw a line between two points, it’s time to draw the first equilateral triangle.
Given the centre point and side length of a triangle, we can work out the height using the handy formula: h = ½(√3a).
Now using that height, centre point and side length, I can figure out where each corner of the triangle should be. Using the plot_line function I made earlier, I can draw a line between each corner.
def draw_triangle(center, side_length, thickness, colour, pixels):# The height of an equilateral triangle is, h = ½(√3a)
# where 'a' is the side length
triangle_height = round(side_length * math.sqrt(3)/2)
# The top corner
top = [center[0] - triangle_height/2, center[1]]
# Bottom left corner
bottom_left = [center[0] + triangle_height/2, center[1] - side_length/2]
# Bottom right corner
bottom_right = [center[0] + triangle_height/2, center[1] + side_length/2]
# Draw a line between each corner to complete the triangle
plot_line(top, bottom_left, thickness, colour, pixels)
plot_line(top, bottom_right, thickness, colour, pixels)
plot_line(bottom_left, bottom_right, thickness, colour, pixels)
The stage is set. Almost everything I need is ready to create my first fractal in Python. How exciting!
However, this final step is arguably the trickiest. I want our triangle function to call itself for each side it has. For this to work, I need to be able to calculate the centre point of each of the new smaller triangles, and to rotate them correctly so they are pointing perpendicular to the side they are attached to.
By subtracting the offset of our centre point from the coordinates I wish to rotate, and then applying the formula to rotate a pair of coordinates, we can use this function to rotate each corner of the triangle.
def rotate(coordinate, center_point, degrees):
# Subtract the point we are rotating around from our coordinate
x = (coordinate[0] - center_point[0])
y = (coordinate[1] - center_point[1])# Python's cos and sin functions take radians instead of degrees
radians = math.radians(degrees)
# Calculate our rotated points
new_x = (x * math.cos(radians)) - (y * math.sin(radians))
new_y = (y * math.cos(radians)) + (x * math.sin(radians))
# Add back our offset we subtracted at the beginning to our rotated points
return [new_x + center_point[0], new_y + center_point[1]]
Now I can rotate a triangle, I must switch my focus to drawing a new smaller triangle on each side of the first triangle.
To achieve this, I extended the draw_triangle function to calculate, for each edge, the rotation and centre point of a new triangle with a side length reduced by the parameter shrink_side_by.
Once it has calculated the centre point and rotation of the new triangle it calls draw_triangle (itself) to draw the new, smaller triangle out from the centre of the current line. This will then in turn hit the same block of code that calculates another set of centre points and rotations for an even smaller triangle.
This is called a recurring algorithm, as our draw_triangle function will now call itself until it reaches the max_depth of triangles we wish to draw. It’s important to have this escape clause, because otherwise the function would theoretically continue recurring forever (but in practice the call stack will get too large, resulting in a stack overflow error)!
def draw_triangle(center, side_length, degrees_rotate, thickness, colour, \
pixels, shrink_side_by, iteration, max_depth):# The height of an equilateral triangle is, h = ½(√3a)
# where 'a' is the side length
triangle_height = side_length * math.sqrt(3)/2
# The top corner
top = [center[0] - triangle_height/2, center[1]]
# Bottom left corner
bottom_left = [center[0] + triangle_height/2, center[1] - side_length/2]
# Bottom right corner
bottom_right = [center[0] + triangle_height/2, center[1] + side_length/2]
if (degrees_rotate != 0):
top = rotate(top, center, degrees_rotate)
bottom_left = rotate(bottom_left, center, degrees_rotate)
bottom_right = rotate(bottom_right, center, degrees_rotate)
# Coordinates between each edge of the triangle
lines = [[top, bottom_left],[top, bottom_right],[bottom_left, bottom_right]]
line_number = 0
# Draw a line between each corner to complete the triangle
for line in lines:
line_number += 1
plot_line(line[0], line[1], thickness, colour, pixels)
# If we haven't reached max_depth, draw some new triangles
if (iteration < max_depth and (iteration < 1 or line_number < 3)):
gradient = (line[1][0] - line[0][0]) / (line[1][1] - line[0][1])
new_side_length = side_length*shrink_side_by
# Center of the line of the traingle we are drawing
center_of_line = [(line[0][0] + line[1][0]) / 2, \
(line[0][1] + line[1][1]) / 2]
new_center = []
new_rotation = degrees_rotate
# Amount we need to rotate the traingle by
if (line_number == 1):
new_rotation += 60
elif (line_number == 2):
new_rotation -= 60
else:
new_rotation += 180
# In an ideal world this would be gradient == 0,
# but due to floating point division we cannot
# ensure that this will always be the case
if (gradient < 0.0001 and gradient > -0.0001):
if (center_of_line[0] - center[0] > 0):
new_center = [center_of_line[0] + triangle_height * \
(shrink_side_by/2), center_of_line[1]]
else:
new_center = [center_of_line[0] - triangle_height * \
(shrink_side_by/2), center_of_line[1]]
else:
# Calculate the normal to the gradient of the line
difference_from_center = -1/gradient
# Calculate the distance from the center of the line
# to the center of our new traingle
distance_from_center = triangle_height * (shrink_side_by/2)
# Calculate the length in the x direction,
# from the center of our line to the center of our new triangle
x_length = math.sqrt((distance_from_center**2)/ \
(1 + difference_from_center**2))
# Figure out which way around the x direction needs to go
if (center_of_line[1] < center[1] and x_length > 0):
x_length *= -1
# Now calculate the length in the y direction
y_length = x_length * difference_from_center
# Offset the center of the line with our new x and y values
new_center = [center_of_line[0] + y_length, \
center_of_line[1] + x_length]
draw_triangle(new_center, new_side_length, new_rotation, \
thickness, colour, pixels, shrink_side_by, \
iteration+1, max_depth)
Below are some examples of different images we can generate by modifying the shrink_side_by and max_depth values input to our draw_triangle function.
It’s interesting how these large repeating patterns often create more complex shapes, such as hexagons, but with a mesmerising symmetry.
All images unless otherwise noted are by the author.
Fractals are great fun to play around with and can create beautiful patterns. Using a few simple concepts and a splash of creativity, we can generate very impressive structures.
In understanding the core properties of our fractals, and applying the recurring algorithm, we’ve created a solid foundation which can help us understand more complex fractal problems in data science.
Feel free to read and download the full code here. Let me know if you find ways to improve or extend it!
I wonder what you could create with a different shape?