More fun with fractals
Mike Bedford continues to review the curious world of fractals by delving into objects that mathematicians first described as “monsters”.
Mike Bedford continues to review the curious world of fractals by delving into objects that mathematicians first described as “monsters”.
The famous Mandelbrot Set likely springs to mind when talking fractals, but it’s just one of a whole group of fractals known as escapetime fractals. As it is there are several categories of fractals that are generated in quite different ways. Escape-time fractals are, perhaps, the most unexpected because, at first sight, it seems barely plausible that applying such a simple formula could produce an image that is visually attractive and literally infinite in the amount of detail it contains. By way of contrast, some of the algorithms used to generate these fractals might seem to be designed specifically to generate a fractal result – but nevertheless we promise to lead you on an astonishing voyage of discovery…
Lost in the Sierpinski Triangle
As fractals are so visual we’re going to leave the maths for later and start by providing a hands-on introduction so you can see fractals on-screen from the very start. The fractal we’re going to look at is called the Sierpinski Triangle and you can generate it with the Xaos software. You can find the Sierpinski Triangle at Fractal > More Formulae > 7 Sierpinski, and investigate it by zooming and panning, using the intuitive interface.
You’ll notice the characteristic nature of a fractal – something that shows self-similarity at all levels of magnification – but in a change from the Mandelbrot Set and other escape-time fractals, that self-similarity is exact. Yes, the Sierpinski Triangle contains nothing more than triangles, at ever smaller scales, going on literally forever.
The real nature of the Sierpinski Triangle is somewhat hidden in Xaos, because of its use of colour to make the image more visually attractive. To see more accurately what this fractal figure really is, and one way it can be generated, head to the online tool at http:// bit.ly/lxf252fracgen1. Initially you’ll be shown a fairly small, partially generated Sierpinski Triangle, but we suggest you select a larger size and start with ‘Step 0’, which is just a single solid triangle. Rather than present you with an apparently complete fractal that you can zoom into, this utility enables you to step through its creation, even though this means that you’d only see the real Sierpinski Triangle if you stepped through an infinite number of iterations.
Now click on the right-arrow icon to move to Step 1 and you’ll see that the initial triangle has been split into four smaller triangles and the centre one removed. Move to Step 2, and each of the remaining three solid triangles are similarly divided into four smaller triangles and, in each case, the central one removed. The same process is repeated over and over to produce the Sierpinski Triangle, and it would be a fairly simple coding task to do this yourself.
The Sierpinski Triangle predated Benoit Mandelbrot’s coining of the word “fractal”. Instead, when this and similar geometrical figures were first discovered in the early 20th century, they were collectively referred to as “monsters”. Some of the Sierpinski Triangle’s monstrous characteristics are that its perimeter is infinite in length, yet it is contained in a finite area. Moving on, we learn that the area of this geometric figure is zero. Even more strange is that it’s a 1.59-dimensional figure. If you thought everything was two- or three-dimensional, or four at a pinch, take a look at the box on page 73.
The Sierpinski Triangle can be described as a geometric fractal, because it’s produced by repeating a simple geometric manipulation. However, it might be better to reserve that term to the method of generation because, as you can see from the box on page 71, there are countless ways of producing it.
Nevertheless, if you want to see some more examples of geometric fractals, has a couple more up its sleeve, in the form of the Sierpinski Carpet and the Koch Snowflake.
Next we’re going to delve into Iterated Function Systems, or IFS for short, which is another method of generating fractals. While this approach can be used to generate very regular-looking fractals, it can also produce results that don’t look anywhere near as regular and geometric as the Sierpinski Triangle.
Getting iterated
To get a feel for IFS fractals, download Ifstile from https://ifstile.com (you won’t find it in the repositories). You could use it to generate very regular fractals of the type we saw in the previous section, but we’re going to try something different, so go to File > Open Example > [3D]_trees and select any of the four trees – we quite liked Tree3. You might think the result looks more like a fern; it certainly looks like something you could find growing in your garden, yet it was produced by repeatedly carrying out a simple transformation. Ifstile appears to be packed with functionality but unfortunately its Help facility is limited to just providing ‘About’ information, and the website’s link to the user manual didn’t work as this article went to press. However, we did find a related PHD thesis by its author, which includes a section on using Ifstile. It might take some perseverance to really get up to speed with Ifstile, but if you want to delve into that thesis you can download it from http://bit.ly/lxf252fractal.
There’s no better way to get a better feel for the IFS approach than writing some software yourself. It’s by no means a difficult coding exercise and it’s an ideal way to understand how it works. Like virtually all methods of generating fractals, the approach is iterative and, in this case, you start with nothing more than a random point which is defined by itsx andy coordinates. The iterative process involves generating and plotting a new point by carrying out a simple geometric transformation that is defined by the following: xn+1 = axn + byn + e yn+1 = cxn + dyn + f where xn and xn+1 are the x coordinates of the point in the current and next generation, yn and yn+1 are the y coordinates of the point in the current and next generation, and a,b,c,d,e and fare constants that define a particular fractal. In fact, in all but the very simplest of Iterated Function Systems, there are several sets of those six constants, each of which has a probability in the range 0 to 1 associated with it, the sum of all the probabilities adding up to 1.
So, for each generation a random number is generated and this is used to determine which of the sets of constants to use. We suggest you start with a known fractal so you know what to expect; for example, the following data generates a fern that looks similar to the one generated by Ifstile. Each row of the table lists the six constants a,b,c,d, ea ndf,pl us the probability associated with that set of constants, in that order.
The fractal fern is just the tip of the iceberg, so to speak. It transpires that so many of the forms we find in nature have fractal properties and in addition to trees and ferns, we could list coastlines, rivers, clouds, lakes, mountains and even a variety of broccoli called Romanesco, which appears to be a perfect fractal. In reality, of course, anything that exists in nature can only ever be an approximation to a true fractal in the sense that, whereas mathematical fractals go on forever, realworld objects will come to the end of the line eventually, and certainly when molecular dimensions are reached.
The fractal nature of the world around us isn’t just an interesting mathematical curiosity but it’s also used to good effect in animated movies and video games. Rather than having to store very detailed descriptions of landscapes, realistic-looking islands, mountains, rivers and clouds, they can be generated on the fly using fractal techniques. If you want to try your hand at creating fractal landscapes, options are few. Free software is pretty thin on the ground and most of it is for Windows. However, to get a feel for the results that are achievable, how about trying the demo version of
Fractscape from https://starscenesoftware.com/ fractscape.html, which runs under Linux. You’ll find that you can generate realistic-looking landscapes, but you can also produce ones that are very otherworldly in their appearance. Fractscape is a reasonably fully
featured package, even though a licence costs just $20 – vastly cheaper than those packages aimed at games creators and animators. However, it’s interesting to note just how little code is required to generate a basic fractal landscape. The utility at http://demos. playfuljs.com/terrain, for example, comprises just 130 lines of Javascript – refresh to see different landscapes, seeded by different random numbers.
Lindenmayer Systems
Aristid Lindenmayer was a Hungarian biologist who studied the growth patterns of yeast, fungi and algae, and developed a mathematical system to define their development. The system that bears his name – but which is often referred to just as the L-system – has more recently been used to model the growth of more complicated biological forms and even geometriclooking fractals.
An L-system is a specific type of string-rewriting system in which a particular string of symbols is replaced by another string, generation after generation, each representing a better approximation to a particular fractal. Similar systems can be used as general models of computation, despite the fact that, in this case, the purpose is specifically to generate a fractal figure. A particular L-system is defined by its alphabet – that is, the specific symbols it uses to compose strings, the so-called axiom – that is the string in the first generation, and the set of rules that define how symbols are substituted for other symbols from one generation to the next.
As an example of how this can carry out a general computation, let’s think about a system with an alphabet of two symbols, A and B, the axiom of A, and the following two rules: A > AB and B > A. It’s a simple task to generate the first few generations by hand and you’ll discover that they are A, AB, ABA, ABAAB, ABAABABA, ABAABABAABAAB, and ABAABABAABAABABAABABA. Although this particular system was developed by Lindenmayer for modelling algae growth, it’s evident that the lengths of the strings – 1, 2, 3, 5, 8, 13, 21… – are actually Fibonacci Numbers: that is, the sequence of numbers in which each number is the sum of the previous two numbers.
For the purpose of generating fractal images, we use an alphabet in which each symbol represents a drawing function. We’ll illustrate this to draw a geometricallooking fractal that we’ve not seen so far. The alphabet comprises F and G, both of which are instructions to draw a line of a fixed length in the direction of the current heading; + which is an instruction to turn 90 degrees to the right; and – which is an instruction to turn 90 degrees to the left. The axiom is F, and the rules are F > F - G and G > F+G.
Like so many fractal coding exercises, it couldn’t be much simpler to try this out in your own code. One bit of advice we should give is that the length of the line generated by an F or G command should halve with each generation, so that the overall figure remains approximately the same size. We also suggest that you write the code so that you can move from one generation to the next via a keystroke, to appreciate how the fractal develops. The result is called a Dragon Curve and, if you’d rather use someone else’s code, there’s a good online utility for a wide range of fractals at the same link we saw earlier at: http://bit.ly/lxf252fracgen1.
By default this shows the Sierpinski Triangle, but the Dragon Curve is just one of its many fractals, and it allows you to track it from generation to generation, starting with just a straight line. Having seen the Dragon Curve build up, it’s clear that the process of moving from one generation to the next involves replacing all straight-line segments with two shorter line segments and a right-angled bend, and this suggests another way of generating it, if you fancy knocking up a bit of code.
It might not involve coding, or using any software at all for that matter, but you might be interested to learn of another, very different way, of generating the Dragon Curve. Take a sheet of A4 paper and observe the longest side, edge on. What you’ll see, of course, is a straight line, which just happens to be the first generation of the Dragon Curve. Now fold the paper in half, with the fold across the shortest edge, and then open it out so the crease is a right-angle. Looking at this edge-on again, you’re now seeing the second generation. Fold it back so it’s flat and then fold it again, parallel to the first fold. Again open it out so that the creases are right-angles and you’ll now observe the third generation of the Dragon Curve.
As you make more and more folds, it becomes increasingly difficult to open the sheet up so that all the folds are right-angles, but you might like to go as far as you can so that you get a more representative Dragon Curve. Although this has been an exercise in origami
rather than programming, the process can easily be expressed algorithmically, so it offers yet another way of generating this fractal in software.
The Dragon Curve can be represented as a string of left and right bends, which we can show as R and L, with an implied straight-line section between each bend. Using this way of expressing it, the first generation is the null string, which represents a straight-line section with no bends. Now to generate the next generation, start with the string for the previous generation, add an R, and then append the string for the previous generation reversed and with all the Ls converted into Rs, and all the Rs changed to Ls. This, therefore, will give R as the second generation. Successive generations are represented by RRL, RRLRRLL, RRLRRLLRRRLLRLL and so on.
Finally, for those who intend to write some code, whatever method you use for generating the Dragon Curve you might like to consider rounding off the rightangled bends. The curve never crosses itself but it does touch and this can give the impression of it crossing. If all right-angles are rounded off, however, the true path is evident – plus you might feel that this representation is more aesthetically pleasing.
Into the third dimension
In the light of our coverage last issue of the Mandelbulb, – the 3D equivalent of the well-known 2D escape-time fractal the Mandelbrot Set – it seemed appropriate to round up this article by extending the principles of the more regular fractals into the third dimension as well. In fact, since you might already have it installed last issue, the obvious choice of software is Mandelbulber – and as one of the fractals we’ve seen most of in this article, why not take a look at the 3D equivalent of something rather similar to the Sierpinski Triangle?
So, start up Mandelbulber, select ‘Menger sponge’ as the Fractal formula type, and click the Render button. The fractal of that name appears in the Render window. Quite evidently, it’s been created by repeatedly splitting a cube into smaller cubes and, after each such subdivision, removing one of the cubes – and in that respect it’s a close relative of the Sierpinski Triangle. This is by no means a unique example. 3D fractals abound; indeed the fractal landscapes we looked at briefly are another example. What’s more, some of the more advanced landscape generation software is able to populate those fractal landscapes with forests made up from fractal trees.
In fact, why stop at three dimensions? We might live in a three-dimensional world but that doesn’t stop mathematicians postulating about four-dimensional figures, and that includes fractals. The only snag is that they’re hard to visualise, so we have to make do with three-dimensional projections – and even those have to be rendered in two dimensions for display on screen. However, if you fancy a more challenging programming challenge, why not respond to the call of the fourth dimension? (And we don’t mean time in this case!)