In the following article, I'm gonna show how to build an application to draw the Sierpinski Triangle (https://en.wikipedia.org/wiki/Sierpinski_triangle). The Sierpinski Triangle is a fractal figure which represent a triangle, and inner triangles leaving always the central one intact. This is a great exercice to do in C, as it trains the loops and pointers.
The application must generate a Sierpinski triangle of a given number of steps (it will be an input argument of the main application) and plot the result into a PNG file with gnuplot. As every programming application, there isn't a single way to build the application. Here, I'm going to show the solution, and how I developed the solution. The way I do, is going from the generic to the specific. First of all, write the main.c file calling both the SierpinskiGenerator and the plot. As those two functions are not yet defined, I don't know which parameters they need, so, I'll assume what they should need and correct it later (I almost know which parameters they need, as I spend some hours doing the application, but in a usual workflow, you don't know). The SierpinskiGenerator should need the size of the main triangle, and the number of iterations. I let the SierpinskiGenerator work already with pixels, this way I won't need to convert from some arbitrary convention to pixels when plotting the result. But usually, you should have a abstract generator and some translators, this way your generator will give you some results, and you can plot it with a translator to pixels, to write it to a CSV file with a CSV translator... But for the current example, it will reduce complexity if I work in all the application with pixels.
The plot function will need the data of the generated triangles, and the amount of triangles. I assume that in the triangles there is already the pixels information. Here is the code of main.c:
From lines 10 to 12 I've made a validation allowing the application to run only if the number of iteration is specified, otherwise, nothing will happen (only a warning/error message will be shown).
Let's go now with Sierpinski generator. First off all, as seen in the main.c, there is a Triangle data type. This is a defined structure in C. A triangle is composed of 3 corners, and each corner is composed of two coordinates (X and Y). Instead of handling a list of float with all those values, I've grouped all of them in two structures: Point and Triangle:
I've stored the structures in the sierpinski.h file as this is the main entry point of those structures. Importing the sierpinski.h file, I can use the Triangle and Point structures everywhere.
For the Sierpinski generator, I've made two implementation, the first one with for-loops (multiple levels), and the second one with recursion. What's the recursion? When a method call itself. This is useful with multiple mathematical applications and in particular with fractals.
Let's start with the easiest, the for-loops. I have to iterate into a first for-loop the number of steps given by the user. Inside this for-loop, I have to iterate over all the existing triangles and generate inner triangles. I create two methods: one to generate a single inner triangle (the central one), and a second to obtain all the triangles except the central one (by elimination). Here are those two methods:
As you can see, the structures, can be used with the sizeof method too (which is very useful to allocate the memory).
And here is the main method, which build our complete Sierpinski triangle:
The first implementation has 3 for-loops (line 25, 26 and 29), which means that when the steps of the Sierpinski triangle increase, this could lead to an important time consuming for the machine. Let's examine the code. First allocate enough memory for all the triangles. Then initialize the first triangle with the given size. And finally, the loops. The first loop will iterate over the number of steps of our fractal. The second will iterate over the existing triangles, and the third will prepare the data for the next fractal iteration saving the triangle data into a separated variable. This is also done in line 35 with the memcpy method which allow you to copy the data from a pointer to another pointer.
Go now with the second implementation. I haven't made a lot of changes inside the methods, to maintain the readability of the code.
The first method is similar to the first implementation, and the second method is the one used in recursion (you can see that the generate_sierpinski_triangle_recursively is called at line 71). This allow us to hide a for-loop. I said hide, as the loop is still there, it's the recursion. The initial condition is the iteration value; the final condition is at line 70; and the statement for each step is at line 71 (--iterations).
Which implementation is the best? It depends. The behavior is quite similar, there are some differences at memory consumption and CPU usage (the first allocate a lot of memory at the beginning, but the second is constantly allocating memory). If there are a lot of for-loops, the second implementation is better for readability (all is split into smaller methods), but you have to do it carefully as the exit condition is not as explicit as the for-loop.
And finally the graph generation. gnuplot was used to plot the graph. Each triangle will be plotted with lines. Here is the code of plot.c:
As said at the beginning, this is not the only (and best) solution of the problem, but I tried to do it in a way which could easily be understood.
No comments:
Post a Comment