Draw a logarithmic spiral in C#

[spiral]

The post Draw an Archimedes spiral in C# uses the equation r = A˙θ to generate the points on a spiral. This example is almost exactly the same except it uses the equation to r = A˙eB˙θ to generate its points.

That equation leads to another small issue. When θ is 0, the eB˙θ becomes 1 so r = A. That means the spiral isn’t at its center point.

You can generate points closer to the center if you consider negative values for θ. The question then becomes, “How small does θ need to be?”

If we set θ small enough to make r equal to 0.1, then the resulting point will be less than one pixel away from the spiral’s center. To do that, we solve the equation 0.1 = A˙eB˙min_theta for min_theta. The result is min_theta = ln(0.1 / A) / B.

The new example is almost exactly the same as the previous example’s version. The only real change is in the GetSpiralPoints method, which uses the following code fragment to generate points on a spiral.

// Return points that define a spiral.
private List GetSpiralPoints(...)
{
    ...
    for (float theta = min_theta; ; theta += dtheta)
    {
        // Calculate r.
        float r = (float)(A * Math.Exp(B * theta));

        ...

        // If we have gone far enough, stop.
        if (r > max_r) break;
    }
    return points;
}

This code calculates min_theta as described above. It then makes variable theta loop starting from min_theta. The code uses the new formula to calculate r.

As in the previous example, the loop continues until the calculated value for r exceeds the maximum necessary value, at which point the method breaks out of its loop and returns the spiral’s points.

The rest of the example is the same as the previous one. Download the program and see the previous example for additional details.


Download Example   Follow me on Twitter   RSS feed   Donate




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

Draw a filled spiral in C#

[spiral]

My post Draw an Archimedes spiral in C# explained how to draw multiple Archimedes spirals starting at a common center point. This post shows how you can fill the spaces between the spirals with colors.

The basic idea is to make a polygon that follows the points along one spiral and then comes back along the reversed points from an adjacent spiral. That much would be interesting enough, but there are three details involving alignment, ending distance, and filling that make this extra tricky.

Alignment

[spiral]

In the previous example, each spiral expands until it its radius was larger than the distance from the spiral’s center to the farthest corner of the drawing area. Because the spirals use different offsets, they span different angles. That means the end of one spiral may be far from the beginning of the next. The picture on the right shows the result. It’s interesting, but not what we’re after.

One solution is to calculate the largest angle max_theta that any spiral must reach to surround the drawing area. Then you can generate points on each spiral until the variable theta plus the spiral’s offset exceeds max_theta.

The equation for an Archimedes spiral is r = A * θ, so solving for θ gives θ = r / A. If we plug in the distance to the farthest corner of the drawing area, we get max_theta = max_distance / A.

Now if each spiral ends when its theta + offset values exceeds max_theta, then the spiral ends will be near each other so they should form usable polygons. That leads to the second problem.

Ending Distance

[spiral]

In the earlier example, a spiral expanded until its radius was larger than the distance from the spiral’s center to the farthest corner of the drawing area. The picture on the right shows what happens if the spirals are only extended that far. This problem actually has two features.

First, some of the spirals don’t go far enough. If you look closely at the picture, you can probably guess that purple band should extend and cut into the drawing rectangle again in its lower left corner. The problem is that this spiral starts pointing upward, so doesn’t go as far around the circle as the red band, which starts pointing to the right.

A second potential problem is that the filled areas must include the area outside of the outermost spiral. If not only need to extend the second spiral to define the outer
edge of the purple band, we also need to extend the second and possibly third spirals to define the outer edges of the other bands.

We can do all of that quite easily by adding 2 π to max_theta to make every spiral take another lap around the center.

Filling

[spiral]

The final problem deals with the way the bands are filled. The obvious approach is to fill the area between spiral i and spiral i + 1. You can use the modulus operator (%) to wrap around to the beginning when you reach the last spiral. Unfortunately, even though the spirals all start at the same center, the first spiral isn’t adjacent to the last one. If you fill the area between those two spirals, you get the picture on the right.

The example solves this problem by simply creating one extra spiral outside all of the others. For example, if you want to draw three spirals, then the program creates four. Then, instead of filling the area between the first and last spirals, it fills the area between spiral number three and spiral number four.

The Program

This example uses the GetSpiralPoints method to generate the points on a spiral. That method is similar to the one used by the previous example. The only difference is that the previous version expands the spiral until r is big enough to cover the drawing rectangle, while the new version expands the spiral until theta reaches max_theta. See the previous example for a description of that method.

This example’s other main piece of code is the following Paint event handler.

// Draw the spiral(s).
private void picSpiral_Paint(object sender, PaintEventArgs e)
{
    e.Graphics.Clear(picSpiral.BackColor);
    e.Graphics.SmoothingMode = SmoothingMode.AntiAlias;
    try
    {
        float A = float.Parse(txtA.Text);
        int num_spirals = int.Parse(txtNumSpirals.Text);

        // Angular spacing between different spirals.
        float d_start = (float)(2 * Math.PI / num_spirals);

        // The angle where the next spiral starts.
        float start_angle = 0;

        // Center point.
        PointF center = new PointF(
            picSpiral.ClientSize.Width / 2,
            picSpiral.ClientSize.Height / 2);

        // Draw axes.
        e.Graphics.DrawLine(Pens.Black,
            center.X, 0,
            center.X, picSpiral.ClientSize.Height);
        e.Graphics.DrawLine(Pens.Black,
            0, center.Y,
            picSpiral.ClientSize.Width, center.Y);

        // Draw the spiral on only part of the PictureBox.
        Rectangle rect = new Rectangle(25, 50, 150, 150);

        // Find the maximum distance to the rectangle's corners.
        float max_dist = Distance(center, rect);

        // Calculate the maximum theta value that we need to go to.
        float max_theta = max_dist / A + 2 * (float)Math.PI;

        // Get points defining the spirals.
        List<List<PointF>> spiral_points = new List<List<PointF>>();

        // Get the spirals' points.
        for (int i = 0; i < num_spirals + 1; i++)
        {
            spiral_points.Add(GetSpiralPoints(
                center, A, start_angle, max_theta));
            start_angle += d_start;
        }

        // Fill the areas between the spirals.
        for (int i = 0; i <= num_spirals; i++)
        {
            // Make a list holding the next spiral's points.
            List<PointF> points = new List<PointF>(spiral_points[i]);

            // Add the following spiral's points reversed.
            List<PointF> points2 =
                new List<PointF>(spiral_points[i + 1]);
            points2.Reverse();
            points.AddRange(points2);

            e.Graphics.FillPolygon(
                SpiralBrushes[i % SpiralBrushes.Length],
                points.ToArray());

            // Optional: Outline the spiral's polygon.
            using (Pen pen = new Pen(Color.Black, 1))
            {
                e.Graphics.DrawLines(pen, points.ToArray());
            }
        }

        // Draw the target rectangle.
        e.Graphics.DrawRectangle(Pens.Black, rect);
    }
    catch (Exception ex)
    {
        MessageBox.Show(ex.Message);
    }
}

This method reads the parameters that you entered and calculates the angular offsets between the spirals as in the previous example. It also finds the drawing area’s center point, draws axes, and creates a drawing rectangle as before.

The program then finds the maximum distance from the spiral’s center to the corners of the drawing area. Next, it plugs r = max_dist in the equation r = a * theta and solves for theta. That gives it the largest value of theta that it needs to use. It saves that value in max_theta.

Next, the code creates a list of lists to hold the points for the spirals. It then enters a loop where it calls GetSpiralPoints to find each spiral’s points and it adds them to the list. Notice that in this loop i runs from 0 to num_spirals so it creates num_spirals + 1 spirals.

After it has all of the spirals’ points, the method uses a loop to fill the spaces between them as. As described earlier, it fills the areas between adjacent spirals up to the extra spiral that it created at the end of the others.

To fill an area, the code makes a new points list initialized with the points for spiral number i. It then creates another list points2 holding the next spiral’s points, reverses that list, and add it to the end of the points list. The code then fills that area and optionally outlines it.

The program includes a few other details that are relatively straightforward. Download the example program to see those details.


Download Example   Follow me on Twitter   RSS feed   Donate




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

New Book: The Modern C# Challenge

[books]

My latest book, The Modern C# Challenge, is now available. It’s a collection of 100 programming challenges that let you test your ability in a wide variety of programming topics, many of which are not usually covered in traditional programming books. Example solutions are included for all of the problems and many demonstrate important programming concepts that can help you get the best performance out of your normal programming challenges.

To learn more about the book at Amazon, look below the buying options tabs for the “Key Features” heading and click the “Read more” link. The book is available for Kindle now and should be available in paperback on February 11, 2019.

Here’s the table of contents in brief.

  1. Mathematics
  2. Geometry
  3. Dates and Times
  4. Randomization
  5. Strings
  6. Files and Directories
  7. Advanced C# and .NET Features
  8. Simulations
  9. Cryptography

Some of the topics include files and directories, geometry, simulations, randomization, the yield keyword, factoring, prime factors, simulations, dynamic programming, statistics, combinations, permutations, recursion, Fibonacci numbers, binomial coefficients, greatest common divisors and least common multiples, amicable numbers, root finding, solving systems of linear equations, calculating areas, Monte Carlo simulation, convexity testing, working times with time zones, random walks, Roman numerals, generating passwords, making thumbnails, and cryptography.


Follow me on Twitter   RSS feed   Donate




Posted in algorithms, books, files, mathematics, puzzles | Tagged , , , , , , , , , , , , , , , , , , , , , , , | 1 Comment

Draw an Archimedes spiral in C#

[spiral]

An archimedes spiral is defined by the polar coordinate equation r = A * θ. It’s just as simple as that, and this would be a significantly shorter post except for one question: how do you know how big you need to make θ to make the spiral fill the drawing area? You cannot simply continue drawing the spiral until it leaves the drawing area because it comes back as it cuts through the drawing area’s corners.

For example, in the picture at the top of this post, the red spiral leaves the black rectangle, cuts back into it before reaching the next corner, leaves again shortly after that corner, misses a corner entirely, cuts the next two corners, and then grows too large to intersect the rectangle after that.

The distance from a point on the spiral to the spiral’s center is simply r. In the Archimedes spiral, r increases as θ increases, so once r is too big to intersect the drawing area, it never goes back, and that gives us the test we need. Simply find the corner of the drawing area that is farthest from the spiral’s center. When r is greater than the distance to that corner, the spiral has gone far enough.

The example program uses the following method to generate a spiral’s points.

// Return points that define a spiral.
private List<PointF> GetSpiralPoints(
    PointF center, float A,
    float angle_offset, float max_r)
{
    // Get the points.
    List<PointF> points = new List<PointF>();
    const float dtheta = (float)(5 * Math.PI / 180);    // Five degrees.
    for (float theta = 0; ; theta += dtheta)
    {
        // Calculate r.
        float r = A * theta;

        // Convert to Cartesian coordinates.
        float x, y;
        PolarToCartesian(r, theta + angle_offset, out x, out y);

        // Center.
        x += center.X;
        y += center.Y;

        // Create the point.
        points.Add(new PointF((float)x, (float)y));

        // If we have gone far enough, stop.
        if (r > max_r) break;
    }
    return points;
}

This method uses a loop to generate the points on the spiral. It calculates r, uses the PolarToCartesian method to convert the polar coordinates (r, θ) into Cartesian coordinates (x, y), adds the spiral’s center to the point to translate it into the correct position, and then adds the new point to the list.

Notice that the code adds the angle offset to theta when it calls PolarToCartesian. That makes the spiral start in a particular direction so the program can draw multiple interlaced spirals.

Next, if r is greater than the distance to the farthest corner of the drawing rectangle max_r, the code breaks out of its loop and returns the spiral’s points.

The following code shows the PolarToCartesian method.

// Convert polar coordinates into Cartesian coordinates.
private void PolarToCartesian(float r, float theta,
    out float x, out float y)
{
    x = (float)(r * Math.Cos(theta));
    y = (float)(r * Math.Sin(theta));
}

This method simply converts polar coordinates into Cartesian coordinates.

The only remaining code of any real interest is the following

// Pens to use for different spirals.
private Pen[] SpiralPens =
{
    Pens.Red, Pens.Green, Pens.Purple,
    Pens.Blue, Pens.Magenta, 
};

// Draw the spiral(s).
private void picSpiral_Paint(object sender, PaintEventArgs e)
{
    e.Graphics.Clear(picSpiral.BackColor);
    e.Graphics.SmoothingMode = SmoothingMode.AntiAlias;
    try
    {
        float A = float.Parse(txtA.Text);
        int num_spirals = int.Parse(txtNumSpirals.Text);

        // Angular spacing between different spirals.
        float d_start = (float)(2 * Math.PI / num_spirals);

        // The angle where the next spiral starts.
        float start_angle = 0;

        // Center point.
        PointF center = new PointF(
            picSpiral.ClientSize.Width / 2,
            picSpiral.ClientSize.Height / 2);

        // Draw axes.
        e.Graphics.DrawLine(Pens.Black,
            center.X, 0,
            center.X, picSpiral.ClientSize.Height);
        e.Graphics.DrawLine(Pens.Black,
            0, center.Y,
            picSpiral.ClientSize.Width, center.Y);

        // Draw the spiral on only part of the PictureBox.
        Rectangle rect = new Rectangle(25, 50, 150, 150);

        // Find the maximum distance to the rectangle's corners.
        float max_r = Distance(center, rect);

        // Draw the spirals.
        for (int i = 0; i < num_spirals; i++)
        {
            List<PointF> points =
                GetSpiralPoints(center, A, start_angle, max_r);
            e.Graphics.DrawLines(SpiralPens[i % SpiralPens.Length],
                points.ToArray());
            start_angle += d_start;
        }

        // Draw the target rectangle.
        e.Graphics.DrawRectangle(Pens.Black, rect);
    }
        catch (Exception ex)
    {
        MessageBox.Show(ex.Message);
    }
}

This code defines an array of colors to use when drawing spirals.

The picSpiral control’s Paint event draws the spirals. It gets the user-entered parameters. It then divides 2π radians by the number of spirals to get the angular spacing between the interlocked spirals.

The code finds the center of the PictureBox and uses it as the center of its spirals. It then draws axes running through that center and makes a test rectangle where it will fit the spirals.

Next, the code calls the Distance method to find the distance to the drawing area’s farthest corner. It then enters a loop to draw each of the spirals, increasing each one’s angle offset by d_start so they start out pointing in different directions. The code calls the GetSpiralPoints method to get the spiral’s points and then uses the Graphics object’s DrawLines method to draw the spiral.

The code finishes by drawing the target rectangle so you can see that the spirals are big enough to cover the rectangle.

The program includes a few other details such as the Distance method that are relatively straightforward. Download the example program to see additional details.


Download Example   Follow me on Twitter   RSS feed   Donate




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

Make a custom component in C#


[custom component]

There are a couple of ways that you can approach this problem. In this post, I’ll describe two: subclassing from Component and making a control that is invisible at runtime.

Subclassing From Component

To make a true component, simply make a class that inherits from the System.ComponentModel.Component class. If you’re using a newer version of Visual Studio, open the Project menu, select Add Component, enter a component name (I called this one MyComponent), and click Add.

If you’re using an older version of Visual Studio, then the Project menu may not have an Add Component command. In that case, simply create a new class and make it inherit from System.ComponentModel.Component.

To change the icon that the component displays in the Component Tray, add a ToolboxBitmap attribute and specify the name of the 16×16 pixel image file that the component should use.

You can include the image file in a couple of ways. For this example, I embedded the file in the project. To do that, open the Project menu, select Add Existing Item, select the file, and click Add. Then select the file in Project Explorer and set its Build Action property to Embedded Resource.

When you build the project, the component will add itself to the Form Designer’s Toolbox. Unfortunately, it won’t display its toolbox icon. (Yeah, I know.) To make it display its icon in the Toolbox, you must add it to the Toolbox manually.

To do that, right-click on the Toolbox and select Choose Items. Click the Browse button and select the compiled project that contains the component. (You may need to uncheck the component in the Choose Toolbox Items dialog first and then re-add the compiled project. This doesn’t seem to work very reliably, at least for me. Perhaps it works in newer versions of Visual Studio.)

The following code shows the example’s MyComponent class.

using System.ComponentModel;
using System.Windows.Forms;

namespace howto_custom_component
{
    [System.Drawing.ToolboxBitmap(typeof(MyComponent), "Small Smiley.png")]
    public class MyComponent : Component
    {
        public void SayHello()
        {
            MessageBox.Show("Hello", "MyComponent", MessageBoxButtons.OK);
        }
    }
}

In addition to the ToolboxBitmap attribute, this code defines a SayHello method that simply displays a message box.

Making a Control that is Invisible at Runtime

Another approach is to make a control that behaves sort of like a component. With this approach, the control displays itself on the form at design time but is invisible at runtime. (Sort of like a VB 6 component, if you can remember that far back.)

To do that, open the Project menu and select Add User Control. Enter a name for the control (I used the name Smiler) and click Add. Then, on the Control Designer, add any constituent controls that you want the custom component to contain.

To make the component display something at design time, set its BackgroundImage property to an image. Set its Size property to match the image’s size. In this example, I used a 32×32 pixel image, so I set the Size property to 32, 32.

Next, add code similar to the following to handle the control’s Resize event.

// Size the control to fit its background image.
private void Smiler_Resize(object sender, EventArgs e)
{
    Size = BackgroundImage.Size;
}

This code sets the control’s size to match that of its background image. When you add a Smiler to a form at design time, it will always have this size.

Next, add a Load event handler similar to the following to the control class.

// Hide the control at runtime.
private void Smiler_Load(object sender, EventArgs e)
{
    if (!DesignMode) Visible = false;
}

This method checks the component’s inherited DesignTime property to see if the control is running at design time or runtime. Those are the times for the form containing the control. When you place a control on a form, that’s design time. When you run the program, that’s runtime.

If the control is in runtime, the code sets its Visible property to false to hide it.

The example’s also defines the following SayHi method.

// Display a hello message box.
public void SayHi()
{
    MessageBox.Show("Hi", "Hi", MessageBoxButtons.OK);
}

This method simply displays a message box that says, “Hi.”

Using the Component

When you build the solution, the component or control should appear in the Form Designer’s Toolbox. You can then place them on the form as usual.

NOTE: When you download the example project, you must build it before the component and control will be usable.

The example program displays a button that executes the following code.

private void btnSayHi_Click(object sender, EventArgs e)
{
    smiler1.SayHi();
    myComponent1.SayHello();
}

This code calls a Smiler control’s SayHi method and then calls a MyComponent object’s SayHello method.

The left part of the picture at the top of this post you can see the form in the Form Designer. On the form, you can see the Smiler control named smiler1. Below the form, you can see the MyComponent component named myComponent1 in the Component Tray.

On the right side of the picture, you can see the form at runtime. Here the smiler1 control is invisible. (The MyComponent component is also invisible, but that’s less impressive. You would expect a component to be hidden at runtime.)

In the middle of the picture, you can see the smiler1 control’s dialog.

Download the example program to experiment with it and to see additional details.


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in controls | Tagged , , , , , , , | 1 Comment

Tile a board with randomly colored trominoes in C#

[example]

The post Tile a board with colored trominoes in C#explains how to color a tromino filing so no two adjacent trominoes share the same color. That example basically tried every possible color for each of the trominoes until it found one that worked.

Unfortunately, that approach makes the algorithm prefer colors near the beginning of the color list. That’s not a big problem with the trominoes because the tiling pattern requires the program to use a lot of colors, but the result can look strange when you color some other maps. In those cases, the coloring uses the first few colors the most and only occasionally uses the other colors. For example, the result might be a map that uses lots of yellow and blue areas and only one or two red areas.

This example examines the allowed colors in random order so it will use more of the colors that are later in the list of allowed colors. The program also uses more colors than the previous version, so the trominoes look more randomly colored.

The only change to the program is in the following code snippet where the program tries different colors for a tromino.

// Try each of the colors for this Chair.
Chair this_chair = Chairs[start_chair];
int[] color_nums =
    Enumerable.Range(0, Chair.BgBrushes.Length).ToArray();
color_nums.Randomize();
foreach (int color_num in color_nums)
{
    if (this_chair.ColorAllowed(color_num))
    {
        this_chair.BgBrushNum = color_num;
        if (FindColoring(start_chair + 1)) return true;
    }
}

This code creates an array named color_nums that contains the numbers 0, 1, 2, up to one less than the number of colors in the Chair.BgBrushes array. It then uses the Randomize extension method described shortly to randomize the color_nums array. The code then loops through the randomized colors and tries each until it finds one that works.

The following code shows the Randomize extension method.

// Randomize an array.
public static void Randomize<T>(this T[] items)
{
    // For each spot in the array, pick
    // a random item to swap into that spot.
    for (int i = 0; i < items.Length - 1; i++)
    {
        int j = Rand.Next(i, items.Length);
        T temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }
}

This method loops through the spots in the array. For each spot, it picks a random following spot and swaps the items in those two positions. When it is done, each of the array’s items may have been swapped into any of the array’s positions with equal probability.

See the previous example and download this example’s program to see additional details.


Download Example   Follow me on Twitter   RSS feed   Donate




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

Tile a board with colored trominoes in C#

[example]

The post Tile a board with trominoes in C# explains how to tile a board with a missing square with trominoes. This post shows how to color the trominoes so no two adjacent ones share the same color.

The four-color theorem states that you can color any map (separation of a plane into contiguous regions) with only four colors. (The theorem was proposed in 1852 but only proven in 1976.) Unfortunately the proof is very long, complicated, and computer assisted, so it does not give a practical method for finding a coloring.

My book Essential Algorithms describes several approaches for coloring maps including a five-coloring algorithm.

Another approach is to simply iterate through every possible combination of colors until you find one that works. In general, this can be slow. If a map has N regions and you want to use C colors, then there are CN possible combinations of colors and that can be a very large number. For example, there are currently 195 countries in the world. If you want to color them with four colors, then there are 4195 ≈ 2.5×10117.

Fortunately, many maps are smaller and many are relatively easy to color so the program doesn’t need to examine every possible combination.

To color the trominoes, this program must perform two main tasks: finding the trominoes’ neighbors and finding a valid coloring.

Finding the Trominoes’ Neighbors

The previous example created an array of PointF to represent each tromino. To determine which trominoes are neighbors, you could loop through every pair of trominoes and then see if they share a common edge. To see if they share an edge, you could see if any of the adjacent pairs of points in the first tromino matched any adjacent pair in the second tromino. When you considered a pair of edges, you would need to check to see if one of the edges was backwards. You would also need to check for approximate matches caused by rounding errors.

That all seemed inelegant and a lot of work, so I took a different approach. When the program creates a chair shape, it knows which rows and columns on the board that chair occupies. To make it easier to find neighbors, I created a Chair class to represent the trominoes. The class stores a chair’s points and the squares that it occupies.

The following code shows the beginning of the Chair class.

public class Chair
{
    public static Brush[] BgBrushes =
    {
        Brushes.Red, Brushes.Blue, Brushes.Yellow,
    };

    public int Number;
    public int BgBrushNum = 0;
    public List<Point> Squares = new List<Point>();
    public PointF[] Points;
    public List<Chair> Neighbors;

The class declares a static array of brushes that it will use to color the trominoes. I believe (but have not proven formally) that you can always color a tromino tiling with only three colors, so the array only contains red, blue, and yellow.

Next, the class declares chair properties such as the chair’s number and brush index in the array. The Squares list holds the squares that the chair occupies. The X and Y coordinates of the points in the list give the squares’ rows and columns on the board.

The Points array holds the chair’s polygon points as before. The Neighbors list will indicate the Chairs that share an edge with this one.

The class also defines methods to perform such tasks as drawing the chair. Download the example and look at the code to see how that works. For now, I only want to described two more methods.

The following AreNeighbors method returns true if two squares share a common edge.

// Return true if the two squares are neighbors.
public static bool AreNeighbors(Point p1, Point p2)
{
    if ((p1.X == p2.X) && (Math.Abs(p1.Y - p2.Y) == 1)) return true;
    if ((p1.Y == p2.Y) && (Math.Abs(p1.X - p2.X) == 1)) return true;
    return false;
}

If the two squares are in the same row and their columns differ by one, then they are adjacent horizontally so the method returns true.

Similarly, if the two squares are in the same column and their rows differ by one, then they are adjacent vertically so the method returns true.

If neither of those tests makes the method return true, then the squares are not adjacent so the method returns false.

The second method is the following IsNeighbor method, which returns true if the current chair shares an edge with another chair.

// Return true if the two Chairs are neighbors.
public bool IsNeighbor(Chair other)
{
    foreach (Point p1 in Squares)
        foreach (Point p2 in other.Squares)
            if (AreNeighbors(p1, p2)) return true;
    return false;
}

This method simply loops through all of the squares occupied by both chairs and calls the AreNeighbors method to see if any of the squares are neighbors.

The main program uses the following FindNeighbors method to finds the trominoes’ neighbors.

// Find the Chairs' neighbors.
private void FindNeighbors()
{
    int num_chairs = Chairs.Count;

    // Create empty Neighbors lists.
    foreach (Chair chair in Chairs)
        chair.Neighbors = new List<Chair>();

    // Find neighbors.
    for (int i = 0; i < num_chairs - 1; i++)
    {
        for (int j = i + 1; j < num_chairs; j   ++)
        {
            if (Chairs[i].IsNeighbor(Chairs[j]))
            {
                Chairs[i].Neighbors.Add(Chairs[j]);
                Chairs[j].Neighbors.Add(Chairs[i]);
            }
        }
    }
}

The method first loops through its Chairs list, which holds a reference to each Chair object and sets each chair’s Neighbors list to an empty list.

Next, the code loops through every pair of distinct chairs and calls uses the Chair class’s IsNeighbor method to determine whether the two chairs are neighbors. If they are neighbors, the method adds each chair to the other’s Neighbors list.

Finding a Valid Coloring

After you know which trominoes are adjacent to which others, finding a coloring is just a matter of trying possibilities. The following FindColoring method starts the process.

// Find a coloring of the Chairs.
private void FindColoring()
{
    // Find the neighbors.
    FindNeighbors();

    // Give each Chair color number -1.
    foreach (Chair chair in Chairs) chair.BgBrushNum = -1;

    // Assign colors.
    if (!FindColoring(0))
        MessageBox.Show("Could not find coloring.");
}

The method first calls the FindNeighbors method described earlier. It then loops through the chairs and sets all of their BgBrushNum properties to -1 to indicate that they do not have an assigned color.

The method finishes by calling the following FindColoring method. It passes that method the parameter 0 to indicate that it should start assigning a color to the first chair.

// Find a coloring of the Chairs starting from Chair
// number start_chair Return true if we find a coloring.
private bool FindColoring(int start_chair)
{
    // If we are beyond the end of the Chairs list, we are done.
    if (start_chair == Chairs.Count) return true;

    // Try each of the colors for this Chair.
    int num_colors = Chair.BgBrushes.Length;
    Chair this_chair = Chairs[start_chair];
    for (int color_num = 0; color_num < num_colors; color_num++)
    {
        if (this_chair.ColorAllowed(color_num))
        {
            this_chair.BgBrushNum = color_num;
            if (FindColoring(start_chair + 1)) return true;
        }
    }

    // We failed to find a coloring. Backtrack.
    this_chair.BgBrushNum = -1;
    return false;
}

This method recursively assigns colors to chairs starting with chair number start_chair. The method first checks to see if it is finished. If chair_number equals the total number of chairs, then every chair has been assigned a color so the method returns true to indicate that it has found an assignment.

If the method is not finished, it loops through the numbers that represent the allowed color indices. In the example as it is written, the colors in the Chair.BgBrushes array have indices 0 through 2, so the loop ranges from 0 to 2.

Inside the loop, the code calls the current chair’s ColorAllowed method (described shortly) to see if that chair can have the color that is currently being examined by the loop. If the chair could have that color, the method tentatively assigns the chair that color and then recursively calls itself to assign the next chair’s color.

If the recursive call returns true, then it found a valid coloring so the method also returns true to unwind the recursion.

If the loop ends with none of the colors leading to a valid coloring, the method resets the chair’s color to -1 and returns false. A call higher up the call stack will change the color of the chair it is examining and the recursive calls will try again until they find a valid coloring or until all combinations have been tried unsuccessfully.

The Chair class defines the following ColorAllowed method, which returns true if the chair can have a certain color.

// Return true if this Chair could have this color number.
public bool ColorAllowed(int color_num)
{
    foreach (Chair chair in Neighbors)
        if (chair.BgBrushNum == color_num)
            return false;
    return true;
}

This method simply loops through the chair’s neighbors and returns false if any of those neighbors have the color color_num. If none of the neighbors have been assigned that color, the method returns true.

Conclusion

The program includes a few other details (such as the pieces described in the earlier post, but those are the most interesting new pieces. Download the example program to see additional details. You can also experiment with the program. See if you can find an instance where you need more than three colors to color the trominoes. Or post a comment if you figure out how to prove that three colors is enough.

In my next post, I’ll explain how you can randomize the colors. That allows the program to find more three-color arrangements or to use more than three colors.


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in algorithms, drawing, graphics, mathematics, recursion | Tagged , , , , , , , , , , , , , , , , , , | 1 Comment

Tile a board with trominoes in C#

[trominoes]

Trominoes are polyominoes of order three. That means they are polygons made up of three equal sized squares joined at their edges. There only are two kinds of trominoes: three squares joined in a line and three squares joined in an L shape. L-shaped trominoes also looks sort of like chairs, so that’s what I’ll call them here.

American mathematician Solomon W. Golomb devised Golomb’s Tromino Theorem, which states that you can tile any 2n×2n (n ≥ 1) chessboard that has one square removed with chair trominoes as shown in the picture at the top of this post.

The following sections describe the proof of Golomb’s Tromino Theorem and the code that the example program uses to find tilings.

Proof

You can prove the theorem by induction, and that proof leads to a method for finding a tiling. For the base case, consider a 21×21 board with one square removed. The following picture shows the four tilings that you might need to use depending on the location of the removed square.


[trominoes]

Now suppose the theorem applies for n and consider the case of n + 1 so the board has size 2n+1×2n+1. Divide the board into four sub-boards with size 2n+1×2n+1. One of the quadrants holds the missing square. Place a tromino in the center squares of the three other sub-boards as shown in red in the following picture. Now each sub-board has one missing square. Because the theorem applies for those smaller sub-boards, we know that we can find a tiling for them, and that gives a tiling for the full 2n×2n board.


[trominoes]

By induction, that means the theorem applies for boards of size 2n×2n for all n ≥ 1.

Setup Code

The code to find the trominoes tilings is surprisingly complicated. The following code shows variables that the program uses to understand the board size.

// The quadrant that holds the square to be ignored.
private enum Quadrants { NW, NE, SE, SW };

private int SquaresPerSide = 0;
private float SquareWidth, BoardWidth, Xmin, Ymin;

// The location of the missing square.
private int MissingX, MissingY;

private List<PointF[]> Chairs;

The Quadrants enumeration defines the four directions northwest, northeast, southeast, and southwest that we can use to keep track of a board’s quadrants.

The variable SquaresPerSide holds the number of squares on each side of the board. The variables SquareWidth, BoardWidth, Xmin, and Ymin hold values used to draw the board. For example, Xmin and Ymin give the upper left corner of the board.

Values MissingX and MissingY gives the row and column (starting from 0) of the missing square.

Finally, Chairs is a list of point arrays that represent the trominoes. For example, Chairs[0] is an array of points representing the first tromino.

When the program starts or when you click the Tile button, the following code finds a tiling.

// Make and solve a new board.
private void Form1_Load(object sender, EventArgs e)
{
    MakeBoard();
}
private void btnTile_Click(object sender, EventArgs e)
{
    MakeBoard();
}
private void MakeBoard()
{
    int n = int.Parse(txtN.Text);
    SquaresPerSide = (int)Math.Pow(2, n);

    // Set board parameters.
    SquareWidth = (picBoard.ClientSize.Width - 10f) / SquaresPerSide;
    float hgt = (picBoard.ClientSize.Height - 10f) / SquaresPerSide;
    if (SquareWidth > hgt) SquareWidth = hgt;
    BoardWidth = SquareWidth * SquaresPerSide;
    Xmin = (picBoard.ClientSize.Width - BoardWidth) / 2;
    Ymin = (picBoard.ClientSize.Height - BoardWidth) / 2;

    // Pick a random empty square.
    Random rand = new Random();
    MissingX = rand.Next(SquaresPerSide);
    MissingY = rand.Next(SquaresPerSide);

    // Solve the board.
    Chairs = new List<PointF[]>();
    SolveBoard(
        0, SquaresPerSide - 1,
        0, SquaresPerSide - 1,
        MissingX, MissingY);

    // Redraw.
    picBoard.Refresh();
}

The form’s Load event handler and the Tile button’s Click event handler call the MakeBoard method. That method gets the value for n that you entered in the text box and calculates the number of squares per side (2n).

Next, the method calculates the size that a square would have if the board fills the picture box horizontally. It also calculates the size a square would have if the board fills the picture box vertically, and sets SquareWidth to the smaller of the two sizes so the board will fit. It then uses the size to calculate Xmin and Ymin to center the board in the drawing area.

The method then uses a Random object to pick a random row and column to hold the missing square. It then creates a new Chairs list and calls SolveBoard to find a tiling. The method finishes by refreshing the picBoard picture box to show the solution.

SolveBoard

The following code shows the SolveBoard method.

// Solve the board.
private void SolveBoard(int imin, int imax, int jmin, int jmax,
    int imissing, int jmissing)
{
    // See if this is a 2x2 square.
    if (imax - imin == 1)
    {
        // It is a 2x2 square. Make its chair.
        Chairs.Add(MakeChair(imin, imax, jmin, jmax,
            imissing, jmissing));
        return;
    }

    // Not a 2x2 square. Divide into 4 pieces and recurse.
    int imid = (imin + imax) / 2;
    int jmid = (jmin + jmax) / 2;
    switch (QuadrantToIgnore(imin, imax, jmin, jmax,
        imissing, jmissing))
    {
        case Quadrants.NW:
            // Make the chair in the middle.
            Chairs.Add(MakeChair(imid, imid + 1, jmid, jmid + 1, imid, jmid));

            // Recurse.
            SolveBoard(imin, imid, jmin, jmid, imissing, jmissing);         // NW
            SolveBoard(imid + 1, imax, jmin, jmid, imid + 1, jmid);         // NE
            SolveBoard(imid + 1, imax, jmid + 1, jmax, imid + 1, jmid + 1); // SE
            SolveBoard(imin, imid, jmid + 1, jmax, imid, jmid + 1);         // SW
            break;
        case Quadrants.NE:
            // Make the chair in the middle.
            Chairs.Add(MakeChair(imid, imid + 1, jmid, jmid + 1, imid + 1, jmid));

            // Recurse.
            SolveBoard(imin, imid, jmin, jmid, imid, jmid);                 // NW
            SolveBoard(imid + 1, imax, jmin, jmid, imissing, jmissing);     // NE
            SolveBoard(imid + 1, imax, jmid + 1, jmax, imid + 1, jmid + 1); // SE
            SolveBoard(imin, imid, jmid + 1, jmax, imid, jmid + 1);         // SW
            break;
        case Quadrants.SE:
            // Make the chair in the middle.
            Chairs.Add(MakeChair(imid, imid + 1, jmid, jmid + 1, imid + 1, jmid + 1));

            // Recurse.
            SolveBoard(imin, imid, jmin, jmid, imid, jmid);                 // NW
            SolveBoard(imid + 1, imax, jmin, jmid, imid + 1, jmid);         // NE
            SolveBoard(imid + 1, imax, jmid + 1, jmax, imissing, jmissing); // SE
            SolveBoard(imin, imid, jmid + 1, jmax, imid, jmid + 1);         // SW
            break;
        case Quadrants.SW:
            // Make the chair in the middle.
            Chairs.Add(MakeChair(imid, imid + 1, jmid, jmid + 1, imid, jmid + 1));

            // Recurse.
            SolveBoard(imin, imid, jmin, jmid, imid, jmid);                 // NW
            SolveBoard(imid + 1, imax, jmin, jmid, imid + 1, jmid);         // NE
            SolveBoard(imid + 1, imax, jmid + 1, jmax, imid + 1, jmid + 1); // SE
            SolveBoard(imin, imid, jmid + 1, jmax, imissing, jmissing);     // SW
            break;
    }
}

This method’s parameters indicate what part of the full board that this method call must tile with trominoes. The parameters imin and imax give the smallest and largest column numbers of interest. Similarly, jmin and jmax give the smallest and largest row numbers of interest.

The parameters imissing and jmissing give the column and row of the square that is missing from this part of the board. Note that this square might actually be missing in the full board, or it might be a square that we should ignore while tiling this part of the board because it has already been covered by the red tromino in the earlier picture.

If the method is trying to tile a 2×2 board, it simply calls the MakeChair method described later to create a tromino for the board. It adds that tromino to the Chairs list and returns.

If the board is larger than 2×2, the code finds the row and column of the middle of the board. Because this calculation uses integer division, imid and jmid give the largest column and row in the upper left quadrant.

Next, the code calls the QuadrantToIgnore method described later to see which quadrant contains the square that we should ignore. The method uses a switch statement to determine how to position the red tromino and recursively call itself as shown in the earlier picture.

This is the trickiest section of code. If the calls are incorrect, the result isn’t a tiling and figuring out exactly what went wrong is very difficult. The best approach to this code is to just walk through it very carefully and make sure there are no mistakes the first time.

For each case, the code calls the MakeChair method to make a polygon for the red tromino shown in the earlier picture and adds that polygon to the Chairs list.

The SolveBoard method then calls itself recursively to tile the four sub-boards with trominoes. It adjusts the imin, imax, jmin, and jmax arguments to make the calls visit the sub-boards. It changes the imissing and jmissing arguments to make the recursive calls ignore the appropriate squares. For the sub-board that contains the square that the original call to SolveBoard was supposed to ignore, that recursive call still ignores that square. For the other sub-boards, the recursive call ignores the square covered by the red tromino in the earlier picture.

MakeChair

The MakeChair method returns an array of points representing a tromino within a 2×2 sub-board. It took me a while to find a nice solution that can draw any of the trominoes we might need. Instead of using a switch statement to return one of four complicated lists of points, I decided to make a single set of points representing the square on the left in the following picture.


[trominoes]

Then the method moves one of the corner points to the center of the sub-board. The picture on the right above shows how it modifies the points when the square to ignore is in the northeast quadrant. (The resulting polygon includes two points that it really doesn’t need in the middle of two of the chair’s sides, but they don’t hurt much so I won’t go to the trouble of removing them.)

The following code shows the MakeChair method.

// Make a chair polygon.
private PointF[] MakeChair(int imin, int imax,
    int jmin, int jmax, int imissing, int jmissing)
{
    // Make the initial points.
    float xmin = Xmin + imin * SquareWidth;
    float ymin = Ymin + jmin * SquareWidth;
    PointF[] points =
    {
        new PointF(xmin, ymin),
        new PointF(xmin + SquareWidth, ymin),
        new PointF(xmin + SquareWidth * 2, ymin),
        new PointF(xmin + SquareWidth * 2, ymin + SquareWidth),
        new PointF(xmin + SquareWidth * 2, ymin + SquareWidth * 2),
        new PointF(xmin + SquareWidth, ymin + SquareWidth * 2),
        new PointF(xmin, ymin + SquareWidth * 2),
        new PointF(xmin, ymin + SquareWidth),
    };

    // Push in the appropriate corner.
    PointF middle = new PointF(
        xmin + SquareWidth,
        ymin + SquareWidth);
    switch (QuadrantToIgnore(imin, imax, jmin, jmax,
        imissing, jmissing))
    {
        case Quadrants.NW:
            points[0] = middle;
            break;
        case Quadrants.SW:
            points[6] = middle;
            break;
        case Quadrants.NE:
            points[2] = middle;
            break;
        case Quadrants.SE:
            points[4] = middle;
            break;
    }

    return points;
}

The method first sets xmin and ymin to the X and Y coordinates of the sub-board’s upper left point. It then creates an array holding the points shown on the left in the earlier picture.

Next, the method finds the sub-board’s midpoint. It then calls the QuadrantToIgnore method described shortly to figure out which quadrant contains the square that we should ignore. It then uses a switch statement to move the appropriate corner point to the sub-board’s midpoint.

QuadrantToIgnore

The QuadrantToIgnore method determines which quadrant of a sub-board contains the square that you should ignore when tiling the sub-board with trominoes. The following code shows the method.

// Return the quadrant holding the square to be ignored for this square.
private Quadrants QuadrantToIgnore(int imin, int imax, int jmin, int jmax,
    int imissing, int jmissing)
{
    int imid = (imin + imax) / 2;
    int jmid = (jmin + jmax) / 2;
    if (imissing <= imid)      // West.
    {
        if (jmissing <= jmid) return Quadrants.NW;
        return Quadrants.SW;
    }
    else                        // East.
    {
        if (jmissing <= jmid) return Quadrants.NE;
        return Quadrants.SE;
    }
}

The method sets imid and jmid to the column and row at the center of the sub-board. Because the calculation uses integer division, imid and jmid give the largest column and row in the upper left quadrant.

The code then uses a simple set of if statements to determine which quadrant contains the missing square.

Drawing the Trominoes

The program’s last piece is the following Paint event handler, which draws the tilings trominoes.

// Draw the board.
private void picBoard_Paint(object sender, PaintEventArgs e)
{
    e.Graphics.Clear(picBoard.BackColor);
    e.Graphics.SmoothingMode = SmoothingMode.AntiAlias;

    // Draw the chairs.
    foreach (PointF[] points in Chairs)
    {
        e.Graphics.DrawPolygon(Pens.Red, points);
    }

    // Draw the missing square.
    float x = Xmin + MissingX * SquareWidth;
    float y = Ymin + MissingY * SquareWidth;
    e.Graphics.FillRectangle(Brushes.Black,
        x, y, SquareWidth, SquareWidth);
}

This code clears the Graphics object and prepares it to draw smoothly. It then loops through the trominoes in the Chairs list and draws each polygon in red.

The method finishes by filling the missing square with black.

Conclusion

The proof that a tiling with trominoes is possible is relatively straightforward, at least if you’re familiar with inductive proofs. The proof leads naturally to a recursive method to finding a tiling, but the details are a bit tricky. In particular, if you make any mistakes in the SolveBoard method’s recursive calls, the result isn’t a tiling and figuring out what went wrong is hard.

In my next post, I’ll explain how you can color the trominoes so that no two adjacent trominoes have the same color.


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in algorithms, drawing, graphics, mathematics, recursion | Tagged , , , , , , , , , , , , , , , , , | 1 Comment

Draw text wrapped to fit columns in C#


[draw text]

The post Draw aligned columns of data in C# shows one way to draw text in rows and columns. It uses the Graphics class’s MeasureString method to size the columns so they are big enough to display their data without wrapping.

In a comment, oghenez asked how you could wrap the data if it was too wide to fit in a column. This post explains how to do that.

For starters, the program cannot set the column widths by measuring the text. If it did that, it would make the columns wide enough to display all of the text. To avoid that, you need to somehow decide on the column widths yourself. This example uses the following code to define the column widths and text alignments.

// The column sizes and alignments.
private int[] ColWidths = { 200, 200, 90, 70, 130};
private StringAlignment[] VertAlignments =
{
    StringAlignment.Center,
    StringAlignment.Center,
    StringAlignment.Near,
    StringAlignment.Near,
    StringAlignment.Near,
};
private StringAlignment[] HorzAlignments =
{
    StringAlignment.Near,
    StringAlignment.Near,
    StringAlignment.Far,
    StringAlignment.Center,
    StringAlignment.Near,
};

The first statement initializes the ColWidths array, which indicates the widths that the columns should have in pixels. The rest of this code defines the vertical and horizontal alignments that the program should use to draw text in the different columns.

When the program’s PictureBox needs to redraw itself, the following code draws text for the values stored in the Values array.

// Display the data aligned in columns.
private void picColumns_Paint(object sender, PaintEventArgs e)
{
    e.Graphics.Clear(Color.White);
    e.Graphics.TextRenderingHint = TextRenderingHint.AntiAlias;

    using (StringFormat sf = new StringFormat())
    {
        using (Font font = new Font("Times New Roman", 12))
        {
            const int margin = 4;
            int y = margin;

            // Display the rows.
            foreach (string[] row in Values)
            {
                // Measure the row's entry heights.
                int num_cols = row.Length;
                int max_height = 0;
                for (int col_num = 0; col_num < num_cols; col_num++)
                {
                    SizeF col_size = e.Graphics.MeasureString(
                        row[col_num], font,
                        ColWidths[col_num] - 2 * margin);
                    int new_height = (int)Math.Ceiling(col_size.Height);
                    if (max_height < new_height)
                        max_height = new_height;
                }
                max_height += 2 * margin;

                // Draw the row's entries.
                int x = margin;
                for (int col_num = 0; col_num < num_cols; col_num++)
                {
                    Rectangle box_rect = new Rectangle(x, y,
                        ColWidths[col_num], max_height);
                    Rectangle text_rect = box_rect;
                    text_rect.Inflate(-margin, -margin);

                    sf.Alignment = HorzAlignments[col_num];
                    sf.LineAlignment = VertAlignments[col_num];
                    e.Graphics.DrawString(row[col_num], font,
                        Brushes.Black, text_rect, sf);

                    e.Graphics.DrawRectangle(Pens.Blue, box_rect);

                    x += ColWidths[col_num];
                }

                y += max_height;
            }
        }
    }
}

This code creates a StringFormat object to specify the alignments used to draw text in the various columns. It also creates a font to use to draw text.

Next, the code defines a margin to place around the text. The program sets variable y to the margin’s value so the first piece of text leaves a small gap at the top of the form. The code then loops through the rows in the Values array.

Each entry in the Values array is an array containing the values that should be drawn in its row. The code initializes max_height to zero. It then loops trough the values in this row.

The code uses the Graphics object’s MeasureString method to see how much space each value needs if it is to be written with its column’s given width. When you call MeasureString and specify a width as in this code, the returned SizeF structure is as tall as necessary to draw the text with the indicated width. This code subtracts twice the margin from the column width so it can place a margin between the edges of the column and the text.

The code rounds the returned SizeF structure’s height up to the nearest integer. If the result is greater than max_height, the code updates max_height.

After it has found the largest height required to display each of the row’s pieces of text, the code adds twice the margin to place some extra space around the text.

Next, the program loops through the row’s entries a second time. For each entry, it makes a Rectangle named box_rect to represent the box around the text. This box is as wide as the column (as stored in the ColWidths array) and has the height found by the previous loop (which includes twice the margin).

The code then copies the Rectangle into a new one named text_rect and uses its Inflate method to make it smaller by the amount margin in all directions. That keeps the Rectangle centered but makes it smaller by the amount margin in the left, right, up, and down directions.

Now the program sets the column’s alignment properties in the StringFormat object that it created earlier and uses that object to draw text in text_rect. It then draws the box_rect to place a box around the text.

After drawing the current entry, the code adds the column’s width to variable x so the next column starts shifted to the right.

After it has drawn all of the text for the row, the code increases y by the row’s height to prepare for the next row.

Note that this example does not break across pages. If the data is long, the program will not stop and start a new page. instead it will simply create a very long single page. You could modify the program to display its data in some sort of scrolled window. Or, if you are printing the data, you could display it on multiple pages.


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in fonts, graphics, lists | Tagged , , , , , , , , , , , , , , , , | Leave a comment

Draw a randomly colored Sierpinski pentagon in C#

[example]

The example Draw a colored Sierpinski pentagon in C# lets the user click on the parts of a Sierpinski pentagon to change their colors. Eddie Bole thought it would be interesting to color the larger pentagons in addition to the smaller ones into which each is divided. This example does that.

To make that easier, I modified the Pentagon class to more accurately reflect the recursive structure of the Sierpinski pentagon. The following code shows the new Pentagon class.

class Pentagon
{
    // Colors.
    private static Random Rand = new Random();
    private static Color[] MyColors =
    {
        Color.Black, Color.Red, Color.Orange,
        Color.Yellow, Color.Lime, Color.LightGreen,
        Color.Cyan, Color.Blue, Color.LightBlue,
        Color.Fuchsia,
    };

    public PointF[] Points = null;
    public Color FillColor = Color.Black;
    public List<Pentagon> Children = new List<Pentagon>();

    // Constructor.
    public Pentagon(PointF[] points)
    {
        Points = points;
        FillColor = MyColors[Rand.Next(0, MyColors.Length)];
        FillColor = Color.FromArgb(128, FillColor);
    }

    // Draw.
    public void Draw(Graphics gr)
    {
        // Draw this Pentagon.
        using (Brush brush = new SolidBrush(FillColor))
        {
            gr.FillPolygon(brush, Points);
        }
        gr.DrawPolygon(Pens.Black, Points);

        // Draw child Pentagons (if any).
        foreach (Pentagon child in Children) child.Draw(gr);
    }
}

The new class defines the colors that a Pentagon could have. The MyColors array is static so it is shared by all instances of the class. (There’s no point making each object take up room for its own separate copy.)

The new Children list gives the pentagons into which the current pentagon is divided to make the Sierpinski pentagon. At the deepest level of recursion, the smallest pentagons are not divided so their Children lists are empty.

The class’s constructor saves the pentagon’s points and then picks a random color from the MyColors array. It then recreates the color setting its alpha component to 128 so the color is semi-transparent. Alternatively, you could make the MyColors array contain colors with alpha is already 128, but then you would have to specify the colors by giving their red, green, blue, and alpha color components instead of using their names. The code shown here specifies the colors by name so it’s easier to know what the colors are.

The Pentagon class’s Draw method now draws the current Pentagon. It then recursively calls the Draw methods for its children.

The main program uses the following code to build its Pentagon objects.

// The root of the Pentagon object hierarchy.
private Pentagon Root = null;

// Make the Pentagon objects and redraw.
private void MakePentagons()
{
    // Build the Root.
    int depth = (int)nudDepth.Value;
    PointF center = new PointF(
        picPentagon.ClientSize.Width / 2,
        picPentagon.ClientSize.Height / 2);
    float radius = (float)Math.Min(center.X, center.Y);
    Root = MakePentagon(depth, center, radius);

    // Redraw.
    picPentagon.Refresh();
}

The program stores the largest Pentagon object in the variable Root.

The MakePentagons method builds the Sierpinski pentagon. It gets the desired depth of recursion, finds the center of the drawing area, and sets the large pentagon’s radius. It then calls the following MakePentagon method to create the largest pentagon.

// Recursively generate a Pentagon and its descendants.
private Pentagon MakePentagon(int depth, PointF center, float radius)
{
    // Make the Pentagon.
    Pentagon parent = new Pentagon(GetPentagonPoints(center, radius));

    // If we are not done recursing, make children.
    if (depth > 0)
    {
        // Find the smaller pentagons' centers.
        float d = radius - radius * size_scale;
        PointF[] centers = GetPentagonPoints(center, d);

        // Recursively draw the smaller pentagons.
        foreach (PointF point in centers)
        {
            parent.Children.Add(MakePentagon(
                depth - 1, point, radius * size_scale));
        }
    }

    return parent;
}

This method first creates a new Pentagon object.

If the depth of recursion has not reached zero, the method gets the pentagon’s vertices. The method then loops through the vertices and recursively calls itself to make smaller pentagons at each of the vertices.

When the program needs to redraw the Sierpinski pentagon, it refreshes the picPentagon PictureBox and the following Paint event handler executes.

// Draw.
private void picPentagon_Paint(object sender, PaintEventArgs e)
{
    e.Graphics.Clear(picPentagon.BackColor);
    e.Graphics.SmoothingMode = SmoothingMode.AntiAlias;
    if (Root == null) return;

    Root.Draw(e.Graphics);
}

This code simply prepares the Graphics object and then calls the Root pentagon’s Draw method. that method recursively calls the Draw methods for all of the smaller pentagons.

Note that the pentagons are drawn in order from largest to smallest. That ensures that the smaller pentagons are drawn on top of the larger ones.

Those are the most interesting changes to the program. Download the example to see additional details and to experiment with the program.


Download Example   Follow me on Twitter   RSS feed   Donate




Posted in drawing, fractals, graphics, recursion | Tagged , , , , , , , , , , | 5 Comments