Use Newton’s method to draw a fractal in C#


Newton's method

This example uses Newton’s method to draw a fractal. The example Use Newton’s method to find the roots of equations in C# explains how to use Newton’s method to find the roots of an equation. In other words, the values x for which F(x) = 0.

If you look at the picture for that example, you’ll see that the method sometimes uses numbers that jump around a bit before settling down to find one of the equation’s roots. In some places, starting points that are very close may lead to different roots. This gives the method a fractal nature that you can use to generate some interesting results. The equation used by the previous example (-x3/3-2x2+5) isn’t very interesting, but you can make some really interesting pictures if you use equations that use complex numbers.

Consider the complex equation F(z) = z4 – 1 for complex numbers z. This equation has four roots (values that make F(z) = 0): 1, -1, i, and -i. For each complex number x + yi in an area, you can use Newton’s method to see to which root the number leads. You can then plot that point with a color that corresponds to the root. For example, if the point leads to the third root, you plot the point with the third color (from some collection of colors).

More generally, the equation F(z) = zN – 1 has N roots. This example uses the equation F(z) = z8 – 1. (The example lets you change the value NumRoots to generate other fractals.)

The program uses the Complex class described by the example Refine the complex number class in C#.

The following code shows how the program calculates F(z) and dFdz(z) for the equation.

// F(x) = x ^ NumRoots - 1.
private Complex F(Complex x)
{
    return (x ^ (Complex)NumRoots) - 1;
}

// dFdx(x) = NumRoots * x ^ (NumRoots - 1).
private Complex dFdx(Complex x)
{
    return NumRoots * (x ^ (Complex)(NumRoots - 1));
}

The following code draws the fractal. For each point in an area, the program uses Newton’s method to find a root of the equation starting with that point as its initial guess. It then looks through a list of the equation’s roots to see which one it found and plots the point with a corresponding color.

// Draw the fractal.
private void DrawFractal(double xmin, double xmax,
    double ymin, double ymax)
{
    // Make sure we have executed Form1_Load.
    if (Roots == null) return;

    // Get the PictureBox's dimensions.
    int wid = picCanvas.ClientSize.Width;
    int hgt = picCanvas.ClientSize.Height;
    if ((wid < 1) || (hgt < 1)) return;

    // Do nothing if neither the PictureBox nor the
    // world coordinates have changed since last time.
    if (Bm != null &&
        (Wxmin == xmin) && (Wxmax == xmax) &&
        (Wymin == ymin) && (Wymax == ymax) &&
        (wid == Bm.Width) && (hgt == Bm.Height))
            return;

    // Save the new world coordinates.
    Wxmin = xmin;
    Wxmax = xmax;
    Wymin = ymin;
    Wymax = ymax;

    // Make a new Bitmap if necessary.
    if ((Bm == null) || (Bm.Width != wid) || (Bm.Height != hgt))
    {
        picCanvas.Image = null;
        if (Bm != null) Bm.Dispose();
        Bm = new Bitmap(wid, hgt);
        Console.WriteLine("Bitmap(" + wid + ", " + hgt + ")");
    }

    // Make a Graphics object to draw on.
    Graphics gr = Graphics.FromImage(Bm);

    // Clear the bitmap.
    gr.Clear(picCanvas.BackColor);
    picCanvas.Image = Bm;
    picCanvas.Invalidate();
    picCanvas.Refresh();
    this.Invalidate();
    this.Refresh();

    // Work until the epsilon squared < this.
    const double cutoff = 0.00000000001;

    // Adjust the coordinate bounds to fit picCanvas.
    AdjustAspect();

    // dx and dy are the changes in the real 
    // and imaginary parts across pixels.
    double dx = (Wxmax - Wxmin) / (wid - 1);
    double dy = (Wymax - Wymin) / (hgt - 1);

    // Calculate the values.
    Complex x0 = new Complex(Wxmin, 0);
    for (int i = 0; i < wid; i++)
    {
        x0.Im = Wymin;
        for (int j = 0; j < hgt; j++)
        {
            Complex x = x0;
            Complex epsilon;
            const int max_iter = 400;
            int iter = 0;
            do
            {
                if (++iter > max_iter) break;
                epsilon = -(F(x) / dFdx(x));
                x += epsilon;
            } while (epsilon.MagnitudeSquared() > cutoff);

            // Set the color.
            int clr = 0;
            if (iter <= max_iter)
            {
                // Find the closest root.
                for (int r = 0; r <= Roots.GetUpperBound(0); r++)
                {
                    if (x.IsCloseTo(Roots[r]))
                    {
                        // Set the pixel's color.
                        clr = r % Colors.Length;
                        break;
                    }
                }
            }
            Bm.SetPixel(i, j, Colors[clr]);

            // Move to the next point.
            x0.Im += dy;
        } // For j
        x0.Re += dx;

        // Let the user know we're not dead.
        if (i % 10 == 0) picCanvas.Refresh();
    } // For i

    // Update the image.
    picCanvas.Refresh();

    Console.WriteLine("(" +
        Wxmin + ", " +
        Wymin + ")-(" +
        Wxmax + ", " +
        Wymax + ")");
}

See the code for additional details.

For more information on Newton’s method, see Eric W. Weisstein’s article Newton’s Method from MathWorld.


Download Example   Follow me on Twitter   RSS feed   Donate




This entry was posted in algorithms, fractals, graphics, mathematics and tagged , , , , , , , , , , . Bookmark the permalink.

One Response to Use Newton’s method to draw a fractal in C#

  1. Pingback: Use Newton's method to draw fractals for new equations in C#C# Helper

Leave a Reply

Your email address will not be published. Required fields are marked *