Mandelbrot Set

This posting is about one of my first BASIC programs that I wrote on my Amstrad CPC464 in 1985. I must confess that I hadn’t actually ‘written’ the program. It was a so-called type-in. Although I was far from understanding the underlying math the program was worth typing the skin off my fingers to get it working.

The program was able to calculate the following fractal picture. A fractal is a self-similar pattern that, as you zoom in deeper and deeper, will reveal the same shapes and structures over and over again.

Mandelbrot Set

Fractals often appear in nature. A really delicious form fractal you probably know is “Romanesco” broccoli.

Today, I know that the related mathematical principle is nothing to worry about. It is quite easy, provided you do know what complex numbers are. I have used this programming project with high-school kids (twelfth grade) and they all managed to understand the principle. What nobody really understands, however, is why there are such things like fractals and what role they play in our universe …

Without any doubt fractals are thrilling programming projects. Here I’m going to explain the algorithm for the popular Mandelbrot set as shown in the picture above. You will find it amazing how simple it is.

1. Create a Cartesian coordinate plane. Both the x-axis and the y-axis are ranging from -2 to 2. Now imagine that any point within the coordinate system represents a complex number. The x value represents the real part of the number, whereas the y value represents the imaginary part of the number.

2. Iterate the formula

for each point within the coordinate plane until the absolute value of z is larger than 2. The number of iterations will directly yield the color of the point in question. In case the number of iterations exceeds the number of available colors, just draw a black pixel or whatever background color you want to use.

Here are some hints how to handle the real part and the imaginary part of the numbers separately:

That’s it.

Here is a thoroughly documented Java implementation which I tried to keep as short and as basic as possible (no swing, no separate threads).

import java.applet.Applet;
import java.awt.event.*;
import java.awt.*;

/**
 * Simple Mandelbrot Applet
 *
 * Note: I tried to keep this program as simple as possible. Thus, 
 *       the applet isn't using different threads. If you want to 
 *       increase runtime efficiency, you probably want to have the 
 *       calculation running in a separate thread.
 *
 * @author Andre M. Maier
 * @version 1.0
 */
public class Fract extends Applet implements MouseListener {

   // The Mandelbrot fractal is defined for complex numbers with
   // -2 < real(z) < 2 and 2 < imag(z) < 2. In the picture the 
   // x-axis represents the real part of the number, whereas the 
   // y-axis represents the imaginary part. The following variables 
   // define the mathematical limits of the picture.
   private final double default_real_min = -2;
   private final double default_real_max = 2;
   private final double default_imag_min = -2;
   private final double default_imag_max = 2;

   // In this applet the number iterations will be represented by 
   // the intensity of red color. Each iteration corresponds to one 
   // step of the color's intensity. In True-Color mode there are 
   // 255 steps available for each of the basic colors (red, green, 
   // blue).
   private final int max_iter = 255;

   // The zoomed window will be 1/4th = 25% of the previous picture 
   // size
   private final int zoom_factor = 4;

   // The actual mathematical limits of the pictures' coordinates 
   // depend on the actual zoom level. So we need some variables to 
   // hold these values.
   private double real_min = default_real_min;
   private double real_max = default_real_max;
   private double imag_min = default_imag_min;
   private double imag_max = default_imag_max;

   // Variables to hold the size of the applet
   private Dimension applet_size;
   private int       xmax, ymax;

   // The value of the following variables will be added and 
   // subtracted from the current position of the mouse pointer. 
   // This allows calculation of the zooming clip's dimensions.
   private int clipping_pixels_x,
               clipping_pixels_y;

   // Variables to hold the x and y boundaries of the clip to be 
   // zoomed
   private int zoom_window_start_x,
               zoom_window_start_y,
               zoom_window_stop_x,
               zoom_window_stop_y;

   /**
    * This method returns the number of iterations that we need to 
    * reach
    *
    * real( p )^2  + imag( p )^2  ~= 4, or we exceed the number of 
    * maximum of iterations allowed
    *
    * with the recursive formulas
    *
    * real( new_p ) = real( p )^2  - imag( p )^2  + real( z )
    *
    * and
    *
    * imag( new_p ) = 2 * ( real( p ) * imag( p ) ) + imag( z )
    *
    * and p starting at 0 + 0i.
    *
    * @param complex_real real part of a complex number
    * @param complex_imag imaginary part of a complex number
    * @returns the number of iterations
    */
   private int iterate( double complex_real, 
                        double complex_imag  ) {

      double real = 0,
             imag = 0;
      double new_real,
             new_imag;
      int    iteration_count = 0;

      while (( real * real + imag * imag < 4 ) &&
             ( iteration_count != max_iter )) {

         new_real = real * real - imag * imag + complex_real;
         new_imag = real * imag + real * imag + complex_imag;

         real = new_real;
         imag = new_imag;

         iteration_count++;

      }

      return( iteration_count );

   }

  /**
   * This method is mandatory for any applet that uses graphical 
   * output. It actually draws the picture.
   *
   * First, the pixel dimensions of the applets need to be mapped 
   * into the mathematical boundaries (real and imaginary) of the 
   * fractal's number space.
   *
   * Then we calculate the number of iterations for each pixel. 
   * After that the pixel is drawn in the color that represents 
   * this number. In case the maximum number of iterations has been
   * reached for a specific pixel, we will draw it in black color.
   */
   public void paint( Graphics g ) {

      double real, imag;
      double step_real, step_imag;
      int    x, y;
      int    iterations;
      int    color;

      // we will start at x = 0, y = 0 (left upper corner), which 
      // is the minimum of real( z ) and the maximum of imag( z )
      imag = imag_max;

      // mapping the pixel steps into mathematical steps for z
      step_real = ( real_max - real_min ) / xmax;
      step_imag = ( imag_max - imag_min ) / ymax;

      // now loop through the entire picture
      for( y = 0; y < ymax; y++ ) {

         real = real_min;

         for( x = 0; x < xmax; x++ ) {

            // calculate number of iterations for the current pixel
            iterations = iterate( real, imag );

            if ( iterations > max_iter ) {

               // draw pixel in black color, if allowed
               // number of iterations has been reached
               color = 0;

            }
            else {

               // let the color value (0 to 255) represent the 
               // number of iterations for this pixel
               color = iterations;

            }

            // set color and draw pixel
            g.setColor( new Color( color, 0, 0 ));
            g.drawLine( x, y, x, y );

            // increasing the (mathematical) real part by one step
            real += step_real;

         }

         // increasing the (mathematical) imaginary part by one step
         imag -= step_imag;

      }
   }

   /**
    * The init() method of an applet is executed when the applet 
    * gets initialized (started by the browser). Hence, we will run 
    * some initiaization code in here ...
    */
   public void init() {

      // setting initial background to white
      this.setBackground( new Color( 255, 255, 255 ));

      // adding the event listener to this applet
      addMouseListener( this );

      // retrieving the applet's size and setting the pixel limits 
      // of the fractal image
      applet_size = this.getSize();
      ymax = applet_size.height;
      xmax = applet_size.width;

      // calculating the clipping size
      // Note: (int) performs a type cast
      clipping_pixels_x = (int) ( xmax / zoom_factor );
      clipping_pixels_y = (int) ( ymax / zoom_factor );

   }

   /**
    * This method gets executed whenever somebody presses the mouse
    * button within the applet.
    */
   public void mousePressed( MouseEvent e ) {

      // So let's determine our position and define our zooming 
      // window
      zoom_window_start_x = e.getX() - clipping_pixels_x;
      zoom_window_start_y = e.getY() - clipping_pixels_y;

      zoom_window_stop_x  = e.getX() + clipping_pixels_x;
      zoom_window_stop_y  = e.getY() + clipping_pixels_y;

   }

   /**
    * Sooner or later the person who pressed the mouse button will
    * release it. We will now use the dimensions of the zooming 
    * window to calculate the new boundaries of the complex number 
    * space z.
    */
   public void mouseReleased( MouseEvent e ) {

      double real1, imag1;
      double real2, imag2;

      // mapping xy pixels for each corner of the zoom window into 
      // the real part and the imaginary part of z
      real1 = real_min + zoom_window_start_x 
                       * ( real_max - real_min ) / xmax;
      imag1 = imag_max - zoom_window_start_y 
                       * ( imag_max - imag_min ) / ymax;

      real2 = real_min + zoom_window_stop_x 
                       * ( real_max - real_min ) / xmax;
      imag2 = imag_max - zoom_window_stop_y 
                       * ( imag_max - imag_min ) / ymax;

      // The following if/else constructs are the remains from a 
      // version where the user could define the dimensions of the 
      // clipping window by dragging the mouse while the button is 
      // pressed.
      //
      // The purpose of this code was to eliminate the direction in 
      // which the zoom window has been opened.
      if ( real1 < real2 ) {
        real_min = real1;
        real_max = real2;
      }
      else {
        real_min = real2;
        real_max = real1;
      }

      if ( imag1 < imag2 ) {
        imag_min = imag1;
        imag_max = imag2;
      }
      else {
        imag_min = imag2;
        imag_max = imag1;
      }

      // In any case, redraw the picture using the new z space that 
      // we have just calculated
      repaint();

   }

   /**
    * This method gets executed whenever the mouse pointer enters 
    * the applet. We will give zooming instructions by writing some
    * text into the status line of the browser running the applet.
    */
   public void mouseEntered( MouseEvent e ) {

      getAppletContext().showStatus( "Click inside the picture!" );

   }

   /**
    * This method gets executed, when the mouse pointer leaves the 
    * applet.
    */
   public void mouseExited( MouseEvent e ) {

      // Let's clean up the status line ...
      getAppletContext().showStatus( "                         " );

   }

   /**
    * Actually we don't need this method, because all the zooming 
    * is already being handled by mousePressed() and 
    * mouseReleased(). As this method needs to be overwritten in 
    * the mouse event handler, we just leave it empty.
    */
   public void mouseClicked( MouseEvent e ) {

   }

}

Now have fun programming. 🙂

— Andre M. Maier

Advertisements

About bitjunkie

Teacher, Lecturer, and BITJUNKIE ...
This entry was posted in Math, Programming Assignments, Uncategorized. Bookmark the permalink.