Tile a PictureBox in C#

[tile]

If you set a form’s BackgroundImageLayout property Tile, then the control fills itself with copies of its background image. Strangely the PictureBox control does not have a corresponding Tile property. This example shows one way you can tile images on a PictureBox.

The example’s PictureBox has Anchor property set so it resizes when the form does. The following form Resize event handler refreshes the PictureBox.

// Refresh the PictureBox.
private void Form1_Resize(object sender, EventArgs e)
{
    picTile.Refresh();
}

The example uses the form’s Resize event instead of the PictureBox control’s event because that event sometimes causes strange behavior.

The following code shows the PictureBox control’s Paint event handler.

// The background image.
private Bitmap BgBitmap = Properties.Resources.Smiley;

// Tile the image.
private void picTile_Paint(object sender, PaintEventArgs e)
{
    int wid = picTile.ClientSize.Width;
    int hgt = picTile.ClientSize.Height;
    for (int y = 0; y < hgt; y += BgBitmap.Height)
    {
        for (int x = 0; x < wid; x += BgBitmap.Width)
        {
            e.Graphics.DrawImage(BgBitmap, x, y);
        }
    }
}

At design time I used the Project < Properties < Resources to create a resource holding an image. The variable BgBitmap holds that image so it’s easier to use.

The Paint event handler gets the control’s current client size. It then makes x and y loop over the PictureBox, increasing by the width and height of the image. The code then draws the image at each x, y position.

If you wanted the program to draw something such as some lines or other shapes on top of the images, it could do so after the two loops.


Download Example   Follow me on Twitter   RSS feed   Donate


Posted in drawing, graphics, image processing | Tagged , , , , , , , , , , , | Leave a comment

Use a symbiote to graphically select hours in C#


[symbiote]

This example modifies the previous example Graphically select hours in C# so it uses a symbiote class. That example shows how to use a PictureBox to let the user select a range of hours. If you want to let the user select more than one range, you could turn this into a custom control. You could place a PictureBox on a UserControl, compile it, and put as many of these as you like on a form.

One drawback to that method is that the new control must be compiled before you can use it or see it in the toolbox. That’s not the end of the world and works pretty well if you’re distributing compiled programs, but I only post source code, never compiled code. If I post a project that contains a non-compiled custom control, when you first load the project any form that uses the control cannot display it. You need to compile the project before you can see it.

An alternative is to make what I call a “symbiote” class. A symbiote is a class that is used to add features to another class. In this case, a SelectHoursSymbiote object adds features to a PictureBox to make it behave like the control used in the previous example. This gives you almost all of the benefits of a compiled custom control but you don’t need to compile it separately. The drawback is that it doesn’t appear in the toolbox. You create the PictureBox control and then attach the symbiote to it at run time.

The SelectHoursSymbiote class contains all of the code used by the previous example to work with the PictureBox control plus a little extra code to manage events and such.

The following code shows how the class declares its HoursScrolled and HoursChanged events.

// Declare events.
public event EventHandler HoursScrolled;
public event EventHandler HoursChanged;

These events tell the main program when the symbiote’s hours change.

The following code shows the class’s StartHour and StopHour properties.

// The selected hours.
private int _StartHour = 0;
private int _StopHour = 0;
public int StartHour
{
    get { return _StartHour; }
    set
    {
        _StartHour = value;
        // Raise the HoursChanged event.
        if (HoursChanged != null) HoursChanged(this, null);
    }
}
public int StopHour
{
    get { return _StopHour; }
    set
    {
        _StopHour = value;
        // Raise the HoursChanged event.
        if (HoursChanged != null) HoursChanged(this, null);
    }
}

These are fairly straightforward properties. You could implement them as public fields (if you’re willing to ignore the purists who say you should never expose fields publicly), but I wanted the code to raise the HoursChanged event when these values changed.

The following code shows the class’s only constructor.

// The PictureBox we manage.
public PictureBox PictureBox;

// Constructor.
public SelectHoursSymbiote(PictureBox pic)
{
    PictureBox = pic;

    // Add event handlers.
    Pic.Paint += pic_Paint;
    Pic.MouseDown += pic_MouseDown;
    Pic.MouseMove += pic_MouseMove;
    Pic.MouseUp += pic_MouseUp;
}

The PictureBox variable holds a reference to the PictureBox to which the symbiote is attached. The constructor saves a reference to the PictureBox.

It then gives the PictureBox event handlers to catch the Paint event and the mouse events it needs to let the user select hours. These event handlers are almost exactly the same as those used by the previous example except they work with the PictureBox control instead of the specific picHours control. See the previous example for information about how the mouse events and the Paint event work.

The only real differences are where the MouseMove and MouseUp event handlers raise events. After it calculates the newly selected hours, the MouseMove event handler uses the following code to raise the symbiote’s HoursScrolled event.

// Raise the HoursScrolled event.
if (HoursScrolled != null) HoursScrolled(this, null);

The MouseUp event handler uses the following code to raise the HoursChanged event.

// Raise the HoursChanged event.
if (HoursChanged != null) HoursChanged(this, null);

The main program uses the following code to attach symbiotes to its PictureBox controls.

// The symbiotes.
private SelectHoursSymbiote Symbiote1, Symbiote2;

private void Form1_Load(object sender, EventArgs e)
{
    this.ResizeRedraw = true;

    // Create the symbiotes.
    Symbiote1 = new SelectHoursSymbiote(picHours1);
    Symbiote1.HoursChanged += pic_HoursChanged;
    Symbiote1.HoursScrolled += pic_HoursChanged;
    Symbiote1.StartHour = 6;
    Symbiote1.StopHour = 14;

    Symbiote2 = new SelectHoursSymbiote(picHours2);
    Symbiote2.HoursChanged += pic_HoursChanged;
    Symbiote2.HoursScrolled += pic_HoursChanged;
    Symbiote2.StartHour = 9;
    Symbiote2.StopHour = 17;
}

The code creates the new symbiotes, passing their constructors the PictureBox controls to which they should be attached. It registers event handlers for the symbiotes’ HoursScrolled and HoursChanged events and gives them initial StartHour and StopHour values.

The following code shows how the program responds when it receives an HoursScrolled or HoursChanged event.

// Show the times in the TextBoxes.
// Show the times in the TextBoxes.
private void pic_HoursChanged(object sender, EventArgs e)
{
    SelectHoursSymbiote symbiote = sender as SelectHoursSymbiote;
    DateTime start_time =
        new DateTime(2000, 1, 1, symbiote.StartHour, 0, 0);
    DateTime stop_time =
        new DateTime(2000, 1, 1, symbiote.StopHour, 0, 0);

    string tip = start_time.ToShortTimeString() +
        " to " +
        stop_time.ToShortTimeString();
    if (tipHour.GetToolTip(symbiote.PictureBox) != tip)
        tipHour.SetToolTip(symbiote.PictureBox, tip);

    if (symbiote == Symbiote1)
    {
        txtStartTime1.Text = start_time.ToShortTimeString();
        txtStopTime1.Text = stop_time.ToShortTimeString();
    }
    else
    {
        txtStartTime2.Text = start_time.ToShortTimeString();
        txtStopTime2.Text = stop_time.ToShortTimeString();
    }
}

This code converts the symbiote’s hours into DateTime objects and then displays them as short times in the appropriate textboxes.

That’s all there is to it. Creating and using symbiote classes is remarkably easy. Usually it only takes a few minutes to convert code inside a form into a symbiote. (Writing it all up in a post takes a lot longer ;-).)


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in controls, graphics, user interface | Tagged , , , , , , , , , , , , | 1 Comment

Graphically select hours in C#


[select hours]

The DateTimePicker control lets you select dates and date ranges, but there’s no standard control that lets you select hours. This example shows one way to do this with a PictureBox.

A big part of this program is the DrawHours method shown in the following code. It draws the selected hours.

// The selected hours.
private int StartHour = 6;
private int StopHour = 18;

// Draw the hour indicator on this PictureBox.
private void DrawHours(PictureBox pic, Graphics gr,
    int start_hour, int stop_hour)
{
    gr.Clear(Color.LightGreen);

    // Scale to fit a 24-hour period.
    const int margin = 3;
    float scale_x = XScale(pic);
    float hgt = pic.ClientSize.Height;
    float y1 = margin;
    float y2 = hgt - margin;

    // Draw the selected time range.
    RectangleF hours_rect =
        new RectangleF(
            start_hour * scale_x, y1,
            (stop_hour - start_hour) * scale_x, y2 - y1);
    gr.FillRectangle(Brushes.Blue, hours_rect);

    // Draw tick marks.
    float x = 0;
    for (int i = 0; i <= 24; i++)
    {
        gr.DrawLine(thin_pen, x, 0, x, hgt);
        x += scale_x;
    }

    // Draw times.
    gr.RotateTransform(-90);
    int xmid = -pic.ClientSize.Height / 2;
    using (Font font = new Font(FontFamily.GenericSansSerif, 12))
    {
        using (StringFormat sf = new StringFormat())
        {
            sf.Alignment = StringAlignment.Center;
            sf.LineAlignment = StringAlignment.Center;

            x = 0;
            for (int i = 0; i <= 24; i++)
            {
                gr.DrawString(HourToString(i), font,
                    Brushes.Black, xmid, x, sf);
                x += scale_x;
            }
        }
    }
}

This method clears the PictureBox with light green. It then calculates a horizontal scale factor scale_x to use when drawing and uses it to fill a rectangle representing the selected hours in blue. Next the code loops over 25 hours (0 through 24) adding tick marks to show where the hours are in the drawing.

The method then adds a -90 degree rotation (90 degrees counter-clockwise) to the Graphics object to rotate future drawing. It finishes by looping through the hours again to draw each hour’s name. It uses the following HourToString method to convert an hour number into its name.

// Return the hour formatted as we want to display it.
private string HourToString(int hour)
{
    if (hour == 0) return "midnight";
    if (hour == 12) return "noon";
    if (hour == 24) return "midnight";
    if (hour <= 12) return hour.ToString() + "am";
    return (hour - 12).ToString() + "pm";
}

The HourToString method simply returns a string appropriate for an hour number.

The following code shows the XScale method that the program uses to calculate a horizontal scale factor.

// Get the horizontal scale factor.
private float XScale(PictureBox pic)
{
    return pic.ClientSize.Width / 24;
}

The scale factor is just the width of the PictureBox control's client area divided by the number of hours the program draws.

The rest of the interesting code handles the mouse events that let the user select hours. The following MouseDown event handler starts the process.

// Handle mouse events.
private bool Drawing = false;
private int DrawingStartHour, DrawingStopHour;
private void picHours_MouseDown(object sender, MouseEventArgs e)
{
    Drawing = true;
    DrawingStartHour = (int)Math.Round(e.X / XScale(picHours));
    DrawingStopHour = DrawingStartHour;
    StartHour = DrawingStartHour;
    StopHour = DrawingStartHour;
    picHours.Refresh();
}

The event handler sets Drawing = true to indicate that the user has pressed the mouse. It divides the mouse's X position by the horizontal scale factor to see what hour is being selected, rounding to the nearest hour. The event handler saves the hour in the variables DrawingStartHour, DrawingStopHour, StartHour, and StopHour, and refreshes the PictureBox to make it redraw.

The following code shows the MouseMove event handler.

private void picHours_MouseMove(object sender, MouseEventArgs e)
{
    if (!Drawing) return;

    // Calculate the value and display a tooltip.
    int hour = (int)Math.Round(e.X / XScale(picHours));
    string new_tip = HourToString(hour);
    if (tipHour.GetToolTip(picHours) != new_tip)
        tipHour.SetToolTip(picHours, new_tip);

    // Save the new value.
    DrawingStopHour = hour;

    // Redraw.
    if (DrawingStartHour < DrawingStopHour)
    {
        StopHour = DrawingStopHour;
        StartHour = DrawingStartHour;
    }
    else
    {
        StartHour = DrawingStopHour;
        StopHour = DrawingStartHour;
    }
    picHours.Refresh();
}

This code gets the hour under the mouse the same way the MouseDown event handler does. It calls HourToString to get the hour's name and compares it to the PictureBox control's current tooltip. If the name is different from the current tooltip, the code sets the tooltip to the new hour name. (You could remove this if the tooltip annoys you. I'm on the fence on this one.)

Next, the code saves the hour in DrawingStopHour. It then sets StartHour and StopHour so StartHour <= StopHour. (If you don't do this, the DrawHours method earlier doesn't correctly draw the selected hours because it tries to draw a RectangleF with a negative width and the Graphics object won't do that.)

Finally, the method refreshes the PictureBox to make it redraw.

The last interesting piece of code is the following MouseUp event handler.

private void picHours_MouseUp(object sender, MouseEventArgs e)
{
    if (!Drawing) return;
    tipHour.SetToolTip(picHours, "");
    Drawing = false;
    DisplayTimes();
}

This event handler simply clears the PictureBox control's tooltip and calls the following DisplayTimes method to display the selected time range in textboxes.

// Show the times in the TextBoxes.
private void DisplayTimes()
{
    DateTime start_time = new DateTime(2000, 1, 1, StartHour, 0, 0);
    DateTime stop_time = new DateTime(2000, 1, 1, StopHour, 0, 0);
    txtStartTime.Text = start_time.ToShortTimeString();
    txtStopTime.Text = stop_time.ToShortTimeString();
}

This method converts the selected times into DateTime values and then uses their ToShortTimeString method to produce a nicely formatted output.

There are lots of interesting modifications you could make to this code. For example, you could allow the user to select times in half hour or quarter hour increments. Or you could draw different selected hours in different colors to show overtime or normal business hours. (I may add some of those in a later example.)


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in controls, graphics, user interface | Tagged , , , , , , , , , , , | 1 Comment

Remove unnecessary using directives in C#


[using directives]

The top of a C# code file usually includes series of using directives to tell Visual Studio which namespaces are used by the code. When you first create a project, the code files include lots of using directives that might be helpful, but what if you don’t use those namespaces?

This post’s picture shows the code in a new Windows Form created in Visual Studio 2017. It includes using directives for these namespaces:

  • System
  • System.Collections.Generic
  • System.ComponentModel
  • System.Data
  • System.Drawing
  • System.Linq
  • System.Text
  • System.Threading.Tasks
  • System.Windows.Forms

The last of these, System.Windows.Forms, is necessary. Depending on what the program does, the others may not be.

So does leaving unnecessary using directives in a program hurt you? Yes and no.

When you compile the application, only the libraries that are actually used are included in the compiled result. That means leaving extra using directives in the code doesn’t make the final result any larger or slower.

However, when you build the application, the compiler must resolve all of the symbols in the code. If the compiler encounters a symbol such as Pen, it first tries to find a definition for Pen in the local code. If it doesn’t find one, it starts looking through the namespaces included by using directives. If those directives include a lot of namespaces that the program doesn’t actually use, the compiler may be digging through a lot of material that couldn’t possibly help, and that may slow things down a bit.

So removing unnecessary using directives can reduce compilation time. In Visual Studio 2017, using directives that are not needed are grayed out, as you can see in the picture at the top of the post. In older versions of Visual Studio, you can comment out the directives one at a time and see which ones cause errors.

An easier method is to let the code editor remove unnecessary usings for you. In Visual Studio 2017, right-click in the code editor and select Remove and Sort Usings. In older versions of Visual Studio, right-click and dig around to find the right menu item.


Follow me on Twitter   RSS feed   Donate




Posted in coding, performance | Tagged , , , , , , , , , | Leave a comment

Draw the Weierstrass function in C#

[Weierstrass function]

The Weierstrass function was discovered by Karl Weierstrass in 1872. It’s an odd function that is continuous everywhere but differentiable nowhere. I’ll explain what that means shortly. Here’s the function:

[Weierstrass function]

Here:

[Weierstrass function]

The following two sections explain what it means to be continuous and differentiable. The section after those explains the example program.

Continuous

Intuitively, a function is continuous if there are no breaks or jumps in its values. More technically, a function is continuous at a point (x, F(x)) if a small change in the x value leads to an arbitrarily small change in Y value.

[Weierstrass function]

To think of this in another way, suppose you pick a small change in Y value dy. Then I can find a small enough value dx such that |F(x – dx) – F(x + dx)| < dy. In other words, I can find a small enough region around the point (x, F(x)) so the function varies by no more than your desired amount dy.

Most of the “normal” functions that you’re used to dealing with are continuous. An example of a function that is not continuous is y = 1/x, which is graphed on the right. This function is discontinuous at x = 0 because its value jumps from minus infinity to plus infinity at that point.

Because the Weierstrass function is continuous everywhere, that means if you zoom in closely enough on any point, the function’s values are limited. They don’t tend towards infinity and they don’t jump from one value to another.

Differentiable

Intuitively, a function is differentiable at a point if it varies smoothly there. Another way to think about it is that, if you zoom in closely enough on the point, the function is approximately linear.

More technically, a function is differentiable at a point if it has a derivative at that point.

[Weierstrass function]

Functions like lines, parabolas, and other polynomial functions are continuous. The function y = |x|, which is graphed on the right, is not differentiable at the point x = 0 because its slope is undefined at x = 0.

Note that a function that is differentiable at point x must also be continuous there, but as the Weierstrass function shows, the converse is not true.

The Weierstrass function is weird because it is everywhere continuous but nowhere differentiable. Basically, the function is infinitely spiky. If you zoom in on part of the curve, you’ll find spikes that were too small to notice at the zoomed-out scale.

The function is also fractal. If you zoom in, you’ll find a similar zigzaggy up and down structure superimposed with smaller zigzags.

The Example

The example program is fairly simple. The following code calculates the Weierstrass function.

// Return a value of the Weierstrass function.
private float F(float x, float A, float B)
{
    const int iterations = 100;
    double total = 0;
    for (int n = 0; n < iterations; n++)
    {
        double cos = Math.Cos(Math.Pow(B, n) * Math.PI * x);
        if (cos > 1) cos = 0;
        else if (cos < -1) cos = 0;

        total += Math.Pow(A, n) * cos;
    }
    return (float)total;
}

In theory, the cosine function should give values between 1 and -1. Unfortunately if its input is too big, the function has some sort of overflow error and returns a nonsensical result. The code protects itself against that by checking for values smaller than -1 and larger than 1, and setting the cosine to 0 in those cases.

The cosine is multiplied by a to the nth power. Because 0 < a < 1, that value becomes smaller as n grows larger. For example, if a = 0.9, Math.Pow(a, 100) is around 0.000027, so that term adds little to the total. Because terms with larger values of n don't contribute much to the total, the program saves time by only adding up the first 100 terms. (This works as long as a isn't too big. If a is 0.999, you should probably use more terms.) The following code draws the function's graph.

// Draw the graph.
private void DrawGraph()
{
    const float wxmin = -2;
    const float wxmax = 2;
    const float wymin = -2;
    const float wymax = 2;

    int wid = picGraph.ClientSize.Width;
    int hgt = picGraph.ClientSize.Height;
    Bitmap bm = new Bitmap(wid, hgt);
    using (Graphics gr = Graphics.FromImage(bm))
    {
        gr.SmoothingMode = SmoothingMode.AntiAlias;

        RectangleF rect = new RectangleF(
            wxmin, wymin, (wxmax - wxmin), (wymax - wymin));
        PointF[] points =
        {
            new PointF(0, hgt),
            new PointF(wid, hgt),
            new PointF(0, 0),
        };
        gr.Transform = new Matrix(rect, points);
        Matrix inverse = gr.Transform;
        inverse.Invert();

        // Draw the axes.
        using (Pen pen = new Pen(Color.Red, 0))
        {
            gr.DrawLine(pen, wxmin, 0, wxmax, 0);
            gr.DrawLine(pen, 0, wymin, 0, wymax);
        }

        // Plot the function.
        // Convert X coordinates for each pixel into world coordinates.
        PointF[] values = new PointF[wid];
        for (int i = 0; i < wid; i++) values[i].X = i;
        inverse.TransformPoints(values);

        // Generate Y values.
        for (int i = 0; i < wid; i++)
            values[i].Y = F(values[i].X, A, B);

        // Plot.
        using (Pen pen = new Pen(Color.Black, 0))
        {
            gr.DrawLines(pen, values);
        }
    }

    picGraph.Image = bm;
}

The code first defines the X and Y values within which it will draw the graph. It then defines a transformation to map those coordinate bounds onto the program’s PictureBox.

The code then draws the X and Y axes. It makes an array holding X values for each of the pixels in the PictureBox, and then uses the inverse transformation matrix to map those points into world coordinates. The code uses the function to fill in the corresponding Y values, and then draws the curve that they define.

Download the example to see additional details.


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in algorithms, drawing, fractals, graphics, mathematics | Tagged , , , , , , , , , , , , , , , | Leave a comment

Determine whether a file or directory exists in C#

[file]

It’s usually more efficient to check whether a file or directory exists before you try to access it. For example, if you try to read a file that doesn’t exist, the system needs to create error handling objects and a stack trace, and that takes extra time.

When the program starts, it uses the following code to initialize its TextBox controls.

private void Form1_Load(object sender, EventArgs e)
{
    txtDirectory.Text = Application.StartupPath;
    txtDirectory.Select(txtDirectory.Text.Length, 0);

    txtFile.Text = Application.ExecutablePath;
    txtFile.Select(txtFile.Text.Length, 0);
}

This code displays the startup directory in the Directory TextBox and the executable program’s name in the File TextBox. When you click the buttons, the following event handlers execute.

private void btnDirectoryExists_Click(object sender, EventArgs e)
{
    if (Directory.Exists(txtDirectory.Text))
        txtDirectoryResult.Text = "Yes";
    else txtDirectoryResult.Text = "No";
}

private void btnFileExists_Click(object sender, EventArgs e)
{
    if (File.Exists(txtFile.Text))
        txtFileResult.Text = "Yes";
    else txtFileResult.Text = "No";
}

These event handlers just use the System.IO.Directory.Exists and System.IO.File.Exists methods to see if the directory and file exist. A simple but useful technique.


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in files | Tagged , , , , , , , | Leave a comment

Calculate Fibonacci numbers in several ways in C#

[Fibonacci]

For some background on Fibonacci numbers and φ, see Examine the relationship between the Fibonacci sequence and phi in C#.

This example shows several ways to calculate Fibonacci numbers. While this is mostly for curiosity’s sake, this example does demonstrate a couple of important lessons here about recursion and look-up tables.

Recall the recursive definition of the Fibonacci numbers:

Fibonacci(0) = 0
Fibonacci(1) = 1
Fibonacci(n) = Fibonacci(n - 1) + Fibonacci(n - 2)

This recursive definition leads naturally to the following recursive algorithm for calculating Fibonacci numbers.

// Recursive.
private double Fibonacci1(int n)
{
    if (n <= 1) return n;
    return Fibonacci1(n - 1) + Fibonacci1(n - 2);
}

This method is simple. Unfortunately it’s also very slow. For example, to calculate Fibonacci(40) the program must calculate Fibonacci(39) and Fibonacci(38). But to calculate Fibonacci(39) the program must calculate Fibonacci(38) and Fibonacci(37). Here Fibonacci(38) is being calculated twice. As the recursion continues, the same Fibonacci values must be calculated again and again a huge number of times making the program take a very long time.

The following method solves the problem of recalculating values by storing the intermediate values it creates in a look-up table for later use.

// With look-up values.
private double Fibonacci2(int n)
{
    if (n <= 1) return n;

    // Create the look-up table.
    double[] fibo = new double[n + 1];
    return Fibonacci2(fibo, n);
}
private double Fibonacci2(double[] fibo, int n)
{
    if (n <= 1) return n;

    // If we have already calculated this value, return it.
    if (fibo[n] > 0) return fibo[n];

    // Calculate the result.
    double result =
        Fibonacci2(fibo, n - 1) +
        Fibonacci2(fibo, n - 2);

    // Save the value in the table.
    fibo[n] = result;

    // Return the result.
    return result;
}

The first overloaded version of this method makes a look-up table big enough to hold the Fibonacci numbers 0 through n. It then calls the second overloaded version to do all the work, passing it the look-up table and n.

The second version of Fibonacci2 looks in the look-up table to see if we have already calculated the n-th Fibonacci number and returns it if we have. This prevents the method from calculating the same values more than once and saves a huge amount of time.

If we have not yet calculated the n-th Fibonacci number, the method calls itself recursively as before, saves the value it calculates in the look-up table, and returns the result it calculated.

This technique of caching values can be extremely powerful. It can let you avoid a lot of work even if you don’t really know when you’ll need the values later. (I worked on a project once where some performance analysis showed that a lot of time was spent calculating the same values repeatedly. I added a look-up table and improved performance greatly.)

This method is a great improvement on the previous version but there’s still room for improvement. Both of the previous methods generate Fibonacci numbers in a top-down way, but the recursive definition of the Fibonacci numbers is really bottom-up. The definition starts with Fibonacci(0) and Fibonacci(1) and works up from there.

The following method uses a bottom-up approach to build Fibonacci numbers without recursion.

// Iterate holding the two previous values.
private double Fibonacci3(int n)
{
    if (n <= 1) return n;

    double minus2 = 0;
    double minus1 = 1;
    double fibo = minus1 + minus2;
    for (int i = 3; i <= n; i++)
    {
        minus2 = minus1;
        minus1 = fibo;
        fibo = minus1 + minus2;
    }
    return fibo;
}

The method creates variables minus2, minus1, and fibo. When fibo holds Fibonacci(n), minus2 holds Fibonacci(n – 2) and minus1 holds Fibonacci(n – 1).

Initially minus2 = Fibonacci(0), minus1 = Fibonacci(1), and fibo = Fibonacci(2).

The method then enters a for loop. During each trip through the loop, the code moves minus2 up to the current value of minus1, moves minus1 up to the current value of fibo, and calculates the next value for fibo. When the loop finishes, fibo holds Fibonacci(n).

This method doesn’t use recursion and doesn’t need a look-up table so it’s even faster than the previous method (and uses less memory), but even it can be improved. The French mathematician Abraham de Moivre discovered the following equation.

Fibonacci(n) = (φ1n - φ2n) / Sqrt(5)

Here φ1 and φ2 are the two roots to the equation for the golden ratio. (See the earlier post.)

φ1 = (1 + Math.Sqrt(5)) / 2
φ2 = (1 - Math.Sqrt(5)) / 2

The following method uses de Moivre’s formula to calculate Fibonacci numbers directly.

// Use Abraham de Moivre's formula.
private double Fibonacci4(int n)
{
    double phi1 = (1 + Math.Sqrt(5)) / 2.0;
    double phi2 = (1 - Math.Sqrt(5)) / 2.0;
    return (Math.Pow(phi1, n) - Math.Pow(phi2, n)) / Math.Sqrt(5);
}

Even this can be simplified (but I promise this is the last one). Because the absolute value of φ2 is less than 1 (it’s roughly -0.62), φ2n is small for all n so you can drop that term and round the remaining result to the nearest integer.

// Ignore phi2.
private double Fibonacci5(int n)
{
    double phi1 = (1 + Math.Sqrt(5)) / 2.0;
    return Math.Truncate(Math.Pow(phi1, n) / Math.Sqrt(5));
}

The lessons to learn are:

  • Whenever you have recursion, be aware of whether you are calculating the same value many times.
  • Whether you have recursion or not, if the program is recalculating the same values many times, you may be able to speed things up by creating a look-up table so you only need to calculate each value once.
  • If a recursive relationship is defined in a bottom-up way, you may be able to create an iterative solution that also works in a bottom-up way.
  • The formula discovered by de Moivre is specific to Fibonacci numbers, so you probably won’t be able to use it unless you are calculating Fibonacci numbers, but the final method used by this example actually holds a lesson that is more general. If you’re calculating a numeric result and part of the result quickly becomes very small, you may be able to ignore it. In particular, if you’re calculating an integer result, you may be able to ignore parts of the equation that contribute only a small amount to the result.


    Download Example   Follow me on Twitter   RSS feed   Donate




Posted in algorithms, mathematics | Tagged , , , , , , , , , , | Leave a comment

“The C# Helper Top 100” now available at Barnes & Noble

My latest book, The C# Helper Top 100, is now available on Amazon here. (As was the case with Amazon, I need to contact them to update the book’s description.)

Posted in Uncategorized | Leave a comment

Recursively draw equations in C#

[equations]

The basic idea for recursively drawing equations is simple. Well, sort of simple.

Classes represent different kinds of equations. A particular class knows how to draw its kind of equation. It uses other classes to draw its pieces.

For example, the FractionEquation class draws a horizontal line with a numerator on top and a denominator on the bottom. It uses other objects to draw the numerator and denominator.

The following abstract Equation base class defines three methods: SetFontSizes, GetSize, and Draw.

abstract class Equation
{
    // The font size used by this equation.
    public float FontSize = 20;

    // Set font sizes for sub-equations.
    public abstract void SetFontSizes(float font_size);

    // Return the equation's size.
    public abstract SizeF GetSize(Graphics gr, Font font);

    // Draw the equation.
    public abstract void Draw(Graphics gr, Font font,
        Pen pen, Brush brush, float x, float y);
}

The SetFontSizes method sets the equation’s FontSize value. If the equation is made up of sub-equations, as most of the equation classes are, this method calls the sub-equations’ SetFontSizes methods passing them scaled font sizes.

The GetSize method calculates the equation’s size. If the equation includes sub-equations, it calls their GetSize methods to get their sizes and then uses them to calculate this equation’s size.

The Draw method draws the equation. If the equation includes sub-equations, it calls their Draw methods to draw them.

Subclasses of Equation implement these methods according to how they draw their particular kind of equation. The example program defines these classes:

StringEquation Draws a string. This is the end of the chain of recursion.
BarEquation Draws vertical elements to the left and right of its contents. The elements can be bars, brackets, braces, pointy brackets, parentheses, or omitted.
FractionEquation Draws an equation above another with an optional horizontal line in between.
IntegralEquation Draws an integral symbol with equations specifying the value inside the integral and the values above and below the symbol.
MatrixEquation Draws equations in an array, optionally making all rows or columns the same size.
PowerEquation Draws an equation to the power of another equation.
RootEquation Draws a root with equations for the index and radicand.
SigmaEquation Draws a sigma summation with equations specifying the value inside the summation and the values above and below the sigma.

The StringEquation class shown in the following code is the most basic. It simply draws a string.

// Draw some text.
class StringEquation : Equation
{
    // The text to draw.
    private string Text;

    // Initialize the text.
    public StringEquation(string text)
    {
        Text = text;
    }

    // Set font sizes for sub-equations.
    public override void SetFontSizes(float font_size)
    {
        FontSize = font_size;
    }

    // Return the equation's size.
    public override SizeF GetSize(Graphics gr, Font font)
    {
        using (Font new_font = new Font(font.FontFamily,
            FontSize, font.Style))
        {
            return gr.MeasureString(Text, new_font);
        }
    }

    // Draw the equation.
    public override void Draw(Graphics gr, Font font,
        Pen pen, Brush brush, float x, float y)
    {
        using (Font new_font = new Font(font.FontFamily,
            FontSize, font.Style))
        {
            gr.DrawString(Text, new_font, brush, x, y);
        }
    }
}

This class provides some constructors. Its SetFontSizes method simply saves the font size. The GetSize method creates a font of the correct size and then measures the object’s string using that font. The Draw method creates a font of the correct size and then draws the string.

The following code shows a less trivial example: the FractionEquation class.

// Draw one item over another.
class FractionEquation : Equation
{
    // True to draw a separator line.
    public bool DrawSeparator;

    // The space between the top and bottom items.
    private const float Gap = 0;

    // Extra width for the separator (on each side).
    private const float ExtraWidth = 6;

    // The items to draw.
    private Equation Numerator, Denominator;

    // Initialize a new object.
    public FractionEquation(Equation top_item,
        Equation bottom_item, bool draw_separator)
    {
        Numerator = top_item;
        Denominator = bottom_item;
        DrawSeparator = draw_separator;
    }

    // Initialize a new object.
    public FractionEquation(string top_string,
        string bottom_string, bool draw_separator)
        : this(new StringEquation(top_string),
            new StringEquation(bottom_string), draw_separator)
    {
    }

    // Set font sizes for sub-equations.
    public override void SetFontSizes(float font_size)
    {
        FontSize = font_size;
        Numerator.SetFontSizes(font_size * 0.75f);
        Denominator.SetFontSizes(font_size * 0.75f);
    }

    // Return the object's size.
    public override SizeF GetSize(Graphics gr, Font font)
    {
        // Get the sizes of the items.
        SizeF top_size, bottom_size;
        float width, height;
        GetSizes(gr, font, out top_size, out bottom_size,
            out width, out height);

        // Calculate our size.
        return new SizeF(width, height);
    }

    // Draw the equation.
    public override void Draw(Graphics gr, Font font,
        Pen pen, Brush brush, float x, float y)
    {
        // Get the sizes of the items.
        SizeF top_size, bottom_size;
        float width, height;
        GetSizes(gr, font, out top_size, out bottom_size,
            out width, out height);

        // Draw the separator.
        if (DrawSeparator)
        {
            float separator_y = y + top_size.Height + Gap / 2;
            gr.DrawLine(pen,
                x, separator_y,
                x + width, separator_y);
        }

        // Draw the top.
        float top_x = x + (width - top_size.Width) / 2;
        Numerator.Draw(gr, font, pen, brush, top_x, y);

        // Draw the bottom.
        float bottom_x = x + (width - bottom_size.Width) / 2;
        float bottom_y = y + top_size.Height + Gap;
        Denominator.Draw(gr, font, pen, brush, bottom_x, bottom_y);
    }

    // Return various sizes.
    private void GetSizes(Graphics gr, Font font, out SizeF top_size,
        out SizeF bottom_size, out float width, out float height)
    {
        top_size = Numerator.GetSize(gr, font);
        bottom_size = Denominator.GetSize(gr, font);
        width = Math.Max(top_size.Width, bottom_size.Width) +
            2 * ExtraWidth;
        height = top_size.Height + bottom_size.Height + Gap;
    }
}

This class begins with some parameters that help determine how it draws a fraction. Its constructors initialize those settings.

The class’s Numerator and Denominator values hold Equation subclasses that should be drawn for the top and bottom of the fraction.

The SetFontSizes method saves the font size and then calls its sub-equations’ SetFontSizes methods passing them the font size scaled by 0.75. That makes the font used by the sub-equations slightly smaller and produces a nicer result. (This is even more important for some of the other equation types such as IntegralEquation and SigmaEquation where the results look really weird if the integral or summation’s limit equations are not in a smaller font.)

The GetSize method calls GetSizes to calculate the sizes of the Numerator and Denominator. It then uses those sizes to calculate the whole FractionEquation object’s size.

The Draw method also calls GetSizes to get the sizes of the Numerator and Denominator. It then draws the fraction. It calls the Numerator object’s and the Denominator object’s Draw methods to make them draw themselves.

The GetSizes method calls the Numerator object’s and Denominator object’s GetSize methods to get their sizes. It then adds some room for the line between the two and returns the combined fraction’s size.

The other equation subclasses work similarly. In each subclass:

  • The SetFontSizes method calls the sub-equations’ SetFontSizes methods, possibly passing them a scaled down font size.
  • The GetSize method calls sub-equations’ GetSize methods and then uses the geometry of the particular subclass to decide how those sizes combine to make the whole equation’s size.
  • The Draw method calls sub-equations’ Draw methods and adds other symbols needed by this equation such as integral signs, brackets, or root symbols.

The subclasses are somewhat involved, but the basic ideas are simple. The only real differences are in how each draws its sub-equations. Download the example to see additional details.


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in algorithms, drawing, fonts, graphics, recursion | Tagged , , , , , , , , , , , | 2 Comments

“The C# Helper Top 100” now available at Amazon

My latest book, “The C# Helper Top 100,” is now available on Amazon here. I need to contact them to update the book’s description, though.

It usually takes a couple days for books to appear on other vendors. Barnes & Noble should come aboard soon.

Posted in Uncategorized | Leave a comment