Load a picture and manipulate pixels in WPF and C#

[manipulate pixels]

The post Easily manipulate pixels in WPF and C# explains a BitmapPixelMaker class that you can use to manipulate the pixels in an image in WPF relatively easily. That example creates the image from scratch.

This post extends that class so you can initialize the image from a file and then manipulate its pixels. When it starts, the program loads the file Smiley.png and then adjusts its pixels, making some brighter and others darker.

BitmapPixelMaker Constructors

The previous version of the BitmapPixelMaker class provided only one constructor that made an image with a given width and height. To make class more flexible, I have added two new constructors.

The following code shows the revised version of the earlier constructor.

// Constructor. Width and height required.
public BitmapPixelMaker(int width, int height)
{
    InitializeFromDimensions(width, height);
}

// Initialize the object from its width and height.
private void InitializeFromDimensions(int width, int height)
{
    // Save the width and height.
    Width = width;
    Height = height;

    // Create the pixel array.
    Pixels = new byte[width * height * 4];

    // Calculate the stride.
    Stride = width * 4;
}

This constructor simply calls the InitializeFromDimensions method. It saves the width and height, creates an array to hold pixel data, and calculates the Stride value. The previous version of the constructor did all of those things directly. I moved that code into a new method so it would be easier to reuse in the following constructor and its helper method.

// Constructor that loads from a WriteableBitmap.
public BitmapPixelMaker(WriteableBitmap wbitmap)
{
    InitializeFromWbitmap(wbitmap);
}

// Initialize from a WriteableBitmap.
private void InitializeFromWbitmap(WriteableBitmap wbitmap)
{
    // Initialize the basics.
    // Use Convert.ToInt32 to round the dimensions to integers.
    int wid = Convert.ToInt32(wbitmap.Width);
    int hgt = Convert.ToInt32(wbitmap.Height);
    InitializeFromDimensions(wid, hgt);

    // Get the pixels.
    Int32Rect rect = new Int32Rect(0, 0, Width, Height);
    wbitmap.CopyPixels(rect, Pixels, Stride, 0);
}

This constructor takes as a parameter a WriteableBitmap and prepares the BitmapPixelMaker class to work with it. The constructor simply calls the InitializeFromWbitmap method. That method converts the bitmap’s width and height, which are stored in doubles, into integers. It then calls InitializeFromDimensions to prepare the object to work with the bitmap. It finishes by calling the WriteableBitmap object’s CopyPixels method to copy its pixel data into the Pixels array.

The following code shows the new example’s final constructor.

// Constructor that loads from a URI.
public BitmapPixelMaker(Uri uri)
{
    // Load the file into a WriteableBitmap.
    BitmapImage bitmap = new BitmapImage(uri);
    WriteableBitmap wbitmap =
        new WriteableBitmap(bitmap);

    // Initialize the object.
    InitializeFromWbitmap(wbitmap);
}

This constructor takes as a parameter a URI indicating an image file to load. The constructor uses the URI to create a BitmapImage and then uses the result to creates a WriteableBitmap. It finishes by calling the InitializeFromWbitmap to prepare the BitmapPixelMaker object to manipulate pixels in the image.

The Main Program

The new constructors are the most interesting part of the example program. The following code shows how the main program creates the image that it displays.

private void Window_Loaded(object sender, RoutedEventArgs e)
{
    // Make the BitmapPixelMaker.
    Uri uri = new Uri("Smiley.png", UriKind.Relative);
    BitmapPixelMaker bm_maker = new BitmapPixelMaker(uri);

    // Brighten and darken the image's pixels.
    int wid = bm_maker.Width / 4;
    int hgt = bm_maker.Height/ 4;
    int num_c = bm_maker.Width / wid;
    int num_r = bm_maker.Height / hgt;
    for (int row = 0; row < num_r; row++)
    {
        for (int col = 0; col < num_c; col++)
        {
            for (int i = 0; i < wid; i++)
            {
                for (int j = 0; j < hgt; j++)
                {
                    int x = col * wid + j;
                    int y = row * hgt + i;
                    if ((x < bm_maker.Width) && (y < bm_maker.Height))
                    {
                        byte r, g, b, a;
                        bm_maker.GetPixel(x, y, out r, out g, out b, out a);
                        if ((col + row) % 2 == 0)
                        {
                            // Lighten the pixel.
                            r = (byte)(255 - (255 - r) * 0.75);
                            g = (byte)(255 - (255 - g) * 0.75);
                            b = (byte)(255 - (255 - b) * 0.75);
                        }
                        else
                        {
                            // Darken the pixel.
                            r = (byte)(r * 0.75);
                            g = (byte)(g * 0.75);
                            b = (byte)(b * 0.75);
                        }
                        bm_maker.SetPixel(x, y, r, g, b, a);
                    }
                }
            }
        }
    }

    // Convert the pixel data into a WriteableBitmap.
    WriteableBitmap new_wbitmap = bm_maker.MakeBitmap(96, 96);

    // Display the result.
    imgResult.Source = new_wbitmap;
}

The program first creates a Uri object representing the local file Smiley.png. (At design time I added the file to the project and set its Copy To Output Directory property to Copy If Newer so it is copied into the directory where the executable is located if necessary.)

The code then uses the Uri to create a new BitmapPixelMaker.

The rest of the program uses the BitmapPixelMaker to manipulate pixels. It divides the image into four rows and columns and loops through them (in the row and col loops). For each row and column value, the code loops through the pixels in that part of the image (in the i and j loops).

For each pixel, the code gets the pixel’s red, green, blue, and alpha values. Then if the sum of the row and column numbers is even, the program moves the pixel’s red, green, and blue values closer to 255, making the pixel more transparent. If the sum is odd, the program moves the pixel’s red, green, and blue values closer to 0, making the pixel more transparent.

After it has adjusted the pixel’s color components, the code calls the BitmapPixelMaker object’s SetPixel method to save the new values in the object’s Pixels data.

After it has updated all of the pixels, the program calls the maker’s MakeBitmap method to convert the pixel data into a WriteableBitmap. It then displays the result in the program’s Image control.

Conclusion

The new version of the BitmapPixelMaker lets you manipulate pixels for an image that you load from a file. It’s somewhat awkward and non-intuitive, so I still prefer to use Windows Forms when I need to manipulate images, but at least this version makes it possible to manipulate pixels in a WPF application if you need to do so.


Download Example   Follow me on Twitter   RSS feed   Donate




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

Download and graph COVID-19 case data in C#


[COVID-19]

This example shows how to download the most recent COVID-19 data and graph it. It demonstrates the following useful techniques.

  • Downloading a file once per day
  • Reading data from a CSV file
  • Creating country data
  • Using different comparers to sort in multiple ways
  • Drawing the graph
  • Displaying data tooltips

This is just a basic example to get things going. Later examples will try to display different data in various ways to get a better understanding of what’s going on in the world.

(I apologize now that this is a fairly long post. I want to include a lot of the code even though some of it has been presented in previous posts.)

Downloading Data

There are two main issues here. First, how do you download the data. Second, how do you download the data only once per day so you don’t bomb the site providing it.

For this example, I decided to download the data into a file named after today’s date. When the program starts, it looks to see if that file is present. If the file is already there, the program uses it. If the file is missing, the program downloads the data.

The data used by this program is from The Humanitarian Data Exchange (HDX). For information about this particular data set, go to Novel Coronavirus (COVID-19) Cases Data. That data is updated daily, so this program only loads the data once per day.

Depending on your timezone and the time when they update the data, you might download yesterday’s data today. If that happens, you can simply delete the data file and try again later. In a production application, you might want to compare the files to see if the data has changed. Depending on how the server makes the data files available, you might also be able to query the site to get the data’s date and then download it if it has changed.

Anyway, the following LoadData method controls the data loading process.

// Load and prepare the data.
private void LoadData()
{
    // Compose the local data file name.
    string filename = "data" + DateTime.Now.ToString("yyyy_MM_dd") + ".csv";

    // Download today's data.
    DownloadFile(filename);

    // Read the file.
    object[,] fields = LoadCsv(filename);

    // Create the country data.
    CreateCountryData(fields);
}

This method just calls DownloadData, LoadCsv, and CreateCountryData to do all of the work.

The following code shows the DownloadFile method downloads today’s data.

// Download today's data.
private void DownloadFile(string filename)
{
    // See if we have today's file.
    if (!File.Exists(filename))
    {
        // Download the file.
        this.Cursor = Cursors.WaitCursor;
        Application.DoEvents();

        try
        {
            // Make a WebClient.
            WebClient web_client = new WebClient();

            // Download the file.
            const string url = "https://data.humdata.org/...";
            web_client.DownloadFile(url, filename);
        }
        catch (Exception ex)
        {
            MessageBox.Show(ex.Message, "Download Error",
                MessageBoxButtons.OK, MessageBoxIcon.Exclamation);
        }
        finally
        {
            this.Cursor = Cursors.Default;
        }
    }
}

The method takes as a parameter the name of today’s file, which has the format data2020_02_01.csv. It uses File.Exists to see if the file already exists. If the file is missing, the program creates a WebClient and uses its DownloadFile method to download the data. The following shows the full path to the data.

https://data.humdata.org/hxlproxy/api/data-preview.csv?url=https%3A%2F%2Fraw.githubusercontent.com%2FCSSEGISandData%2FCOVID-19%2Fmaster%2Fcsse_covid_19_data%2Fcsse_covid_19_time_series%2Ftime_series_covid19_confirmed_global.csv&filename=time_series_covid19_confirmed_global.csv

The data looks like this:

Province/State,Country/Region,Lat,Long,1/22/20,1/23/20,1/24/20,...
,Afghanistan,33.0,65.0,0,0,0,...
,Albania,41.1533,20.1683,0,0,0,...
,Algeria,28.0339,1.6596,0,0,0,...
...
Anhui,China,31.8257,117.2264,1,9,15,...
Beijing,China,40.1824,116.4142,14,22,36,...
Chongqing,China,30.0572,107.874,6,9,27,...
Fujian,China,26.0789,117.9874,1,5,10,...

The program loops through the first row starting at the fifth column to get the dates.

It then loops through the rows starting at the second row to get the country data. For each row, it reads the country’s name and loops through the columns (starting with the fifth column) to get the numbers of cases.

As it loops through the rows, the program combines entries for the same country. For example, it adds up the values for China and places the result in one object.

Reading CSV Data

Usually it’s not too hard to load a CSV (Comma-Separated Value) file as a string and then parse the string. Unfortunately one value in the file (Korea, South) contain a comma. To indicate that the comma is part of the field and not a delimiter, the file encloses that value in double quotes.

You could modify the program to deal with that, but (a) that would be more work, and (b) it wouldn’t handle any other weird situation that might pop up. To avoid that, I decided to use an Excel server to load the file.

To do that, you need to add a reference to Excel to the program. In Solution Explorer, right-click References and select Add Reference. On the COM tab, add a reference to Microsoft Excel 14.0 Object Library (or whatever version you have).

Now the program can use the following method to load the file into a two-dimensional array.

// Load a CSV file into a 1-based array.
private object[,] LoadCsv(string filename)
{
    // Get the Excel application object.
    Excel.Application excel_app = new Excel.ApplicationClass();

    // Make Excel visible (optional).
    //excel_app.Visible = true;

    // Open the workbook read-only.
    filename = Application.StartupPath + "\\" + filename;
    Excel.Workbook workbook = excel_app.Workbooks.Open(
        filename,
        Type.Missing, true, Type.Missing, Type.Missing,
        Type.Missing, Type.Missing, Type.Missing, Type.Missing,
        Type.Missing, Type.Missing, Type.Missing, Type.Missing,
        Type.Missing, Type.Missing);

    // Get the first worksheet.
    Excel.Worksheet sheet = (Excel.Worksheet)workbook.Sheets[1];

    // Get the used range.
    Excel.Range used_range = sheet.UsedRange;

    // Get the sheet's values.
    object[,] values = (object[,])used_range.Value2;

    // Close the workbook without saving changes.
    workbook.Close(false, Type.Missing, Type.Missing);

    // Close the Excel server.
    excel_app.Quit();

    return values;
}

This method creates an Excel application object. It composes the file’s full path and uses the Excel object’s Workbooks.Open method to open the file.

The code then gets the workbook’s first worksheet. It uses the UsedRange value to get a Range representing the cells in the worksheet that are used. It then calls the range’s Value2 method to return an array containing the values.

Note that Excel starts indexing the array at index 1 so the first item in the array is at position values[1, 1].

Creating Country Data

The program stores data in the CountryData class. The following code shows the pieces of the class that store the data. I’ll show the rest of the class later.

public class CountryData
{
    static public DateTime[] Dates = null;
    public string Name = null;
    public int[] Cases = null;
    public int MaxCases = 0;
    public int CountryNumber = -1;

    public PointF[] DeviceCoords = null;

    public override string ToString()
    {
        return Name;
    }

    public void SetMax()
    {
        MaxCases = Cases.Max();
    }
}

The following list summarizes the class’s data fields.

  • Dates – The dates for the data points
  • Name – The country’s name
  • Cases – The number of COVID-19 cases for the corresponding date
  • MaxCases – The maximum number of cases for this country on any date
  • CountryNumber – Just a number
  • DeviceCoords – The country’s data points transformed into bitmap coordinates

The Dates array is declared static so it is shared by all of the CountryData objects.

The program only uses the countries’ numbers to calculate a color for each country. (You’ll see that later.) The number doesn’t really matter as long as it doesn’t change for each country.

The DeviceCoords array holds the country’s data values converted into bitmap coordinates. The program uses those values to tell if the mouse (which has location in bitmap coordinates) is over the country’s data.

The ToString method returns the country’s name. The program’s CheckedListBox automatically uses this to display each CountryData object. (Comment out this method to see what happens if you don’t override ToString).

The program calls the SetMax method after a country’s data has been loaded. That method uses the Max LINQ extension method to find the largest value in the Cases array.

The following CreateCountryData method uses the CSV data to create CountryData objects.

// Create the country data.
private void CreateCountryData(object[,] fields)
{
    // Load the dates.
    Dictionary<string, CountryData< country_dict =
        new Dictionary<string, CountryData<();
    const int first_date_col = 5;
    int max_row = fields.GetUpperBound(0);
    int max_col = fields.GetUpperBound(1);
    int num_dates = max_col - first_date_col + 1;
    CountryData.Dates = new DateTime[num_dates];
    for (int col = 1; col <= num_dates; col++)
    {
        // Convert the date into a double and then into a date.
        double double_value = (double)fields[1, col + first_date_col - 1];
        CountryData.Dates[col - 1] =
            DateTime.FromOADate(double_value);
    }

    // Load the country data.
    const int country_col = 2;
    for (int country_num = 2; country_num <= max_row; country_num++)
    {
        // Get the country's name.
        string country_name = fields[country_num, country_col].ToString();

        // Get or create the country's CountryData object.
        CountryData country_data;
        if (country_dict.ContainsKey(country_name))
        {
            country_data = country_dict[country_name];
        }
        else
        {
            country_data = new CountryData();
            country_data.Name = country_name;
            country_data.Cases = new int[num_dates];
            country_dict.Add(country_name, country_data);
        }

        // Add to the country's data.
        for (int col = 1; col <= num_dates; col++)
        {
            // Add the value to the country's total.
            country_data.Cases[col - 1] +=
                (int)(double)fields[country_num, col + first_date_col - 1];
        }
    }

    // Convert CountryDict into CountryList.
    CountryList = country_dict.Values.ToList();

    // Set MaxCases values.
    foreach (CountryData country in CountryList)
    {
        country.SetMax();
    }

    // Sort.
    CountryList.Sort(Comparer);

    // Number the countries and set MaxCases values.
    for (int i = 0; i < CountryList.Count; i++)
    {
        CountryList[i].CountryNumber = i;
    }
}

The method first creates a dictionary to hold the data. It allocates the Dates array and then loops through the data’s first row to read the dates.

Excel represents dates as a double-precision offset from the base date, which is midnight, 30 December 1899. (Because why not use that as the base date?) The program casts the value into an object and then uses DateTime.FromOADate to convert the double into a date.

After reading the dates, the program loops through the country data rows. For each row it reads the country name and looks up the country in the dictionary. If the country is not present, the program creates a new CountryData object and adds it to the dictionary.

The program then loops through the row’s case data, adding the values to the CountryData object’s Cases array. Excel stores numeric values a doubles, so the program converts the generic object into a double. Because the case counts are in fact integers, the code converts the double result into an integer and then adds it to the country’s total for that date.

After it finishes loading the country data, the program pulls the dictionary’s values out into a list. It then loops through the countries and calls their SetMax values so we can later use the maximum number of cases for each country without needing to calculate them again.

The program them sorts the countries using a Comparer object to determine the sort order. I’ll explain that object next.

Finally, the program loops through the countries and sets their CountryNumber values. Those values to not change later even if the list is resorted in a different order.

Comparers

When you call a list’s Sort method, you can pass it a comparer object to tell the method how to sort items.

The comparer class must implement the IComparer interface so the Sort method can use it. The following code shows the CountryDataComparer class that this program uses.

public class CountryDataComparer : IComparer<CountryData>
{
    public enum CompareTypes
    {
        ByName,
        ByMaxCases,
        //ByPopulation,
    }
    private CompareTypes CompareType = CompareTypes.ByName;

    public CountryDataComparer(CompareTypes type)
    {
        CompareType = type;
    }

    public int Compare(CountryData x, CountryData y)
    {
        switch (CompareType)
        {
            case CompareTypes.ByName:
                return x.Name.CompareTo(y.Name);
            case CompareTypes.ByMaxCases:
            default:
                return -x.MaxCases.CompareTo(y.MaxCases);
        }
    }
}

This class defines an enumeration that the program can use to specify the sort type. These objects can sort by country name or maximum number of cases.

The variable CompareType indicates which comparison type a particular comparer object should use. The class’s constructor sets the object’s comparison type.

The Compare method required by the IComparer interface checks the object’s CompareType and then compares the two objects either by name or MaxCases value.

The program declares its comparer object like this.

private CountryDataComparer Comparer =
    new CountryDataComparer(CountryDataComparer.CompareTypes.ByMaxCases);

This means the program initially sorts countries by maximum number of cases.

When you click one of the radio buttons, an event handler changes the comparer. The following code shows how the program creates the new comparer when you click the By Name button.

private void radSortByName_Click(object sender, EventArgs e)
{
    if (CountryList == null) return;
    Comparer = new CountryDataComparer(CountryDataComparer.CompareTypes.ByName);
    clbCountries.DataSource = null;
    CountryList.Sort(Comparer);
    clbCountries.DataSource = CountryList;
    RedrawGraph();
}

This code sets the Comparer variable equal to a new comparer that sorts by name. It then sets the CheckedListBox control’s data source to null, re-sorts the list of data, sets the CheckedListBox control’s data source back to the list, and then redraws the graph. (I’ll get to how that works that eventually.)

Drawing the Graph

The following method draws the graph for the countries selected in the CheckedListBox.

// Draw the graph.
private void GraphCountries()
{
    ClosePoint = new PointF(-1, -1);
    if (SelectedCountries.Count == 0)
    {
        picGraph.Image = null;
        return;
    }

    // Get the maximum value.
    float y_max = SelectedCountries.Max(country => country.Cases.Max());

    // Create a transformation to make the data fit the PictureBox.
    DefineTransform(SelectedCountries, y_max);

    // Create a bitmap.
    Bitmap bm = new Bitmap(
        picGraph.ClientSize.Width,
        picGraph.ClientSize.Height);
    using (Graphics gr = Graphics.FromImage(bm))
    {
        gr.SmoothingMode = SmoothingMode.AntiAlias;
        gr.TextRenderingHint = TextRenderingHint.AntiAlias;
        gr.Transform = Transform;

        // Draw the axes.
        DrawAxes(gr);

        // Draw the curves.
        Color[] colors =
        {
            Color.Red, Color.Green, Color.Blue, Color.Black,
            Color.Cyan, Color.Orange,
        };
        int num_colors = colors.Length;
        using (Pen pen = new Pen(Color.Black, 0))
        {
            foreach (CountryData country in SelectedCountries)
            {
                pen.Color = colors[country.CountryNumber % num_colors];
                country.Draw(gr, pen, Transform);
            }
        }
    }

    // Display the result.
    picGraph.Image = bm;
}

The method first sets ClosePoint to (-1, -1). That point indicates the point on the graph where the mouse is an initially the program assumes the mouse is not on the graph.

Next if no countries are selected, the method sets the picGraph PictureBox control’s Image to null and returns.

The code then uses the LINQ Max extension method to get the largest maximum number of cases from the objects in the SelectedCountries list and calls the DefineTransform method (shown shortly) to make a transformation so it can draw using the data’s values and the result will be mapped onto the drawing surface.

The method then creates a Bitmap large enough to fill the PictureBox and makes an associated Graphics object. The program sets a few Graphics object properties. In particular it sets the object’s Transform property to a matrix named Transform. You’ll see how that is defined next.

The method then calls the DrawAxes method to draw the X and Y axes and defines the colors that it will use to draw the countries’ data curves.

It then creates a pen with thickness 0. The value 0 tells the drawing methods to draw the line as thinly as possible (one pixel wide on a monitor) no matter what transformation might be in place that would otherwise scale the pen.

The program loops through the selected countries and sets the pen’s color to a value taken from the colors array. The index in the array is given by the country’s taken modulus the number of colors. This is why we set the country number earlier. That number doesn’t change so the country’s color won’t change even if you resort the countries or change the countries that are selected.

The code calls each country’s Draw method to do the actually drawing. After the bitmap is complete, the program displays it.

DefineTransform

The following code shows the DefineTransform method.

private void DefineTransform(List<CountryData> country_list, float y_max)
{
    int num_cases = country_list[0].Cases.Length;
    WorldBounds = new RectangleF(0, 0, num_cases, y_max);
    int wid = picGraph.ClientSize.Width;
    int hgt = picGraph.ClientSize.Height - 1;
    const int margin = 4;
    PointF[] dest_points =
    {
        new PointF(margin, hgt - margin),
        new PointF(wid - margin, hgt - margin),
        new PointF(margin, margin),
    };
    Transform = new Matrix(WorldBounds, dest_points);
    InverseTransform = Transform.Clone();
    InverseTransform.Invert();
}

This method defines a rectangle that bounds the data values. It then creates an array of points that defines corners of the bitmap. The code then uses the rectangle and array to define a matrix named Transform that maps the data coordinates onto the bitmap.

That transformation allows the program to draw in data coordinates and have the result appear in bitmap coordinates. Sometimes the program needs to do the reverse, so the program creates a new matrix named InverseTransform that is a copy of the first one and inverts the copy.

DrawAxes

The DrawAxes method is mostly straightforward so I won’t show most of it here, but it does two interesting things in addition to drawing a bunch of lines.

First, it must decide how tall to make the graph and how frequently to draw horizontal lines. The following code snippet does that.

// Calculate the Y step value.
// Find the largest power of 10 less than y_max.
float y_max = WorldBounds.Bottom;
int power = (int)Math.Log10(y_max);
// If this is more than 1/2 of y_max, use the next smaller power.
if (Math.Pow(10, power) > y_max / 2) power--;
int y_step = (int)Math.Pow(10, power);

This code first gets the data’s largest Y value, takes the logarithm base 10, and truncates the result. For example, if the largest value is 120,000, the logarithm is 5.08, and truncating that gives 5.

Next the program raises ten to this power, in this example giving 100,000. If that value is greater than half of the maximum Y value, the program subtracts one from the power. In this example 100,000 is more than half of 120,000, so we subtract one.

The code then raises ten to the final power to get the distance between the horizontal lines, 10,000 in this example.

The result is that the y_step value provides at least two divisions that are powers of ten below the maximum value. In this example the horizontal lines are 10,000 apart.

The second interesting thing that the DrawAxes method does is it draws the tick marks on the X axis in pixels. If you just drew the tick marks in data coordinates, then the Graphics object’s transformation would scale the marks and produce unpredictable results.

The following snippet ensures that the the tick marks are ten pixels tall.

// Calculate the tick mark size.
const int tick_y_pixels = 5;
PointF[] tick_points = { new PointF(0, tick_y_pixels) };
InverseTransform.TransformVectors(tick_points);
float tick_y = -tick_points[0].Y;

// Draw tick marks.
for (int i = 0; i < num_cases; i++)
{
    gr.DrawLine(pen, i, -tick_y, i, tick_y);
}

This code creates an array holding a single PointF with Y coordinate equal to half of the desired tick mark length. It the calls the InverseTransform matrix’s TransformVectors method to transform the PointF back from bitmap coordinates to data coordinates.

A matrix has two methods that can apply a transformation to an array of PointF. The TransformPoints method treats the values as points. It will scale, rotate, and translate the values as if they were points.

The TransformVectors method treats the values as vectors. Vectors have a direction and length but not a location. For example, the vector pointing from point (2, 3) to point (4, 6) has components <4 – 2, 6 – 3> = <2, 3>. When the TransformVectors method acts on a vector, it rotates and scales the vector, but does not translate it. That is useful in this example because all I really want is the length of the result. If we used TransformPoints, then the point would be translated so it’s Y value would be modified and we could not use it to find the length of a tick mark. Basically we just want to scale the Y value 5 to see how long the tick mark should be.

(Another approach would be to give the array two points with Y coordinates that differ by 5, use TransformPoints, and then subtract their resulting Y coordinates to see how far apart they are in the data coordinate system.)

After figuring out how far five pixels in bitmap coordinates is in data coordinates, the method simply loops through the X values (the dates) and draws their tick marks.

Download the example to see the rest of the DrawAxes method.

CountryData.Draw

The CountryData class’s Draw method shown in the following code draws a country’s data.

// Draw this country's data.
public void Draw(Graphics gr, Pen pen, Matrix transform)
{
    // Make the array of points.
    int num_cases = Cases.Length;
    PointF[] points = new PointF[num_cases];
    for (int i = 0; i < num_cases; i++)
        points[i] = new PointF(i, Cases[i]);

    // Draw the curve.
    gr.DrawLines(pen, points);

    // Find device coordinates for tooltips.
    transform.TransformPoints(points);
    DeviceCoords = points;
}

This code loops through the country’s data and creates a point representing each value. It then calls DrawLines to connect the points. The Graphics object’s transformation automatically transforms the values to the bitmap’s coordinate system.

The method then transforms the points into bitmap coordinates and saves them in the country’s DeviceCoords variable. (Recall that the program uses those coordinates to determine whether the mouse is over the curve.)

Displaying Data Tooltips

The last piece of the program that I want to describe determines when the mouse is over a curve. The following code starts the process when the mouse moves over the graph.

private void picGraph_MouseMove(object sender, MouseEventArgs e)
{
    SetTooltip(e.Location);
}

private void SetTooltip(PointF point)
{
    if (picGraph.Image == null) return;
    if (SelectedCountries == null) return;

    string new_tip = "";
    int day_num;
    int num_cases;
    foreach (CountryData country in SelectedCountries)
    {
        if (country.PointIsAt(point, out day_num,
            out num_cases, out ClosePoint))
        {
            new_tip = country.Name + "\n" +
                CountryData.Dates[day_num].ToShortDateString() + "\n" +
                num_cases.ToString("n0") + " cases";
            break;
        }
    }

    if (tipGraph.GetToolTip(picGraph) != new_tip)
        tipGraph.SetToolTip(picGraph, new_tip);
    picGraph.Refresh();
}


When the mouse moves, the MouseMove event handler simply calls the SetTooltip method.

The SetTooltip method returns if there is no graph yet or if you have not selected any countries.

If the method doesn’t immediately exit, it sets new_tip equal to a blank string. It then loops through the selected countries and calls their PointIsAt methods (described shortly) to see if the mouse is over the country’s data. If PointIsAt returns true, the code sets new_tip to an appropriate tooltip value and breaks out of the loop.

After the loop ends, the program compares the PictureBox control’s current tooltip to the one stored in new_tip. If the two are different, the program updates the displayed tooltip.

The method finishes by refreshing the PictureBox to circle the point under the mouse. I’ll describe that shortly, but first here’s the CountryData class’s PointIsAt method.

public bool PointIsAt(PointF device_point, out int day_num,
    out int num_cases, out PointF close_point)
{
    const double close_dist = 4;
    PointF closest;
    for (int i = 1; i < Cases.Length; i++)
    {
        double dist = FindDistanceToSegment(device_point,
            DeviceCoords[i - 1], DeviceCoords[i], out closest);
        if (dist <= close_dist)
        {
            // See whether it is closer to this this
            // segment's left or right point.
            if (DistanceBetweenPoints(DeviceCoords[i - 1], closest) <
                DistanceBetweenPoints(DeviceCoords[i], closest))
                day_num = i - 1;
            else
                day_num = i;
            num_cases = Cases[day_num];

            // Use the point on the segment.
            //close_point = closest;

            // Use the closer segment end point.
            close_point = DeviceCoords[day_num];
            return true;
        }
    }

    day_num = -1;
    num_cases = -1;
    close_point = new PointF(-1, -1);
    return false;
}

This method loops through adjacent pairs of the country’s data points. For each pair it calls the FindDistanceToSegment method to see how far the point is from the line segment connecting the points. See the post Find the shortest distance between a point and a line segment in C# to learn how that method works.

If the point is within four pixels of the segment, the mouse is close to the current segment. The program copmares the distances between the mouse’s location and the segment’s two end points and sets day_num to the index of the closer end point. It then saves the corresponding number of cases in the num_cases output parameter.

The code also saves the point that the program should circle in the output parameter close_point. Depending on which line of code you comment out, that might be the point on the segment or the closer end point.

The method then returns true to let the calling method know that the point is near the data.

Paint

The last piece of code that I want to discuss is the PictureBox control’s Paint event handler. The program’s MouseMove event handler refreshes the PictureBox to circle the point on the graph that is close to the mouse’s position.

The following code shows the Paint event handler.

private void picGraph_Paint(object sender, PaintEventArgs e)
{
    if (ClosePoint.X < 0) return;

    const int radius = 3;
    e.Graphics.SmoothingMode = SmoothingMode.AntiAlias;
    float x = ClosePoint.X - radius;
    float y = ClosePoint.Y - radius;
    e.Graphics.FillEllipse(Brushes.White, x, y, 2 * radius, 2 * radius);
    e.Graphics.DrawEllipse(Pens.Red, x, y, 2 * radius, 2 * radius);
}

Note that this method does not call the Graphics object’s Clear method. The PictureBox control’s Image property is displaying the graph. If the program called Clear, it would erase that image.

If the variable ClosePoint has a negative X coordinate, then the Paint event handler simply exits. Otherwise it draws a circle centered at the point.

The result is that you should see a small circle at the data point and a tool tip indicating the country, date, and number of cases under the mouse. For example, the tooltip in the picture at the top of this post indicates that the United States had 188,172 COVID-19 cases on March 31, 2020.

Conclusion

Again I apologize for this post’s length. The program’s pieces are not too complicated, but there are a lot of them.

Please download the example and experiment with it to understand more about how different countries have handles the COVID-19 pandemic so far. The graph makes some things immediately obvious. For example, China and South Korea have both flattened their case curves dramatically. Other countries that acted less quickly or less strongly, such as Italy, Spain, and the United Kingdom, still have increasing numbers of cases. And some countries such as the United States and the United Kingdom have curves that are still upward curving, indicating that they are still experiencing exponential growth in their numbers of cases.

For now, look the program over, see how it works, and study the data. If you find any interesting patterns, please note them in the comments below.

Later posts will add other ways to study the data such as looking at different values like deaths, mortality ratios, and cases or deaths per million population. If you like, you can try to make some of those modifications yourself before I have a chance to post my versions.


Download Example   Follow me on Twitter   RSS feed   Donate




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

Build a Windows process tree in C#

[process tree]

A process tree is a tree that shows the processes running on the computer arranged hierarchically so you can see which processes started other processes. My first attempts at this used techniques that I found scattered around the internet. Unfortunately those techniques generally worked by finding the parent process for individual processes. Repeating those techniques for each of the hundreds of processes on my system took a couple of minutes.

This example uses a different approach that only takes about half a second. It gets information on all of the process at once and then uses the information to build the tree.

ProcessInfo

The program stores information about a process in the following ProcessInfo class.

class ProcessInfo : IComparable<ProcessInfo>
{
    public Process TheProcess;
    public ProcessInfo Parent;
    public List<ProcessInfo> Children = new List<ProcessInfo>();

    public ProcessInfo(Process the_process)
    {
        TheProcess = the_process;
    }

    public override string ToString()
    {
        return string.Format("{0} [{1}]",
            TheProcess.ProcessName, TheProcess.Id);
    }

    public int CompareTo(ProcessInfo other)
    {
        return TheProcess.ProcessName.CompareTo(
            other.TheProcess.ProcessName);
    }
}

The class stores a reference to the process that it represents in the variable TheProcess. Note that the class does not keep itself up to date so, for example, if the process ends, the ProcessInfo object does not know that.

As you can probably guess, the class stores the process’s parent process in variable Parent. The Children list holds references to this process’s child processes.

The class’s constructor simply saves a reference to the process. The ToString method returns the process’s name and ID.

Finally the CompareTo method compares this object’s ProcessName to another object’s ProcessName. That method implements the IComparable interface, which allows the program to sort ProcessInfo objects alphabetically.

Form1_Load

When the program starts, the following Load event handler does most of the interesting work.

private int NumProcesses, NumThreads;

private void Form1_Load(object sender, EventArgs e)
{
    Stopwatch watch = new Stopwatch();
    watch.Start();

    Dictionary<int, ProcessInfo> process_dict =
        new Dictionary<int, ProcessInfo>();

    // Get the processes.
    foreach (Process process in Process.GetProcesses())
    {
        process_dict.Add(process.Id, new ProcessInfo(process));
    }

    // Get the parent/child info.
    ManagementObjectSearcher searcher = new ManagementObjectSearcher(
       "SELECT ProcessId, ParentProcessId FROM Win32_Process");
    ManagementObjectCollection collection = searcher.Get();

    // Create the child lists.
    foreach (var item in collection)
    {
        // Find the parent and child in the dictionary.
        int child_id = Convert.ToInt32(item["ProcessId"]);
        int parent_id = Convert.ToInt32(item["ParentProcessId"]);

        ProcessInfo child_info = null;
        ProcessInfo parent_info = null;
        if (process_dict.ContainsKey(child_id))
            child_info = process_dict[child_id];
        if (process_dict.ContainsKey(parent_id))
            parent_info = process_dict[parent_id];

        if (child_info == null)
            Console.WriteLine(
                "Cannot find child " + child_id.ToString() +
                " for parent " + parent_id.ToString());

        if (parent_info == null)
            Console.WriteLine(
                "Cannot find parent " + parent_id.ToString() +
                " for child " + child_id.ToString());

        if ((child_info != null) && (parent_info != null))
        {
            parent_info.Children.Add(child_info);
            child_info.Parent = parent_info;
        }
    }

    // Convert the dictionary into a list.
    List<ProcessInfo> infos = process_dict.Values.ToList();

    // Sort the list.
    infos.Sort();

    // Populate the TreeView.
    NumProcesses = 0;
    NumThreads = 0;
    foreach (ProcessInfo info in infos)
    {
        // Start with root processes.
        if (info.Parent != null) continue;

        // Add this process to the TreeView.
        AddInfoToTree(trvProcesses.Nodes, info);
    }
    lblCounts.Text =
        "# Processes: " + 
        NumProcesses.ToString() + ", " +
        "# Threads : " +
        NumThreads.ToString();

    watch.Stop();
    Console.WriteLine(string.Format("{0:0.00} seconds",
        watch.Elapsed.TotalSeconds));
}

After starting a stopwatch, the code creates a dictionary that uses an integer (process ID) for the keys and ProcessInfo objects for the values.

Next the code loops through the processes returned by the Process.GetProcesses. For each returned process, the program creates a new ProcessInfo object and adds that object to the dictionary.

After this step, the program has a list of the system’s processes, but it doesn’t have any parent/child information. To get that information, the program uses a ManagementObjectSearcher. (To use that class, add a reference to the System.Management library and add the statement using System.Management at the top of the file.)

The program initializes the searcher with the query SELECT ProcessId, ParentProcessId FROM Win32_Process. For every process that is running, that fetches the process’s ID and its parent ID. The program calls the object’s Get method to execute the query and return a collection holding the results.

Now the program loops through the results. For each result, the program gets the child and parent process IDs and looks them up in the dictionary to find the corresponding ProcessInfo objects. If it finds both ProcessInfo objects, the code sets the child’s Parent field and adds the child to the parent’s Children list.

After the program has finished looping through the searcher’s results, the objects in the dictionary have links to their parents and children. To make using the objects easier, the program gets the dictionary’s value collection, converts it into a list, and sorts the result. (Remember that the ProcessInfo class implements IComparable so the list can sort the objects.)

Next the program uses the list to populate the program’s TreeView control. To do that, it loops through the list. If a process has a parent, then it will be placed in the tree when its parent is placed in the tree. If a process does not have a parent, then the code adds it as a top-level node in the tree by calling the AddInfoToTree method described shortly.

After it finishes building the tree, the program displays the number of processes and threads that it found, and the elapsed time.

AddInfoToTree

The following AddInfoToTree method adds a ProcessInfo to the TreeView.

// Add a ProcessInfo, its children, and its threads to the tree.
private void AddInfoToTree(TreeNodeCollection nodes, ProcessInfo info)
{
    // Add the process's node.
    TreeNode process_node = nodes.Add(info.ToString());
    process_node.Tag = info;
    NumProcesses++;

    // Add the node's threads.
    if (info.TheProcess.Threads.Count > 0)
    {
        TreeNode thread_node = process_node.Nodes.Add("Threads");
        foreach (ProcessThread thread in info.TheProcess.Threads)
        {
            thread_node.Nodes.Add(string.Format(
                "Thread {0}", thread.Id));
            NumThreads++;
        }
    }

    // Sort the children.
    info.Children.Sort();

    // Add child processes.
    foreach (ProcessInfo child_info in info.Children)
    {
        AddInfoToTree(process_node.Nodes, child_info);
    }

    // Expand the main process node.
    if (info.Children.Count > 0)
        process_node.Expand();
}

The method takes as its first parameter the TreeNodeCollection where the process should be added.

The method adds a new node to the nodes collection and saves the ProcessInfo object in the new node’s Tag property. This example does not use that value, but another program might want to be able to find the ProcessInfo object for a tree node. It could then use that object to get the process object and all of the properties that it contains.

The code increments NumProcesses to indicate that it added another process to the tree.

Next, if the process has threads, the method adds them to the tree. It creates a child node labeled Threads and then loops through the threads, adding them to the thread node.

Before the method adds the process’s children to the tree, it sorts the children. (Again, this is possible because the ProcessInfo class implements IComparable.) The code then loops through the children and recursively calls the AddInfoToTree method to add the child’s information below the current process’s node.

The method finishes by expanding the process’s node if the node has children. The result is that TreeView nodes that have children are expanded so you can see all of the processes, but Threads nodes are not expanded. (There are so many of them that it make the tree hard to read.)

Conclusion

Download the example to experiment with it. If you like, you can modify the example to manipulate the processes. For example, you could click on tree node and then call the corresponding process’s Kill method. (There’s some commented out code in the example that does this.)


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in algorithms, system | Tagged , , , , , , , , , | 5 Comments

Draw lines with gaps to show they are passing under other lines in C#

[draw lines]

This example shows how to draw lines with gaps in them to show that they are passing under other lines. It seems like there must be a name for this, but I couldn’t find it so I’m calling them “cut lines.” (If you know the “official” name for this, please post a comment below.)

You could calculate where two lines intersect and then break the line on the bottom into two pieces, shortening them a bit so they leave a gap where the upper line is supposed to be. If you had many lines, you might then need to break the pieces into smaller pieces and so on until you finish examining every pair of lines for intersections. That should all work, but it sounds like a lot of trouble.

Fortunately there’s a much simpler way to draw lines with gaps like this. Loop through the lines in bottom-to-top order. For each line, first draw it with a slightly thicker pen that uses the background color. That creates a channel for the line through the lines below it. Then draws the line with its usual pen.

To make this slightly easier, I created the following method to draw lines.

// Draw a line segment in the indicated color.
private void DrawLine(Graphics gr, Pen bg_pen, Pen fg_pen,
    Point start_point, Point end_point)
{
    if (bg_pen != null)
        gr.DrawLine(bg_pen, start_point, end_point);
    gr.DrawLine(fg_pen, start_point, end_point);
}

If the background pen bg_pen is not null, the method draws the line using that pen. It then draws the line again using the foreground pen fg_pen.

The following code shows how the program’s Paint event handler uses this method to draw lines.

private void picLines_Paint(object sender, PaintEventArgs e)
{
    e.Graphics.SmoothingMode = SmoothingMode.AntiAlias;

    // Draw the previously saved lines.
    Pen bg_pen = null;
    if (chkUseCuts.Checked) bg_pen = new Pen(picLines.BackColor, 8);
    using (Pen fg_pen = new Pen(Color.Blue, 4))
    {
        for (int i = 0; i < StartPoints.Count; i++)
        {
            DrawLine(e.Graphics, bg_pen, fg_pen,
                StartPoints[i], EndPoints[i]);
        }

        // Draw the new line if there is one.
        if (Drawing)
        {
            fg_pen.Color = Color.Red;
            DrawLine(e.Graphics, bg_pen, fg_pen,
                NewStartPoint, NewEndPoint);
        }
    }
    if (bg_pen != null) bg_pen.Dispose();
}

This code defines the bg_pen variable to hold the background pen and sets it to null. Then if you have checked the program’s Use Cuts box, the method sets the pen equal to a new eight-pixel-wide pen using the drawing’s background color.

The code then creates a four-pixel-wide blue pen.

Next the method loops through the line segments whose end points are stored in the StartPoints and EndPoints lists. For each segment, the code simply calls the earlier DrawLine method to draw the line above the previous lines.

If you are in the middle of drawing a new line, the program changes the foreground pen’s color to red and draws the new line so far.

Finally, if the background pen is not null, the code calls its Dispose method. It is important to call the Dispose method of any object that has such a method so it can free up resources that are limited on the system. Pens and brushes are two common items that have a Dispose method.

If you define an object inside a using statement, as the code does with the foreground brush, then the program automatically calls its Dispose method when the using block ends.

[draw lines]

Unfortunately this technique is harder to apply to more complicated objects such as self-overlapping polygons (like a star) or mutually overlapping objects (like interlocked circles). In those cases, you will probably need to draw all of the objects and then go back and draw just their points of intersections using the new technique. For an example that does something like this, see the post Draw interlocked circles in C#.

Download the example program to experiment with it and to see other details such as how the program lets you click and drag to select new lines.


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in drawing, graphics, Uncategorized | Tagged , , , , , , , , | Leave a comment

Recommended Book on CD: “The Serpent of Venice” by Christopher Moore

This book continues the adventures of Pocket, the fool who is the title character in the previous Christopher Moore book Fool. The book begins with Pocket’s murder, or at least attempted murder. Hilarity then ensures as Pocket spends the rest of the book avenging his own death.

If you read my earlier post about Moore’s book Fool, you may remember how much I enjoyed the performance of reader Euan Morton. Morton brings the same amazing set of skills to this book, giving each character a separate, recognizable, and somehow wholly appropriate voice. His performances are so good that I may seek out books based on his reading them. (I notice that he is also the reader for Moore’s book Sacre Bleu. I’ve read it but now may need to find it on CD.)

I also notice that Moore has a new book coming out, Shakespeare for Squirrels and Morton is also the reader for that book. At a whopping $31 for the paperback and $40 for the CD version, I may need to wait on that one for a while or try the $15 Kindle edition.

As with all of Moore’s books, skip this book if you don’t like bawdy humor. But if you like general silliness in a Shakespearean setting, this is another great listen.


Follow me on Twitter   RSS feed   Donate




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

Animate maze solving, version 3

[animate maze solving]

The previous maze-solving examples Animate maze solving, version 1 and Animate maze solving, version 2 used a recursive method named Solve that returns an IEnumerable containing the paths that the program was searching.

Removing Recursion

To remove the recursion, think about what happens during recursion or any method call for that matter. Here’s the structure of the Solve method.

private IEnumerable<List<MazeNode>> Solve(
    MazeNode end_node, List<MazeNode> path)
{
    ...

            foreach (List<MazeNode> test_path in Solve(end_node, path))
                yield return test_path;
    ...
}

The method does a bunch of stuff and then uses a foreach loop to iterate over the paths returned by a recursive call to the Solve method. When the program makes that call, it saves the current call’s position and local variables. It then calls the method again passing it the desired end node and the path that we need to examine with a new node added at the end.

To remove the recursion, we can imitate those steps. In order to animate the solution, we also need to save that kind of state information and then later restore it so we can continue execution at the animation’s next step.

The Solve Method

Here’s the new version of the Solve method.

private List<MazeNode> Path = null;
private List<int> LastUsedNeighbor = null;

// The final node in the Path list is the node we are visiting.
// If LastUsedNeighbor has an entry for that node, then
// we have visited some of its children.
// See if we have a solution.
// If not, try the last node's next neighbor.
private void Solve()
{
    // See if we have reached the end node.
    int last_node_index = Path.Count - 1;
    MazeNode last_node = Path[last_node_index];
    if (last_node == EndNode)
    {
        FoundSolution = true;
        tmrStep.Enabled = false;
        return;
    }

    // See if the last node has any more neighbors we can visit.
    bool found_neighbor = false;
    int neighbor_index = LastUsedNeighbor[last_node_index];
    MazeNode neighbor = null;
    for (; ; )
    {
        // Try the next neighbor.
        neighbor_index++;

        // If we have checked all neighbors, break.
        if (neighbor_index >= last_node.Neighbors.Count) break;

        // See if this neighbor is not already in the current path.
        neighbor = last_node.Neighbors[neighbor_index];
        if (!neighbor.InPath)
        {
            // Visit this neighbor.
            found_neighbor = true;
            LastUsedNeighbor[last_node_index] = neighbor_index;
            break;
        }
    }

    // See if we found a neighbor to visit.
    if (found_neighbor)
    {
        // Visit this neighbor.
        Path.Add(neighbor);
        LastUsedNeighbor.Add(-1);
        neighbor.InPath = true;
    }
    else
    {
        // We have visited all of the last node's neighbors.
        // Remove the last node from the Path list.
        last_node.InPath = false;
        Path.RemoveAt(last_node_index);
        LastUsedNeighbor.RemoveAt(last_node_index);
    }
}

As before, the Path list stores the path we are currently exploring. The LastUsedNeighbor list holds the index of the last neighbor that we have considered for the last node in the path. When a “recursive” call returns, we use LastUsedNeighbor to decide which neighbor to explore next. If the current node has no more neighbors, then the “recursion” ends and control moves to the “calling method.”

The Solve method first checks to see if we have reached the maze’s destination node. If we have reached that node, the method sets FoundSolution to true, disables the tmrStep Timer, and returns.

If we have not yet found a solution, the method gets the index of the last neighbor visited. It then enters a loop to consider other neighbors of the current node. If the next possible neighbor index is greater than the current node’s neighbor count, then the code breaks out of the loop having found no new neighbor to use.

If the next neighbor considered is not currently in the test path, the code sets found_neighbor to true to indicate that we should use that neighbor. It adds the neighbor index to the LastUsedNeighbor list, and breaks out of the loop.

When the loop ends, the method checks whether it found a new neighbor to try. If it did find a neighbor, the code adds it to the Path list. It also adds -1 to the LastUsedNeighbor list to indicate that the last neighbor of this node is -1. That makes the Solve method’s loop starting looking for a new neighbor at index 0, which is this node’s first neighbor.

When the loop ends, if the method did not find a new neighbor to explore, then it must “move up” the “recursive call stack.” In that case, it removes the last node from the Path list because that node did not lead to a solution. It also removes the last entry from the LastUsedNeighbor list because we are done considering that node’s neighbors.

Now each time this method is called, it performs one step in the search for a complete path.

Searching for a Solution

When the program needs to start finding a path through the maze, it executes the following StartSolving method.

// Start solving the maze.
private void StartSolving()
{
    // Remove any previous results.
    Path = new List<MazeNode>();
    LastUsedNeighbor = new List<int>();
    foreach (MazeNode node in Nodes)
        node.InPath = false;

    // Make the nodes define their neighbors.
    foreach (MazeNode node in Nodes)
        node.DefineNeighbors();

    // Start at the start node.
    Path.Add(StartNode);
    LastUsedNeighbor.Add(-1);
    StartNode.InPath = true;

    // Solve.
    FoundSolution = false;
    tmrStep.Enabled = true;
}

This method creates new, empty Path and LastUsedNeighbor lists and then defines the nodes’ neighbors as usual. It then adds the start node to the Path list and adds -1 to the LastUsedNeighbor list. It sets the start node’s InPath value to true, sets FoundSolution to false, and starts the tmrStep Timer.

When the timer’s Tick event fires, the following event handler executes.

// Take a step in solving the maze.
private void tmrStep_Tick(object sender, EventArgs e)
{
    Solve();
    picMaze.Refresh();
}

This code calls the Solve method to take the next step searching for the solution. It then refreshes the picMaze PictureBox so its Paint event handler can display the current path.

Conclusion

This example uses a timer to animate maze solving. Instead of using recursion, it uses the Path and LastUsedNeighbor lists to keep track of where it is in the process of finding a path through the maze. You can always remove recursion from any program if you try hard enough. In the worst case, you can imitate the recursion as this example does.

The previous version of the program used an enumerator created by a recursive method. The process of returning an enumerator is a bit strange and recursion can also be confusing, but personally I like that solution. It’s weird, but understandable once you figure out how to return enumerations.

Download the examples to see additional details and to compare their code.


Download Example   Follow me on Twitter   RSS feed   Donate




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

Animate maze solving, version 2

[animate maze solving]

My earlier post Animate maze solving, version 1 uses a method that returns an enumeration to show the steps used to find a path through a maze. That method works but it uses a loop that includes calls to Thread.Sleep and Application.DoEvents.

That technique works, but it’s inelegant and can sometimes interfere with the normal operation of the event loop. For instance, the previous example needed to provide a special way to break out of the loop if the user tried to close the form. If the code did not do that, then the program could remain in a sort of zombie mode where the form has disappeared but the code was still running.

This post describes an improved solution.

[Essential Algorithms]
Note that this algorithm is similar to those described in my book Essential Algorithms, Second Edition. That book explains many other algorithms for finding paths through networks such as the mazes used here.

Approach

Making a method return an enumeration is a clever way to return results from inside a sequence of recursive calls and then resume those calls later, and its still worth using that technique. The problem with the previous example was that it looped through the enumeration in a foreach loop. That made it awkward to process events within the loop and to leave the loop early.

This example’s approach takes advantage of a useful but often overlooked fact about enumerations: they have enumerators. An enumerator is an object that keeps track of the position within an enumeration. A foreach loop uses an enumerator to loop through the values.

The new example keeps its own reference to an enumerator and uses it to move through the values when a timer fires. Because the program uses a timer, it doesn’t need to sleep and use Application.DoEvents to process pending events. That’s basically what the normal event loop does while the program is waiting for the timer to fire.

Code

The new example’s Solve method is the same as before. It still recursively searches for a path through the maze, uses yield return to return paths, and uses yield break to break out of the recursion when it has found a solution.

The following code shows the new version of the StartSolving method.

IEnumerator<List<MazeNode>> PathEnumerator = null;

// Start solving the maze.
private void StartSolving()
{
    // Remove any previous results.
    Path = new List<MazeNode>();
    foreach (MazeNode node in Nodes)
        node.InPath = false;

    // Make the nodes define their neighbors.
    foreach (MazeNode node in Nodes)
        node.DefineNeighbors();

    // Start at the start node.
    Path.Add(StartNode);
    StartNode.InPath = true;

    // Create the IEnumerable to generate paths.
    FoundSolution = false;
    IEnumerable<List<MazeNode>> enumerable = Solve(EndNode, Path);

    // Get the enumerable's enumerator.
    PathEnumerator = enumerable.GetEnumerator();

    // Start the timer.
    tmrStep.Enabled = true;
}

This new version builds kits maze network and adds the start node to the Path list as before. It then calls the Solve method and saves its IEnumerable result in variable enumerable.

Note that the Solve method does not actually do anything at this point. In fact the Solve method is not even invoked.

After setting the enumerable variable, the program calls its GetEnumerator method to get an enumerator object. Again, the Solve method doesn’t do anything at this point. The enumerator has not requested a value so Solve has not produced one yet.

The StartSolving method enables its timer and ends.

When the timer fires, the following Tick event handler executes.

// Get and display the next path.
private void tmrStep_Tick(object sender, EventArgs e)
{
    PathEnumerator.MoveNext();
    Path = PathEnumerator.Current;
    picMaze.Refresh();
}

This code calls the enumerator’s MoveNext method to generate the next value in the enumeration. This is where the Solve method springs into action. It executes until it produces a result and returns it with the yield return statement. At that point, the Solve method is suspended and control returns to the Tick event handler.

The event handler uses the enumerator’s Current property to get the enumeration’s current value and refreshes the program’s PictureBox to show the current path.

Each time the Tick event occurs, the program uses the enumerator to get the next path in the enumeration and displays it.

The new example doesn’t need a clever way to break out of a foreach loop because it does not use such a loop. It still needs the FoundSolution variable so it can climb out of the recursive calls to the Solve method.

If you create a new maze or click the maze to define the start or end point, the program disables its timer so it stops the previous search. If you close the form, the normal event loop is smart enough to stop waiting for the timer, so the program ends normally.

If you define new start and end points to begin a new search, the new call to StartSolving creates a new enumerator and the whole things starts over.

Summary

Using an enumeration with yield return and yield break in this way is still confusing, but it’s a lot less confusing than the previous version. (At least in my humble opinion.)

The remaining complexity comes from the recursion. The yield statements provide a sneaky trick for temporarily leaving the recursion, but that’s still the most complicated part. In my final post on this topic, I’ll show how you can eliminate the recursion entirely so you don’t need to use yield. I’m not sure it’s less confusing or in any way better than this version, but it does emphasize that you can remove recursion if you really want to.

Meanwhile, download the new example and experiment with it to see how it works and to see additional details.

[Essential Algorithms]
Note that this algorithm is similar to those described in my book Essential Algorithms, Second Edition. That book explains many other algorithms for finding paths through networks such as the mazes used here.


Download Example   Follow me on Twitter   RSS feed   Donate




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

Quarantine Reading Suggestions

[reading suggestions]

Currently more than a billion people are locked down to slow the spread of the COVID-19 virus. If you’re a programmer, then you can hopefully work from home and remain productive. If you can’t, here are some suggestions for books that you can read to keep your programming skills sharp. Even if you can work from home, you may find some of these books provide a much needed distraction from current events.

Improve Your Programming and Problem Solving Skillz

These books will help you improve your programming skills. Some, like the algorithms and database design books, cover topics that every programmer should study. Others, like the software engineering book, will be useful to programmers, although perhaps not as directly as the algorithms and database design books. Finally, a few books such as the three-dimensional programming book, cover more specialized topics that are not absolutely necessary for everyone. (Although I find them extremely fun and interesting!)

Note that the database design and software engineering books were written to be usable in a classroom. The times that I have taught in the classroom, I found humor an invaluable way to keep students awake and interested, so those books have a slightly more humorous feel. I wouldn’t say they’re as funny as a Steve Martin or John Oliver show, but I think they’re more amusing than most software books.

Essential Algorithms, Second Edition: A Practical Approach to Computer Algorithms Using Python and C#

Algorithms are the basis of any program. A good algorithm can mean the difference between finding a solution to a problem in minutes, days, or not at all. This book uses relatively straightforward English to explain a wide variety of algorithms that you can use under many different circumstances. Algorithms include classics such as sorting and searching algorithms, plus newer more esoteric algorithms such as algorithms to solve the skyline problem.

(While you may not need to solve the skyline problem in your everyday work, it is still quite interesting because one of its algorithms provides an excellent demonstration of a divide-and-conquer problem-solving approach.)

WPF 3d, Three-Dimensional Graphics with WPF and C#

This easy-to-read guide provides everything you need to know to get started writing striking 3D graphics programs with WPF and C#. The book’s three parts describe 3D basics, building many different shapes, and advanced topics. More than 100 example programs covering such topics as:

  • The lights, cameras, materials, texture coordinates, and other details that you need to create a 3D scene
  • Orthographic, perspective, and other projections that emphasize different aspects of a scene
  • Special material treatments such as specular reflection, wireframes, and solid and translucent materials
  • Examples of many shapes including flat polygons, boxes, Platonic solids, spheres, tori, cones, and more
  • Advanced objects such as parametric surfaces, surfaces of transformation, fractal surfaces, and 2D and 3D text
  • Higher-level scene management to let users select and move objects
  • Advanced techniques such as loading models created in other applications and using skeletons

Essential Interview Puzzles Dissected, Solving and Understanding Interview Puzzles

Whether you’re applying for a programming job or a position on Wall Street, interview puzzles are the norm at many high-tech companies. This book explains how to solve more than 200 of the hardest and most common interview puzzles in use. Essential Interview Puzzles Dissected:

  • Shows how to solve more than 200 challenging interview puzzles
  • Reveals underlying techniques that let you solve problems that you haven’t seen before
  • Tells how you can show the interviewer that you can think in an organized fashion
  • Explains how to get “partial credit” when all else fails and you just can’t solve a puzzle
  • Includes programming challenges to give you a deeper understanding of puzzles (obviously only if you’re a programmer)

Beginning Software Engineering

A complete introduction to building robust and reliable software

Beginning Software Engineering demystifies the software engineering methodologies and techniques that professional developers use to design and build robust, efficient, and consistently reliable software. Free of jargon and assuming no previous programming, development, or management experience, this accessible guide explains important concepts and techniques that can be applied to any programming language. Each chapter ends with exercises that let you test your understanding and help you elaborate on the chapter’s main concepts. Everything you need to understand waterfall, Sashimi, agile, RAD, Scrum, Kanban, Extreme Programming, and many other development models is inside!

Beginning Database Design Solutions

The database is the foundation on which all other development rests. Make your foundation solid!

This concise introduction teaches database design concepts, methods, and techniques of high-quality database design. You’ll explore creating an initial logical design and refining it into a superior database that meets users’ requirements. Plus, you’ll see how to implement the design using specific types of database platforms and build databases using SQL scripts. Each chapter begins with a list of topics that will be covered, closes with a summary that provides the key points described in the chapter, and includes a list of review questions and a series of helpful exercises.

Other Books

If you would rather read something less technical, perhaps just to take your mind off of current affairs, consider the books described on my Favorite Books page. I haven’t kept that page up to date very well, particularly the Currently Reading section, partly because if I included every book that I like the page would be enormous. Still, you may be able to find something there that you like.


Follow me on Twitter   RSS feed   Donate




Posted in books | Tagged , , , , , | 2 Comments

Recommended Book on CD: “Fool” by Christopher Moore

Until recently my job required me to drive a lot. A whole lot. To avoid boredom I’ve been listening to books on CD. So far the best books I’ve listened to are those by Christopher Moore. Not only does Moore write ridiculously funny books, but he also picks the most amazing readers to put his books on CD.

This book follows the story of Pocket, a jester in the service of King Lear. If the name Lear sound familiar, that’s not a coincidence. The book is based on Shakespeare’s play King Lear with references to other plays thrown in. The plot is full of Shakespearean-style deceit and plot twists, together with Moore’s trademark general silliness and bawdy banter. If you’re easily offended by casual naughtiness, skip this book. (And most of Moore’s other books, too, for that matter.)

One thing I’ve learned while listening to books on CD is that the reader can make or break the book. One reader for another book made all male characters sound either whiny or like complete doofuses. Another reader made all non-American characters sound Russian whether they were Russian, French, or Middle Eastern.

Euan Morton does an amazing job reading Fool. Every character has a distinct voice that’s easy to distinguish from the others, his pace is fast enough to hold your attention, and his pronunciation and emphasis make the book simple to understand.

One extra benefit that I did not anticipate is that listening to the book made it easier for me to follow the relatively complicated plot. I have read this book before in print form, but I could only read it in relatively short chunks and I sometimes found it hard to keep track of what was happening. For some reason listening to the book made it easier for me to follow. That might just be me, but consuming the book in a new format gave me a much better appreciation of it.

As I mentioned, if you don’t like bawdy humor, give this book a pass. But if you like general silliness in a Shakespearean setting, this is a great listen.


Follow me on Twitter   RSS feed   Donate




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

Animate maze solving, version 1

[animate maze solving]

The post Solve mazes in C# solves mazes very quickly, but it only shows you the final path from the start point to the end point. It might be nice to make a program to animate maze solving so you can see the paths that it tries before it finds the final solution.

To use the program, enter the maze’s width and height, and then click Create. After you create the maze, left click to set the start point and right click to set the end point. After you select the start and end points, the program searches for a solution while displaying the paths that it considers.

[Essential Algorithms]
Note that this algorithm is similar to those described in my book Essential Algorithms, Second Edition. That book explains many other algorithms for finding paths through networks such as the mazes used here.

Approaches

One approach would be to save all of the paths that the program tries in some sort of list. Then the program could use a timer to loop through the saved paths and display them. Unfortunately the list of paths could be quite long. For example, in order to solve the maze shown at the top of this post, the program examined 723 paths. That’s still a manageable number, but for larger mazes the program would use a lot of memory to store the paths.

One of the bigger problems with displaying paths as they are found is that the program uses recursion to find them. To display the paths, the program would need to pause while inside a possibly deep recursive search, display the current path, and then resume the recursive execution. This post and the next two show different approaches to displaying paths while searching for them.

This post uses a trick that allows a method to return an enumeration. That lets the method return a result to the calling method and then resume execution.

Code

After you select the maze’s start and end points, the program executes the following StartSolving method to search for a solution.

private int NumPaths = 0;
private bool FoundSolution = false;
private List<MazeNode> Path = null;

// Start solving the maze.
private void StartSolving()
{
    NumPaths = 0;

    // Remove any previous results.
    Path = new List<MazeNode>();
    foreach (MazeNode node in Nodes)
        node.InPath = false;

    // Make the nodes define their neighbors.
    foreach (MazeNode node in Nodes)
        node.DefineNeighbors();

    // Start at the start node.
    Path.Add(StartNode);
    StartNode.InPath = true;

    // Solve recursively.
    FoundSolution = false;
    Running = true;
    foreach (List<MazeNode> test_path in Solve(EndNode, Path))
    {
        NumPaths++;

        Path = test_path;
        picMaze.Refresh();
        Thread.Sleep(Interval);
        Application.DoEvents();

        if (!Running) break;
    }
    Running = false;

    // Show the result.
    picMaze.Refresh();
    Console.WriteLine("Examined " + NumPaths.ToString() + " paths.");
}

This method clears any previous path and builds the maze network. It sets FoundSolution to false to indicate that the program has not yet found a solution. It also sets Running to true to indicate that the program is still running. You’ll see how those variables are used shortly.

The most interesting part of the method is its foreach loop. That loop makes the program loop over the values returned by the Solve method described shortly.

For each path returned by the Solve method, the code sets variable Path equal to the latest test path. It then refreshes the picMaze PictureBox control to show the current path. (Download the example to see how it draws the path.)

The method then calls Thread.Sleep to pause the program so you can see the path. After the program wakes up, the program calls Application.DoEvents so it can process any pending events. In particular that allows the program to notice if you create a new maze, click to set new start or end points, or close the program.

If the Running variable is false, then you have stopped the program. In that case, the StartSolving method breaks out of its loop so the method ends.

If you press the Create button, click to set new start or end points, or close the program, the program calls the following StopRunning method.

// Stop running.
private void StopRunning()
{
    Running = false;
}

This code simply sets Running to false to tell the StartSolving method to break out of its loop.

One particularly interesting time when the program calls StopRunning is when you try to close the program’s form. When you do that, the Form1_FormClosing event handler calls StopRunning. If you don’t do that, then the program knows that it should close but it continues executing its search. The form disappears but its code keeps running. Comment out the call to StopRunning in the Form1_FormClosing event handler to see this strange affect.

The example’s final interesting new piece of code is the following Solve method. You may recall that this method returns an enumeration of test paths that the StartSolving method uses in its foreach loop.

private IEnumerable<List<MazeNode>> Solve(
    MazeNode end_node, List<MazeNode> path)
{
    // Yield this path.
    yield return path;

    // See if we have reached the end node.
    MazeNode last_node = path[path.Count - 1];
    if (last_node == end_node)
    {
        FoundSolution = true;
        yield break;
    }

    // Try each of the last node's children in turn.
    foreach (MazeNode neighbor in last_node.Neighbors)
    {
        if (!neighbor.InPath)
        {
            path.Add(neighbor);
            neighbor.InPath = true;

            foreach (List<MazeNode> test_path in Solve(end_node, path))
                yield return test_path;
            if (FoundSolution) yield break;

            neighbor.InPath = false;
            path.RemoveAt(path.Count - 1);

            // Redraw the path without this latest node.
            yield return path;
        }
    }
}

This method uses a neat little trick that allows a method to return the items in an enumeration one at a time. Notice that it is declared to return an IEnumerable of lists of MazeNode objects. Each item in the enumeration is a list of nodes that represents a test path.

The method takes as a parameter the path that it should examine. The method returns that path and then explores the paths leading out of the end of that path.

The code starts by using a yield return statement to return the initial path. The yield return statement pauses the Solve method and returns control to the calling method. The calling method might be another call to Solve.

If you look a bit farther along in the Solve method’s code, you’ll see where the method calls itself. When it does, it loops through the values returned by the recursive call and uses yield return to return them higher up the recursive call stack.

The recursive calls use yield return to pass values up the call stack until they reach the StartSolving method, and that method displays the current path.

At that point, control returns to the Solve method that first called yield return and the method resumes.

After the yield return statement, the Solve method checks to see if it has found the maze’s end point. If it has, then the code sets FoundSolution to true. It then calls yield break to end its enumeration and return control to the calling method.

After checking to see if it has found a complete path, the method loops through the neighbors of the current path’s last node. For each of those neighbors, the code checks the neighbor’s InPath value to see if the node is already in the path. (That happens if the neighbor is the current path’s second-to-last node. This check prevents the path from doubling back on itself.) If the node is not in the path, the method tries adding the neighbor to the path.

The code adds the neighbor to the current path list and sets the neighbor’s InPath value to true. The method then recursively calls itself and loops through the paths that the recursive call returns. It calls yield return to return each of the paths returned by the recursive call.

After it finishes examining paths via the neighboring nodes, the method checks the FoundSolution variable to see if a solution has been found. If a path has been found, the method calls yield break to finish end enumeration. Note that in this case the method does not remove the current neighbor from the path so the path returned to the calling method includes that neighbor. In fact, the recursive calls that this instance of the method made may have left many other nodes added to the end of the initial path.

If the program has not yet found a complete path, the code sets the current neighbor’s InPath value to false to remove the node from the path. The code also removes that node from the end of the Path list.

Finally the method calls yield return to return the original path without the neighbor added at the end. That makes the program display the initial path, then display paths that extend the initial path via neighbor nodes, and finally backtrack to the initial path.

Summary

I know this is a bit confusing, so here’s a summary. The Solve method is declared to return an IEnumerable<List<MazeNode>>. The method can then use yield return to return items for the enumeration.

The StartSolving method loops through the paths returned by the enumeration. That method could break out of its loop at any time, although in this example it does not.

When it calls itself recursively, the Solve method loops through the paths returned by the recursive call and uses yield return to return them. That adds them to its own enumeration.

When the method finds a path from the start point to the end point, it uses yield break to end its enumeration. It uses the variable FoundSolution to tell instances of the method farther up the call stack that the solution has been found so they know to end their enumerations.

There are a few key steps inside the StartSolving method’s foreach loop. Each time through the loop, the method displays the current path, sleeps for a while, calls Application.DoEvents, and then checks Running to see if it should break out of the loop early. That allows the program to stop the search if you click on the maze, click Create, or close the form.

Download the example and experiment with it to see how it works and to see additional details. My next few posts show other ways to manage the trick of displaying paths while continuing a recursive search for a solution path.


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in algorithms, drawing, graphics, mathematics | Tagged , , , , , , , , , | 2 Comments