Koch Snowflakes

Today I want to talk about a particular kindof fractal known as the Koch Snowflake. Fractals are oneexample of "algorithmic art": interesting geometric pictures createdusing mathematics. First I will explain how to draw the Koch snowflakeby hand. Once we understand the process, we can use the computer toexplore some variations on the usual Koch snowflake, ultimatelycreating some (to my mind) fascinating images like the one below.

You can click on any of the fractal images to see an enlarged versionwith more detail, and if you run the code yourself in R, you can makemuch larger versions. Plus, by changing a few numbers in the code, youcan experiment with creating your own unique images!

The basic idea of "fractals" is simple enough: they are "self-similar"shapes. What does "self-similar" mean? Well, think of broccoli. A headof broccoli has a big thick stem which splits into severalbranches. Each branch in turn splits into smaller ones, and so on,eventually terminating in a very large number of tiny buds. Supposeyou tear off one of the big branches. Up close, it looks essentiallyjust like a full head of broccoli, only smaller: it starts with athinner stem, which in turn splits into smaller ones, and so on.Broccoli is self-similar because each piece looks a lot like aminiature version of the original.

Lots of shapes in nature are fractals. Besides broccoli, trees, andferns, there are examples like coast lines and the craters on themoon. If you look at a picture of the moon that is zoomed in enough sothat you cannot see the edges, it is difficult to tell how far you arefrom the surface. Your view will likely include a few big craters andmany smaller ones. But you could equally well be looking at the wholevisible face of the moon, or at a greatly magnified view of a smallarea within it, because crater patterns on the moon are self similar:they occur at all size ranges, from large to very small.

Crater patterns are also primarily random, because their positionsrecord meteor impacts over millions of years. Today, however, we willbe drawing pictures of fractals that are not at all random: they willbe completely defined by simple geometric operations.

Let's start by drawing the Koch snowflake by hand. Get apencil (you will be doing some erasing, so a pencil is better than apen) and paper. A ruler will help if you want to be precise, but youdon't really need it: the reason to try it by hand first is just tolearn the concept. We will draw more interesting pictures soon usingthe computer.

First, draw a triangle. The symmetric version of the Koch snowflakestarts from an equilateral triangle, but any one will do.

Your picture currently consists of 3 line segments.Now, for each of the line segments, erase its middle third and thenfill in the gap with a smaller triangle. This gives you a 6-pointed star.

Another way to say this is: replace each straight line segment with 4smaller line segments that join together in a _/\_ kind of shape.So, our orignal 3 line segments get replaced by 3*4=12 shorter ones.

Your picture currently consists of 12 line segments. Now, for each ofthe line segments, erase its middle third and then fill in the gapwith a smaller triangle. This produces a "snowflake" shape made from48 smaller line segments.

Now we continue the pattern. Just as the broccoli main stem dividesinto branches, which in turn divide some more, we keep on "iterating"our "erase and draw" procedure.

So, for each of the 48 line segments, erase its middle third and thenfill in the gap with a smaller triangle. This gives you an even moredetailed snowflake pattern. It will also take you a long time, so youmight just look at these computer generated versions instead.

If we repeat the process yet again, we get the following image:

And one last time. You could keep going forever, but the line segmentswill get so small that you won't be able to see them, even on thecomputer screen, so there is not much point.

So that's the "Koch Snowflake". It is pretty, in an abstract sort of way, but it is really just thetip of the iceberg. By modifying our procedure just slightly - forinstance by coloring in the triangles instead of just drawing theiroutlines - we can make much more dramatic images, such as this one:

Time for some computer code. I drew these pictures using R,although you can of course do similar things in any programminglanguage that provides graphics functions. You can follow along bydownloading your own completely free copy of Rfrom The Comprehensive R Archive Network.

If you use Microsoft Windows or Macintosh computers, you maybe used to the idea that you have pay money to get qualitysoftware. R is different. R has been developed byvarious statistics professors and other experts around the world forroughly 20 years, all of whom have donated their time and expertisefor free so that the whole world can have access to a free, highquality statistical programming environment. Practicing statisticiansall over the globe routinely use R in their daily work.

R is not "shareware" or "adware" - there is no "catch"lurking behind it. When you think about it, the existence of R isamazing. The rise of the Internet over the last few decades hasfacilitated programmers sharing code without costs, and a culture ofcontributing (and receiving) help has developed that has led to anumber of unprecedented achievements. Not only R, but Linux (an entireoperating system, analogous to Windows or Mac OS X), GIMP (an imagemanipulation program similar to Photoshop), Inkscape (a drawingprogram similar to Illustrator), and LibreOffice (a word processor /spreadsheet / presentation suite similar to and inter-operable withMicrosoft Office) are all completely free, high quality "open source"programs available for anyone to download on the web - and they are"portable", meaning versions exist for Macintosh, Windows, and Linuxcomputers.

The list goes on - Python (another programming language we usein some of these articles), Perl, Ruby, GNU C++, and many otherprogramming language interpreters and compilers are open source.There are programs for typesetting mathematical journal articles(LaTeX), for recording and playing music (Rosegarden), for turningyour computer screen into a planetarium, and an unbelievableproliferation of all sorts of others. Of course, not all are equallyhigh quality or equally portable. You want the ones that have beenaround a long time and have a large user base of support. Most of theones I mentioned above have established non-profit Foundations thatcoordinate the volunteer contributions and maintain the program forthe long term.

The key phrase is "open source". An open source program is onefor which the source code (the computer instructions, such as the Rcode that I post in most articles) is made publicly available,instead of being kept secret. Companies like Microsoft keep theirsource code secret, so that they can charge you money to buy theprogram. But when a program is open source, anyone can see how itworks, and therefore anyone can improve it. Which is exactlywhat happens: the programs I mentioned above have large numbers ofprogrammers around the world looking at the source code, finding andfixing bugs and adding powerful new features. No one can do this withclosed-source (secret) programs. But with open source, you get thisamazing synergy in which the combined talents of many people aroundthe globe create something of lasting value. People donate theirimprovements because the improvements make the program more usefulto them, but at the same time they make it more usefulto everyone. To paraphrase Newton: if we have achieved more, itis only by standing on the shoulders of giants.

At any rate, copy and paste the following code into R and itwill create various image files ("PNG" - portable network graphicsformat). Or comment out the "png" and "dev.off" lines in the finalparagraph of code by putting a pound (hash) sign (#) in frontof them, to see the results directly on screen instead.

magnif0 <- sqrt(3)/2fill <- function(va, vb, vc, col)  polygon(c(va[1], vb[1], vc[1]),    c(va[2], vb[2], vc[2]), col=col)COL <- rainbow(7)koch <- function(v1, v2, v3, level) {  fill(v1, v2, v3, COL[level])  if(level > 1) {    a <- kochB(v1, v2, level)    b <- kochB(v2, v3, level)    c <- kochB(v3, v1, level)    koch(a$vb, v2, b$va, level-1)    koch(b$vb, v3, c$va, level-1)    koch(c$vb, v1, a$va, level-1)  }}kochB <- function(v1, v2, level) {  va <- (2*v1+v2)/3  vb <- (v1+2*v2)/3  vc <- (va+vb)/2 + magnif*c(vb[2]-va[2], -vb[1]+va[1])  koch(va, vc, vb, level-1)  list(va=va, vb=vb, vc=vc)}size <- 1600for(m in c(1, 1.3, 1.5, 1.7, 2)) {  magnif <- m*magnif0  png(paste("koch-colored", m, ".png", sep=""), size, size)  par(mar=c(0,0,0,0))  plot(c(-0.1-0.5/sqrt(2), 1.1+0.5/sqrt(2)),        c(-0.6, 1.35), type="n", xaxt='n',        yaxt='n', xlab='', ylab='', bty='n')  v1 <- c(0,0)  v2 <- c(1,0)  v3 <- c(0.5, sqrt(3)/2)  koch(v1, v2, v3, 7)  dev.off()}

What is the program actually doing? It is quite short. Start with thefinal paragraph and work backward. The final paragraph sets up a loop:it draws 5 images, using different "magnification" factors (1, 1.3,1.5, 1.7, 2). Each image is 1600x1600 pixels (about 2.5 megapixels indigital-camera parlance), but you can change that by editing the"size" variable.

Each image begins with a triangle, specified by giving the x and ycoordinates for the three vertices (v1, v2, v3). We use (0,0), (1,0),and (1/2, sqrt(3)/2), which define an equilateral triangle, but youcan play with changing these values, thereby creating new shapes!

Given a magnification factor, we then draw a 7 level Koch snowflake. The "koch" function (third paragraph from the bottom) fills in thecurrent triangle with a color that depends on the level. For instance,the first level (the initial triangle) is filled with a rose (magenta)color; you can change the COL variable to some other list of colors ifyou prefer.

Then, we iterate: we call "kochB" on each of the three sides of thetriangle, and then call "koch" again on each of the three vertices.This will seem a bit odd: in my original description above, Idescribed how to outline the Koch snowflake by drawing anderasing line segments. This code, however, is doing something a bitdifferent: it is coloring in the area inside the snowflake, using adifferent color at each new stage of the process. As a result, insteadof drawing and erasing 3 line segments, I have to color in six smallertriangles at each step.

The "kochB" function does the real work: finding the middle third ofeach edge (va, vb), then finding a new vertex (vc) for the "pushedout" corner of the new triangle in the _/\_ shape. This is where the"magnification" factor comes into play: it determines how far the newvertex vc is positioned away from the "middle third" line segment.

When the magnification factor is 1, the sqrt(3)/2 that we stored in"magnif0" in the first line of the program puts the vc vertex in the"symmetrical" position for an equilateral triangle. So magnification 1corresponds to the original Koch snowflake; the original equilateral triangletransforms into a symmetrical 6-pointed star.

But the subsequent pictures in this list have used magnificationslarger than 1. As you can see, this makes the new triangles bigger:they point further out away from the center. By the time themagnification is 1.7, as in the image directly above, this expansionmakes the subsequent levels overlap with earlier ones, resulting in acomplicated "oriental carpet" sort of pattern.Magnification 2.0, shown below, again gives a sort of "oriental carpet" pattern.

I would like to encourage you to experiment with modifying this Rprogram. Try changing things and see what happens. If you make toodrastic a change you may get a jumble of lines and colors you don'tthink is very pretty, but if you make small, subtle changes, you canachieve all sorts of interesting effects.

For example, in this final series of images, I have added a blackbackground for drama, and more importantly, I have changed somenumbers in the code.

I changed the initial vertex positions so that my starting trianglewas no longer symmetric but a little skewed.

I also changed the "kochB" function. Instead of removing the middlethird of each edge, I remove a line segment that is slightly offcenter.

Together these changes created a skewed effect which is kind ofinteresting. Combining that with increasing the magnification resultsin this series of images. Especially in this final example you can seethe original triangle, and the division of each of its edges intosub-triangles, in the form of faint black shadow lines.

Have fun experimenting! If you create an image you really like, sendit along, I would be interested in seeing it!

If you enjoyed this article, you might also like Algorithmic Art, for more colorful designs based on using 'e' as the scaling ratio, orWhy are there exactly five Platonic solids?, for more on symmetry.

You can click the "M" button below to email this post toa friend, or the "t" button to Tweet it, or the "f" buttonto share it on Facebook, and so on.

As usual, please post questions, comments and other suggestions using the box below, or G-mail me directly at the address mentioned in the Welcome post. Remember that you can sign up for email alerts about new posts by entering your address in the widget on the sidebar. If you prefer, you can "follow" @ingThruMath on Twitter to get a 'tweet' for each new post. The Contents page has a complete list of previous articles in historical order. Now that there are starting to be a lot of articles, you may also want to use the 'Topic' and 'Search' widgets in the side-bar to find other articles of related interest. See you next time!