Hello, Habr! Today's post on fractals has come across as part of a Python theme , in particular, Matplotlib. Follow the author’s example and warn that in the post there is a lot of heavy animation that may not even work on a mobile device. But how beautiful.
All enjoy readingFractals are beautiful. They line up in accordance with a very complex pattern and are preserved without distortion at any magnification! In this article, we will look at how you can easily draw fractals of several kinds, using a tool called L-Systems and the Turtle module for Python to perform step-by-step drawing.In this article, we will not excessively go into technical details; instead, I restrict myself to a brief introduction, show a lot of animated examples and code with which you can generate such an example. If you want to skip the theory and just watch the animation, go straight to the examples. In addition, at the end I will point out several resources, both in code writing and in basic mathematics, that you might want to explore.What is a fractal?To get started, let's give a “loose” definition of a fractal. In principle, a fractal is a geometric figure that demonstrates the same properties regardless of the degree of increase.This definition is not perfect, so here is a more accurate one from the Math World website:A fractal is an object or quantity that demonstrates self-similarity (in the formal sense) at any scale. An object exhibits not identical structures at different scales, but structures of the same “type” must appear at all levels of the fractal. In this case, the graph is plotted in a coordinate system with a logarithmic scale, where the magnitude and scale are counted along the axes, the graph is a straight line with a slope reflecting the dimension of the fractal. - Math World
How to draw fractals using Python?Typically, rendering fractals is complex, as the deep nature of fractals is determined by the concept of recursion. Speaking about graphs and their drawing, we usually think that they are formed by pixels or vectors, but the number of pixels or vectors is always limited, and fractals are infinitely recursive by definition. Thus, trying to apply a fractal to the coordinate grid, we will have to stop at some point, and that is why we are talking about “iterations” in this case. At each iteration, the fractal becomes more complicated, and at some point it becomes impossible to distinguish two of its iterations following each other (such a moment occurs when changes occur at a level comparable to the size of the pixel). It is logical to stop here, but, as a rule, the shape of the fractal looms faster, and you can stop even earlier.Two such examples are the square island of Koch, whose structure clearly emerges after three iterations, and the Carter-Heitway dragon, for which 8 iterations are enough to build the complete structure. The required number of iterations is highly dependent on the specific fractal we are working with.Of course, there are many Python libraries for plotting, among which the most popular is Matplotlib, but they are usually designed for drawing statistics and drawing well-known graphs. In particular, Matplotlib contains some low-level constructions that can be used to construct fractals, but this time we will focus on the undeservedly little-known module of the standard library called Turtle.Turtle modulein Python documentationwe read: “Turtle graphics is a popular tool for the first acquaintance of children with programming. He was part of the original Logo programming language, developed by Wally Förzeg and Seymour Papert in 1966. ”The bottom line is that the turtle recognizes 3 commands by default:- Crawl forward
- Rotate Left Angle
- Rotate Right Angle
Note: other commands are provided in the standard library, but here we will use only these three.Also we can:- Mute record
- Enable recording
These characteristics seem too simple to draw on such a complex graph as a fractal, relying only on them, but we will use another tool that uses only this small set of instructions. I am talking about L-systems.L-systems AnL-system is a way of representing recursive structures (for example, fractals) as a string of characters and rewriting such a string multiple times. Again, we give a formal definition:The Lindenmeyer system, also known as the L-system, is a line rewrite mechanism that can be used to generate fractals with dimensions from 1 to 2 - Math World
Having understood what an L-system is, we can create recursive structures, but first, let's figure out what components we need for this. Each L-system has:Note for Computer Science fans: If you have studied Computer Science in depth, then all of the above may remind you of something. Indeed, formal grammars are defined very similarly; the key difference is that, unlike grammars, here at each iteration as many rules apply as possible, and not just one. Therefore, L-systems are a subset of context-free grammars.Given that we are going to use Turtle to build graphs and the L-system to represent what we are going to plot, we need to create a relationship between them.Since in Turtle we have only the teams listed above, we assign each of them a symbol; the alphabet will consist of these characters.- F: crawl forward
- +: turn right
- -: turn left
For this to work, an angle must be provided for each fractal; this will be the angle at which the turtle will turn to the right or left. For simplicity, we agree that only one corner should be provided, and we will write the L-system, keeping this in mind.The axiom and instructions for creating strings will depend only on the fractal, but the fractal must be written so that it can be represented only by these three characters. So there is a restriction, by virtue of which we can only build single-line fractals, that is, something like the Cantor set cannot be obtained in this way. But this is just a simplification, because we can always enter two other commands for moving forward without recording, and the same for moving backward.Now let's get to the examples!Animated ExamplesThe following examples were taken online from several publicly available sources, and I decided to port them to Python using the Turtle module, center them, colorize them, and provide a way to export to a vector format.ATTENTION: the proposed animations are quite large, it is recommended to watch them only with good internet. The Repl code may not work because it consumes your resources, and there may be problems with displaying fractals on mobile devices.Note: Skulpt uses YOUR BROWSER to render and create animations, so when you hang, lag or any strange behavior, it is usually enough just to re-play the animation or reload the page. May not work on mobile device.The examples are given in order of complexity (in my subjective opinion), so the most interesting thing is at the end.Koch snowflakeaxiom = "F--F--F"
rules = {"F":"F+F--F+F"}
iterations = 4
angle = 60
Koch Square Islandaxiom = "F+F+F+F"
rules = {"F":"F-F+F+FFF-F-F+F"}
iterations = 2
angle = 90
Crystalaxiom = "F+F+F+F"
rules = {"F":"FF+F++F+F"}
iterations = 3
angle = 90
Square snowflakeaxiom = "F--F"
rules = {"F":"F-F+F+F-F"}
iterations = 4
angle = 90
Fractal Wichekaaxiom = "F-F-F-F"
rules = {"F":"F-F+F+F-F"}
iterations = 4
angle = 90
Levy Curveaxiom = "F"
rules = {"F":"+F--F+"}
iterations = 10
angle = 45
Sierpinski Carpetaxiom = "YF"
rules = {"X":"YF+XF+Y", "Y":"XF-YF-X"}
iterations = 1
angle = 60
Sierpinski latticeaxiom = "FXF--FF--FF"
rules = {"F":"FF", "X":"--FXF++FXF++FXF--"}
iterations = 7
angle = 60
Squareaxiom = "F+F+F+F"
rules = {"F":"FF+F+F+F+FF"}
iterations = 3
angle = 90
Tilesaxiom = "F+F+F+F"
rules = {"F":"FF+F-F+F+FF"}
iterations = 3
angle = 90
Ringsaxiom = "F+F+F+F"
rules = {"F":"FF+F+F+F+F+F-F"}
iterations = 2
angle = 90
Cross 2axiom = "F+F+F+F"
rules = {"F":"F+F-F+F+F"}
iterations = 3
angle = 90
Pentaplexityaxiom = "F++F++F++F++F"
rules = {"F":"F++F++F+++++F-F++F"}
iterations = 1
angle = 36
32 segment curveaxiom = "F+F+F+F"
rules = {"F":"-F+F-F-F+F+FF-F+F+FF+F-F-FF+FF-FF+F+F-FF-F-F+FF-F-F+F+F-F+"}
iterations = 3
angle = 90
Peano Gosper Curveaxiom = "FX"
rules = {"X":"X+YF++YF-FX--FXFX-YF+", "Y":"-FX+YFYF++YF+FX--FX-Y"}
iterations = 4
angle = 60
Sierpinski curveaxiom = "F+XF+F+XF"
rules = {"X":"XF-F+F-XF+F+XF-F+F-X"}
iterations = 4
angle = 90
Krishna's Questionletsaxiom = " -X--X"
rules = {"X":"XFX--XFX"}
iterations = 3
angle = 45
Gosper Square Fractalaxiom = "YF"
rules = {"X": "XFX-YF-YF+FX+FX-YF-YFFX+YF+FXFXYF-FX+YF+FXFX+YF-FXYF-YF-FX+FX+YFYF-",
"Y": "+FXFX-YF-YF+FX+FXYF+FX-YFYF-FX-YF+FXYFYF-FX-YFFX+FX+YF-YF-FX+FX+YFY"}
iterations = 2
angle = 90
Moore Curveaxiom = "LFL-F-LFL"
rules = {"L":"+RF-LFL-FR+", "R":"-LF+RFR+FL-"}
iterations = 0
angle = 90
Hilbert curveaxiom = "L"
rules = {"L":"+RF-LFL-FR+", "R":"-LF+RFR+FL-"}
iterations = 8
angle = 90
Hilbert Curve IIaxiom = "X"
rules = {"X":"XFYFX+F+YFXFY-F-XFYFX", "Y":"YFXFY-F-XFYFX+F+YFXFY"}
iterations = 4
angle = 90
Peano curveaxiom = "F"
rules = {"F":"F+F-F-F-F+F+F+F-F"}
iterations = 2
angle = 90
Crossaxiom = "F+F+F+F"
rules = {"F":"F+FF++F+F"}
iterations = 3
angle = 90
Triangleaxiom = "F+F+F"
rules = {"F":"F-F+F"}
iterations = 2
angle = 120
Dragon curveaxiom = "FX"
rules = {"X":"X+YF+", "Y":"-FX-Y"}
iterations = 8
angle = 90
Terdragon Curveaxiom = "F"
rules = {"F":"F-F+F"}
iterations = 5
angle = 120
Double Dragon Curveaxiom = "FX+FX"
rules = {"X":"X+YF+", "Y":"-FX-Y"}
iterations = 6
angle = 90
Triple Dragon Curveaxiom = "FX+FX+FX"
rules = {"X":"X+YF+", "Y":"-FX-Y"}
iterations = 7
angle = 90
CodeAll the above examples were obtained using the same code, and when working on them some difficulties arose (for example, how to keep the fractal in the center as far as possible), working with color, inversion, offsets, as well as providing quick export to vector format. Here I show you only the simplest version.This version displays fractals in black and white and is not equipped with export functionalityimport turtle
def create_l_system(iters, axiom, rules):
start_string = axiom
if iters == 0:
return axiom
end_string = ""
for _ in range(iters):
end_string = "".join(rules[i] if i in rules else i for i in start_string)
start_string = end_string
return end_string
def draw_l_system(t, instructions, angle, distance):
for cmd in instructions:
if cmd == 'F':
t.forward(distance)
elif cmd == '+':
t.right(angle)
elif cmd == '-':
t.left(angle)
def main(iterations, axiom, rules, angle, length=8, size=2, y_offset=0,
x_offset=0, offset_angle=0, width=450, height=450):
inst = create_l_system(iterations, axiom, rules)
t = turtle.Turtle()
wn = turtle.Screen()
wn.setup(width, height)
t.up()
t.backward(-x_offset)
t.left(90)
t.backward(-y_offset)
t.left(offset_angle)
t.down()
t.speed(0)
t.pensize(size)
draw_l_system(t, inst, angle, length)
t.hideturtle()
wn.exitonclick()
Code Explanationimport turtle
First you need to import the Turtle moduledef create_l_system(iters, axiom, rules):
start_string = axiom
if iters == 0:
return axiom
end_string = ""
for _ in range(iters):
end_string = "".join(rules[i] if i in rules else i for i in start_string)
start_string = end_string
return end_string
Then you need to generate an L-system, which will be a set of instructions for the turtle. We define a function create_l_systemthat receives the number of iterations, an axiom, and construction rules. It starts with an axiom and uses an auxiliary variable end_string, if the iteration is 0, then it will return the axiom, since some fractals can also be applied with zero iterations. In this case, it is assumed that the rules have the form of dictionaries, so each key is unique, represents a symbol, and the value indicates what and what needs to be replaced. So we combine all the replacements for each character and eventually get a string for the next iteration.def draw_l_system(t, instructions, angle, distance):
for cmd in instructions:
if cmd == 'F':
t.forward(distance)
elif cmd == '+':
t.right(angle)
elif cmd == '-':
t.left(angle)
Then we determine draw_l_systemwhich accepts the turtle, a set of instructions (output of the L-system), the angle for turning left or right, and the length of each individual line. It consists of a simple structure eliffor each of the previously defined teams.def main(iterations, axiom, rules, angle, length=8, size=2, y_offset=0,
x_offset=0, offset_angle=0, width=450, height=450):
inst = create_l_system(iterations, axiom, rules)
t = turtle.Turtle()
wn = turtle.Screen()
wn.setup(width, height)
t.up()
t.backward(-x_offset)
t.left(90)
t.backward(-y_offset)
t.left(offset_angle)
t.down()
t.speed(0)
t.pensize(size)
draw_l_system(t, inst, angle, length)
t.hideturtle()
wn.exitonclick()
Finally, let's talk about the function main, which takes all the parameters necessary for the generation of L-systems, as well as y_offset, x_offset, offset_angle, widthand height. The first three describe the displacement of the turtle, it is necessary just to position the graph on the canvas the way we want.The function first generates a set of instructions and saves them in inst, then initializes the turtle and the screen and puts the turtle at a specific point, then draws a graph in accordance with the instructions and waits for a click to close.Special considerationsAs I mentioned above, many restrictions are left here. Firstly, we did not provide for the turtle the ability to move without rendering; this would require another character. There is also no symbol for retreating back, and for remembering previous positions. They were not required for all fractals discussed above, but are required for some others (for example, fractal trees).Additional resourcesThe Internet has many resources on fractals, where they are considered both from the point of view of programming and from the point of view of mathematics. The following two seemed especially interesting to me: 3Blue1Brown (math) and CodingTrain (code).The article was inspired by a post from Math World and the article Paula Burka.