Two complex numbers can be added and subtracted as ordinary binomials, giving similar terms containing an imaginary unit. Let z = x + ⅈ y and w = u + ⅈ v. Then z ± w = x ± u + ⅈ y ± v.
For complex numbers, the multiplication operation is also determined. Two numbers are multiplied in the same way as binomials, only the imaginary unit squares encountered in the resulting expression are replaced by - 1: z w = x + ⅈ y u + ⅈ v = x u + ⅈ x v + y u + ⅈ 2 y v = x u - y v + ⅈ x v + y u.
To determine the division of complex numbers, we transform the fraction z w, multiplying its numerator and denominator by the number w ¯ = u - ⅈ v, which differs from the denominator by the sign of the imaginary part (this number is called complex conjugate): zw = z w ¯ w w ¯ = x + ⅈ y u - ⅈ vu + ⅈ v u - ⅈ v = x u + y v + ⅈ y u - x vu 2 + v 2. Of course, the denominator must be nonzero.
The set of complex numbers for which arithmetic operations are defined is called the field of complex numbers. It deserves a separate designation ℂ.
Building the Mandelbrot set
Consider the square polynomial f z = w + z 2, where z w ∈ ℂ. Put z 0 = 0. Then, using the polynomial, we can construct a recurrent sequence of complex numbers z k + 1 = f z k. We will call this sequence the orbit of zero (the term “orbit” was already used in chapter 15. “Decimal fractions"). Zero - because the first element of the sequence is zero. So, here are the first few elements of the orbit: 0 w w + w 2 w + w 2 + 2 w 3 + w 4 ....
An orbit will be called bounded if all its elements remain on the complex plane inside some circle centered at zero. The remaining orbits will be called, naturally, unlimited. Both the zero orbit itself and its boundedness depend on the number w, and the Mandelbrot set is defined as the set of those numbers w for which boundedness takes place.
Defining Orbital Limitations
We faced the task of determining the boundedness or unboundedness of the zero orbit for each given complex number w. Unfortunately, it is not possible to write out the general formula for the elements of the orbit z k = f f f ... f 0 ..., where k icons are f. So, analytical methods are unlikely to help solve the problem. For our purposes practically an orbit can be considered unlimited, which, sooner or later, breaks out beyond a circle with a center at zero of a sufficiently large radius R, say, equal to 100. But this may happen sooner or later, or it may never happen. However, the algorithm that determines the limitations of the orbit must be stopped at some point. Therefore, we will need to formulate one more condition under which the orbit can be considered practically limited.
Recall that an exact representation of a real number in a computer is impossible, and that the number of representable numbers is finite, albeit very large. Because of this, the number of complex numbers inside a certain circle will also be finite. When calculating on a computer, any orbit is necessarily looped, because its elements belong to a finite set and are calculated recursively. It would be wise to consider the orbit practically limited if it goes in cycles before leaving the big circle. The Floyd method, described in detail in the “Tortoise and Hare Method” section, helps to determine the looping moment. Recall that the key circumstance on which the Floyd method is based is the equality z k = z 2 k for some k, that is, the coincidence of the elements of the “turtle” sequence z k and the “rabbit” z 2 k. Once equality is fulfilled, it can be argued that the Turtle has already entered the cycle.
The trouble is that in the worst case, the looping can occur no earlier than the orbit (Turtle) will visit each and every complex number in a circle, and there are a lot of them. We will not wait until the moment of looping comes. Instead, we will consider the orbit practically looped if the turtle sequence is close enough to the rabbit sequence, that is, the condition z k - z 2 k 1 R is fulfilled.
So, if it turns out that the sequence is practically looped before its practical unlimitedness is revealed, it is declared practically limited.
Mandelbrot set image method
Now, for each complex number w, one can determine whether it belongs to the Mandelbrot set or not. You can paint the points of the set in black, leaving all the others white. But the image in Figure 48.1. The Mandelbrot Set is colored. What is the meaning of this coloring? The Mandelbrot set itself is depicted in red. The appearance of the set is green. The faster the zero orbit leaves a circle of radius R, the brighter the green coloring of the point w. Inside the set, contrary to tradition, we also used various degrees of intensity of red to get a more expressive image. The red color is lighter the faster the limited orbit is detected.
Thus, for each number w it is possible to calculate the color with which it will be painted over on the image, as the number I from the interval 0 1. This will be the intensity of red (for points from the set) or green (for all others) colors in the picture. In any case, the found number should depend on the number n of orbit elements found before its boundedness or unboundedness was discovered, and decrease with increasing this number. To distinguish between these cases of boundedness or unboundedness, we assign a sign to this number: for bounded orbits, let it be a minus. Color, red or green, is selected depending on the sign.
We experimented by choosing the dependence of the color intensity on n, and settled on I n = ± 1 n 4 + 1 (adding a unit under the root sign excludes division by zero at n = 0, and division by 4 brightens the picture). It is easy to understand that the largest values of n, and therefore the darkest colors, are found near the boundary of the Mandelbrot set, where the orbit spends a lot of time, deciding either to rush to infinity or to remain limited. Figures 48.1 and 48.2 confirm this idea.
The symmetry of the Mandelbrot set
Figure 48.1 demonstrates an important property of the Mandelbrot set - its symmetry with respect to the real axis. In other words, with complex conjugation, the set goes into itself. This is easy to prove. Note that the boundedness or unboundedness of the orbit will not change if each element is subjected to complex conjugation. It remains to prove that the zero orbits for w and w ¯ are symmetric to each other when reflected relative to the real axis. For w, we obtain the orbit O w = 0 ww + w 2 w + w 2 + 2 w 3 + w 4 ... and for w ¯ - O w ¯ = 0 w ¯ w ¯ + w ¯ 2 w ¯ + w ¯ 2 + 2 w ¯ 3 + w ¯ 4 .... Since all elements of the orbit O w are polynomials in w with real coefficients, it remains to prove that complex conjugation can be taken out of the sign of such polynomials: g w ¯ = g w ¯. The latter fact follows from two easily verifiable properties of complex conjugation: p ± q ¯ = p ¯ ± q ¯ and p ⋅ q ¯ = p ¯ ⋅ q ¯ for any complex numbers p and q. So, O w ¯ = O w ¯, as required.
It is a sin not to take advantage of the proved circumstance in those cases when the displayed fragment of the complex plane contains a section of the real axis. Then, for some points, you can not find the color by calculating the elements of the orbit, but simply copy it from the complex conjugate point. This, of course, will speed up the calculations at the cost of a little complication of the algorithm.
This article is intended for those who are already at least a little familiar with the C # and F # languages. In any case, I tried to make the code as readable as possible and give a description of each fragment. You can familiarize yourself with the F # language in the following articles:
- Introduction to F #, or Useful About Useless
- F #: Hello, World!
- MSDN: First introduction to F #
Already many general words were written on Habré about the F # language - its history, origin, features. I do not want to repeat myself, so I propose to go straight to the point. So, the action plan is as follows:
- Building the Mandelbrot set,
- Visualization of results,
- Integration with C # and not only with it.
How is the Mandelbrot set determined?
Consider the sequence of numbers generated by the following equation:
Cn + 1 = Cn 2 + c0
If such a sequence does not go beyond two complex numbers C1(1, 1i) and C2(-1, -1i), then the complex number c0 belongs to the Mandelbrot set. Therefore, the Mandelbrot set is the set of all such numbers c0in which the sequence considered above remains within C1 and C2.
Mandelbrot set and F #
To work with complex numbers in F # there is a Microsoft.FSharp.Math library, which, in turn, is available in the FsharpPowerPack package (the link also provides installation instructions and other useful information about this package). Add this library to our project and specify it:
Now we can manipulate complex numbers in a program. Define the minimum and maximum boundaries:
We proceed directly to the function. We implement the function of checking for membership in the set as follows:
The recursive function isInMandelbrotSet works until the number being checked exceeds the boundaries of cMax and cMin, and the recursion depth does not exceed the number of iterations. Upon completion, the function returns the number of perfect recursion steps (this will be useful to us in the future when we “colorize” our set).
We have already built a great many, it remains only to display it. But here the fun begins.
Since complex numbers consist of two parts, we can create their display on a two-dimensional plane. Mandelbrot set exists between C1(1, 1i) and C2(-1, -1i), so the coordinate system we need will have a center at the point (0, 0), the abscissa and ordinates will be limited to -1.0 and 1.0.
Therefore, we need to carry out the transfer of the coordinates of the points from the complex plane to the one used in the construction of the image.
Let's do it as follows:
This function will return for each point of the "familiar" plane the corresponding complex number. We will use the values mx and my in the future to implement navigation in our image.
Now we can easily draw our entire set on the familiar plane. To do this, we need to “walk” along all the coordinates of the plane and verify that each point (more precisely, the corresponding complex number) belongs to the Mandelbrot set. If the point belongs to the set, we will make it black, otherwise we will color it in a different color. To do this, we will make a special “coloring” function:
The function will take the number of iterations we got from the isInMandelbrotSet function and determine the RGB value of the color. Numerical coefficients can be set any, but in order to achieve a smooth transition of colors, it is advisable to set them with a small difference. Also, here we need the System.Drawing library:
Using this library, we will create a new bitmap image and add points of a certain color to it. So, our rendering function will look like this:
Here we use the System.Windows.Forms component:
It remains only to run our program and enjoy the result. You can do this as follows:
We indicate the initial parameters: scale, offset in X and Y, as well as the number of iterations. The larger the number of iterations, the more detailed our image will be (and, accordingly, it will take longer to create). Something like this should result in the work:
So, a complete listing of our program:
As you can see, it took us a little more than 40 lines to create the “color” Mandelbrot set and not so much time. But we still cannot fully enjoy the beauty of fractal images (more precisely, we can, but it’s completely inconvenient to change the image scale before each compilation). To overcome this problem, you need to add interface elements - navigation keys and increase / decrease the image, preferably changing the details.
Of course, you can create all the interface elements inside F # in the same way as we created the form itself using the System.Windows.Forms library. But on the other hand, it would be much more interesting (and, perhaps, more logical) to do this in the framework of a full-fledged Windows Forms application! Okay, then let's do it now.
Integration with C # and not only with it
After assembling the F # application, at the output we get a library containing all the functionality we need. For convenient access to the necessary functions of this library, declare namespace in the F # code. This is done as follows: at the very beginning of the code, add
In addition, we no longer need the form, as well as the code that runs it. Therefore, now the function that we will call from the outside will look like this:
The called function createImage returns the created bitmap image containing the Mandelbrot set.
Using the F # Library in Windows Forms
In fact, everything is very simple: you just need to add the finished library to a new project (for example, Windows Forms or any other). Having created the project, in MS Visual Studio this can be done using the Add Reference command of the Solution Explorer window, selecting the required library. Since we previously designated namespace in the library (module Fractal), in the new project we have access to all the functions of this library. Now call the function that will generate the finished image, as follows:
The resulting bitmap image can already be used in any way - for example, add as a background to the PictureBox element.
Adding Navigation Elements
As you can see, we can “request” image generation with various parameters: scale, number of iterations, offset relative to X and Y. That means adding navigation is not difficult. We’ll take PictureBox as a container for our image, we will navigate using 6 buttons: zoom in / zoom out, move up / down, left / right.
For convenience, create a separate class FractalClass, which will store the state of the current fractal: scale, offsets from the center, level of approximation. The main method of the class will request an image of the set with the current parameters.
The remaining methods of the class will change the state of the fractal and refer to the Draw () method. So, for example, the approximation method may look:
It remains only to add the call to the corresponding methods of the FractalClass class to the processing of keystrokes for navigation. The result will be something like this:
The ability to pass the required number of iterations to the function allows you to refine the fractal as it approaches. Therefore, with each step, the image becomes more and more interesting:
About the Mandelbrot set
The Mandelbrot set, like the Newton basins considered earlier, refers to fractals - sets that have the property of self-similarity. This property consists in the fact that the set can be divided into parts, each of which has a structure that coincides with the structure of the original set (or close to the structure of the original set), moreover, the division of some parts into other parts, "reproducing" (in one or another degrees) initial, can be continued indefinitely.
The Mandelbrot set, in addition to various valuable properties, is also interesting because it can have very attractive visuals from an aesthetic point of view. We will build some of the visualizations with the help of our future program.
Before moving on to visualization, we give a definition of the Mandelbrot set.
Consider, first, an arbitrary complex number z0 = x0 + iy0. This number corresponds to a point on the complex plane with coordinates (x0, y0) In what follows, we will identify complex numbers with the corresponding points of the complex plane. Complex sequence
let's call Mandelbrot sequence for the point z0. It is clear that each such sequence is either bounded (modulo, of course) or unbounded. The Mandelbrot set is the set of all such points of the complex plane for which the Mandelbrot sequences are bounded.
The simplest visualization of the Mandelbrot set is as follows. The pixels of a canvas for drawing are naturally mapped to the points of a certain rectangular region of the complex plane. Pixels corresponding to the points of the plane belonging to the Mandelbrot set are colored in black, and the rest in white. By the way, it is known that the points of the Mandelbrot set are more or less “placed” in a square centered at the point (-1/2, 0) with side 2.
To construct such a visualization, obviously, an algorithm is required that establishes whether one or another point of the complex plane belongs or does not belong to the Mandelbrot set. The problem is that there is no universal algorithm that works for any point. However, it is known that the Mandelbrot sequence, the modulus of a certain term of which exceeds 2, modulo tends to infinity, i.e., is not bounded. This means that the initial term of this sequence does not belong to the Mandelbrot set.
Это утверждение позволяет нам использовать алгоритм определения "условной" принадлежности точки данному множеству. Заключается он в вычислении фиксированного, заранее выбранного числа первых членов последовательности Мандельброта для проверяемой точки. Если модуль ни одного из вычисленных членов не превосходит числа 2, то испытуемая точка считается принадлежащей множеству Мандельброта. В противном случае точка считается этому множеству не принадлежащей.
The authors of the book mentioned earlier propose to limit themselves to finding the first 255 members of the sequence (including the point being checked). If all 255 numbers do not exceed 2 in absolute value, then the corresponding pixels are painted black. If the initial term (i.e., the point being checked) itself exceeds modulo 2, then the corresponding pixel is painted over in white.
If the non-affiliation of the point is established z0 Mandelbrot set due to the fact that for some minimal k such that 1 ≤ k ≤ 254, the inequality |zk| > 2, then in this case it is logical to color the corresponding pixel also in white. However, the authors of the book offer a different approach: paint the pixel with a shade of gray. In this case, the fill color should be closer to white, the smaller k and the closer to black the more k. More specifically: gray intensity is proposed to be calculated as the difference 255 - k.
In this case, we mean the intensity, which coincides with the values of each of the three components when saving colors in RGB format. Recall that each shade of gray corresponds exactly to the coincidence of the components.
Thus, our “picture” will not contain only two colors: black and white. But it will also include dots of a gray hue, the darker the "later" the members of the Mandelbrot sequences for these points exceed in absolute value the number 2.
As we can see, the coloring algorithm is very simple, perhaps it’s not even necessary to formulate it in a strict form, but you can already proceed to building the program.
Program structure. Preprocessor directives
The program will consist of the main main.c file, as well as three files that make up the pgraph library. The header file of the pgraph.h library will be connected to main.c using the #include directive. Here's what the preprocessor directives look like with which the main.c file starts:
As you can see, besides praph.h, the header file of the standard library for working with complex numbers complex.h is also connected to our file (you can read about C99 support for complex numbers (within the framework of using the MinGW64 compiler) here).
Next, using the #define directive, 5 macros are defined that have the following meaning:
- W is the image width,
- H - image height,
- X0 is the abscissa of the pixel in the original coordinate system, in which the beginning of the new coordinate system is placed,
- Y0 - the ordinate of the pixel in the original coordinate system, in which the beginning of the new coordinate system is placed,
- L is the length of a segment that has a unit length in pixels in the new coordinate system.
Let us explain that the original coordinate system is the one used in the pgraph library and allows you to access the pixels of the image by coordinates. And the new coordinate system is the one that we introduce on the complex plane to construct the image of the Mandelbrot set in it.
It is easy to notice that a pixel having coordinates (i, j) in the original coordinate system will correspond to a point with coordinates
((i - X0) / L, (j - Y0) / L)
in the new coordinate system.
As we see (see the code), our image will be square, displaying an area of the complex plane of about 2.1x2.1 in size, and the origin is equidistant from the "lower" and "upper" borders of the square and about 2 times closer to the "right" its border than to the "left." The choice of parameters leading to the described state of affairs is due to the previously mentioned feature of the "localization" of points of the Mandelbrot set.
The main.c file will contain the definitions of two functions: get_gray_color () and main (). Let's consider each of them.
Calculation of pixel gray intensity: get_gray_color () function
The following is the code for the get_gray_color () function.
The function takes as a parameter a point on the complex plane and returns the "color" with which the pixel corresponding to this point should be colored. The word "color" is placed in quotation marks, because, to be precise, the pixel is painted in one of the shades of gray (including white and black), and this function returns, in fact, the intensity of gray in the range from 0 up to 255. We explain that the uchar type is defined in the pgraph.h file and is equivalent to the unsigned char type.
The algorithm for finding the intensity has already been described previously. The current intensity value is contained in the gray variable (page 4). During the for loop (see page 4-9), gray runs through the intensity values from 255 to 1, and during the cycle, the values of the Mandelbrot sequence for the starting point are calculated (see page 8). For each intensity value, we check whether the current point of the Mandelbrot sequence exceeds the number 2. If it exceeds, then we interrupt the cycle and return the current intensity (p. 6-7).
If the module does not reach and does not exceed 2 of the first 255 members of the sequence calculated, then we assume that the starting point belongs to the set and return zero intensity (p. 10), which corresponds to black.
Mandelbrot set image construction: main () function
The main function of our program, directly creating an image of the Mandelbrot set, looks like this:
Create an image (p. 3). We iterate over all its pixels in two for loops (see pages 4, 5). For each pixel, we calculate the coordinates of a point on the complex plane to which it corresponds (p. 7, 8). We form a complex number from the coordinates of the point (p. 9). We pass this number to the get_gray_color () function and get the "color" of the current pixel (p. 10). If the “color” of a pixel is different from white, then paint over the pixel with that color (p. 11-12) (initially the canvas for painting is white, so there is no need to color its pixels in white).
We write the image to the file "out.bmp" (p. 14) and delete the image (p. 15).
Colorize the image of the Mandelbrot set
In the same book of Sedgwick and other authors, the following task is formulated: to modernize the program for constructing the image of the Mandelbrot set in such a way as to make it “color”. To do this, it is proposed to colorize the image not with 256 shades of gray, but with 256 arbitrary colors (among which, of course, there may be shades of gray). Let's solve this problem.
We will act as follows. Passing the complex number to the get_gray_color () function, we will now consider the gray color returned by the function as the color number from some predefined list of colors. It is with this color that we will colorize the pixel corresponding to this complex number.
Obviously, changing the get_gray_color () function is not required. But the main () function needs to be redone. Here is her new, color version:
The list of predefined colors discussed above is formed as an array of colors in lines 3-11. The principle of formation is quite simple: 8 shades of red and green, as well as 4 shades of blue are selected. Further, these shades are mixed, resulting in 256 colors, with which the colors array is filled with three nested loops (see page 7-11). The intensities of each of the three colors are approximately evenly distributed over the spectrum of intensities of a given color (see p. 3-5).
Now, the value returned by the get_gray_color () function is interpreted as the index of the element of the colors array containing the color that the current pixel needs to be colored (see p. 19-21). Note that the values 0 and 1 returned by the function, as in the previous ("black and white") case, correspond to the black and white colors of the pixel, respectively.
As a result of the new version of the program, we get the following image:
Color image of the Mandelbrot set
Clearly, there are so many ways to color Mandelbrot sets. To get some of them, you can, for example, change the order of expressions inside curly brackets that are responsible for the values of the fields of the elements of the colors array (see page 11). There are obviously 6 options for locating expressions:
Replacing the 11th line of the main () function with one of the above lines (with the exception of the 1st), we get 5 more coloring options. Images of the Mandelbrot set, painted in all 6 ways, corresponding to the 6th lines above, are depicted below.
6 images of the Mandelbrot set (click to enlarge)
I probably liked the 2nd image the most. Let's, by the way, to consider it more carefully, increase the resolution by about 2 times. To do this, change the values of some macros:
As the 11th line (see the main () function code) we will use the following:
After starting and compiling the program, we get an image that can be viewed via the link (opens in a new window, the source file is converted to the JPG format, the size of the JPG file is 475 KB). The same image can be obtained by clicking on the picture below, representing a reduced version of it.
Another image of the Mandelbrot set (click to enlarge)
And the last one. From the coloring algorithm of the Mandelbrot set, it follows that only pixels corresponding to points of the complex plane that are no more than 2 from the origin, i.e., lying inside a circle of radius 2 centered at the origin or at its border, are exposed to coloring. Let's take a full look at this circle. To do this, change the values of the macros defined in the main.c file as follows:
After starting and compiling the program, we get an image, a smaller version of which is given below (the original 237 KB image, converted to JPG format, can be obtained by clicking on the picture or the link that opens in a new window).
A lot of Mandelbrot bird's-eye view (click to enlarge)
So, we have created programs that allow you to build "black and white" and "color" images of the Mandelbrot set. Note that the goal was to write code that was most effective in terms of speed. The programs described in the article, and so are executed in a fairly short period of time: in a split second.