Recursion in C# works well when using WPF
The aim of this article is to illustrate how to draw a binary tree and a snowflake using WPF. Both examples appear useless, having no practical value, but they are part of a hot topic in parallel computing: fractals. You can define a binary tree recursively as a trunk attached to branches. The branches are attached to smaller branches that are attached to still smaller branches, and so on. That is, we will sort of write a program that continues drawing smaller and smaller branches until the new branches are less than one pixel long. At this point, the program obviously stops. The first place to start is layout management. In WPF, the Canvas control allows elements to be positioned absolutely using fixed coordinates. This layout container is the most similar to traditional Windows Forms, but it doesn't provide anchoring or docking features. The StackPanel control places elements in a horizontal or vertical stack. This layout container is typically used for small sections of a larger, more complex window. Both are used for layout management when building a WPF application. Here is a view of the draw after the start button control is clicked.
<Window
xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
x:Class="Project.BinaryTree"
x:Name="Window"
Title="BinaryTree"
Width="345"
Height="300">
<Window.Background>
<LinearGradientBrush EndPoint="0.5,1" StartPoint="0.5,0">
<GradientStop
Color="Black" Offset="0"/>
<GradientStop
Color="#FF0016FF" Offset="1"/>
</LinearGradientBrush>
</Window.Background>
<Viewbox Stretch="Uniform">
<StackPanel>
<StackPanel Orientation="Horizontal"
Margin="5,5,5,0">
<Button Name="btnStart" Click="btnStart_Click"
Width="98.502" Content="Start"
FontFamily="Times New Roman"
FontWeight="Bold" FontSize="16"/>
<TextBlock Name="tbLabel" Margin="20,5,0,0"/>
</StackPanel>
<Canvas Name="canvas1" Width="300"
Height="300" Margin="5" Background="#FFBDFF00"/>
</StackPanel>
</Viewbox>
</Window>
Every stroke gets smaller as the entire tree grows by adding successively smaller branches.
To build this project without the solution file, fire up Visual Studio 2008 (2010) or Expression Blend, start a new C# WPF project called Project. Right-click the project icon and select "Add new item" to select a new window that you will name BinaryTree. Right-click the MainWindow.xaml file and select "Remove from project". You will only see a window with a button. It will draw a tree because of the code we'll write in the corresponding code-behind file.
Here is the code-behind file. Notice the use of recursion:
using System;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Shapes;
namespace Project
{
public partial class BinaryTree : Window
{
private int II = 0;
private int i = 0;
public BinaryTree()
{
InitializeComponent();
}
private void btnStart_Click(object sender, RoutedEventArgs e)
{
canvas1.Children.Clear();
tbLabel.Text = "";
i = 0;
II = 1;
CompositionTarget.Rendering += StartAnimation;
}
private void StartAnimation(object sender, EventArgs e)
{
i += 1;
if (i % 60 == 0)
{
DrawBinaryTree(canvas1, II,
new Point(canvas1.Width / 2,
0.83 * canvas1.Height),
0.2 * canvas1.Width, -Math.PI / 2);
string str = "Binary Tree - Depth = " +
II.ToString();
tbLabel.Text = str;
II += 1;
if (II > 10)
{
tbLabel.Text = "Binary Tree - Depth = 10. Finished";
CompositionTarget.Rendering -=
StartAnimation;
}
}
}
private double lengthScale = 0.75;
private double deltaTheta = Math.PI / 5;
private void DrawBinaryTree(Canvas canvas,
int depth, Point pt, double length, double theta)
{
double x1 = pt.X + length * Math.Cos(theta);
double y1 = pt.Y + length * Math.Sin(theta);
Line line = new Line();
line.Stroke = Brushes.Blue;
line.X1 = pt.X;
line.Y1 = pt.Y;
line.X2 = x1;
line.Y2 = y1;
canvas.Children.Add(line);
if (depth > 1)
{
DrawBinaryTree(canvas, depth - 1,
new Point(x1, y1),
length * lengthScale, theta + deltaTheta);
DrawBinaryTree(canvas, depth - 1,
new Point(x1, y1),
length * lengthScale, theta - deltaTheta);
}
else
return;
}
}
}
This example holds a type of system concept. If we consider the text and graphics that output to the console screen, the system has had to write them to screen. Perhaps another API makes the text and/or object understandable to the human eye. Having said that, consider this line segment that has been trisected into lines of equal length. We form an equilateral triangle rising out of the middle segment.
The snowflake begins with an equilateral triangle. The program replaces each of the triangle's sides with a properly scaled and rotated version of the basic unit. The program then replaces each of the straight segments in the new figure with a smaller version of the basic unit. It replaces the newer straight segments with smaller and smaller versions of the basic unit until the snowflake reaches the desired depth. By the way, the linear gradients shown in this and the binary tree application are just there to make the appearance a little more stimulating. A white background for window is more than sufficient. So now, add a new WPF window to the project that we called Project. Remove the binary tree XAML file from the project. Name the new window SnowFlake. Here is a view of the before the button click and after:
<Window
xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
x:Class="Project.SnowFlake"
x:Name="Window"
Title="SnowFlake"
Width="350"
Height="300">
<Window.Background>
<LinearGradientBrush EndPoint="0.5,1"
StartPoint="0.5,0">
<GradientStop Color="Black" Offset="0"/>
<GradientStop
Color="#FFFF0006" Offset="1"/>
</LinearGradientBrush>
</Window.Background>
<Viewbox Stretch="Uniform">
<StackPanel>
<StackPanel Orientation="Horizontal"
Margin="5,5,5,0" Background="#FFA6FF00">
<Button Name="btnStart" Click="btnStart_Click"
Width="95.949" Content="Start" Height="29.618"
FontFamily="Times New Roman"
FontWeight="Bold" FontSize="16"/>
<TextBlock Name="tbLabel" Margin="20,5,0,0"/>
</StackPanel>
<Canvas Name="canvas1" Width="300"
Height="300" Margin="5">
</Canvas>
</StackPanel>
</Viewbox>
</Window>
Here is the corresponding code-behind file:
using System;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Shapes;
namespace Project
{
public partial class SnowFlake : Window
{
private double distanceScale = 1.0 / 3;
double[] dTheta = new double[4] { 0, Math.PI / 3,
-2 * Math.PI / 3, Math.PI / 3 };
Polyline pl = new Polyline();
private Point SnowflakePoint = new Point();
private double SnowflakeSize;
private int II = 0;
private int i = 0;
public SnowFlake()
{
InitializeComponent();
double ysize = 0.8 * canvas1.Height /
(Math.Sqrt(3) * 4 / 3);
double xsize = 0.8 * canvas1.Width / 2;
double size = 0;
if (ysize < xsize)
size = ysize;
else
size = xsize;
SnowflakeSize = 2 * size;
pl.Stroke = Brushes.Blue;
}
private void btnStart_Click(object sender, RoutedEventArgs e)
{
canvas1.Children.Clear();
tbLabel.Text = "";
i = 0;
II = 0;
canvas1.Children.Add(pl);
CompositionTarget.Rendering += StartAnimation;
}
private void StartAnimation(object sender, EventArgs e)
{
i += 1;
if (i % 60 == 0)
{
pl.Points.Clear();
DrawSnowFlake(canvas1, SnowflakeSize, II);
string str = "Snow Flake - Depth = " +
II.ToString();
tbLabel.Text = str;
II += 1;
if (II > 5)
{
tbLabel.Text = "Snow Flake - Depth = 5. Finished";
CompositionTarget.Rendering -=
StartAnimation;
}
}
}
private void SnowFlakeEdge(Canvas canvas,
int depth, double theta, double distance)
{
Point pt = new Point();
if (depth <= 0)
{
pt.X = SnowflakePoint.X +
distance * Math.Cos(theta);
pt.Y = SnowflakePoint.Y +
distance * Math.Sin(theta);
pl.Points.Add(pt);
SnowflakePoint = pt;
return;
}
distance *= distanceScale;
for (int j = 0; j < 4; j++)
{
theta += dTheta[j];
SnowFlakeEdge(canvas, depth - 1,
theta, distance);
}
}
private void DrawSnowFlake(Canvas canvas, double length, int depth)
{
double xmid = canvas.Width / 2;
double ymid = canvas.Height / 2;
Point[] pta = new Point[4];
pta[0] = new Point(xmid, ymid + length / 2 *
Math.Sqrt(3) * 2 / 3);
pta[1] = new Point(xmid + length / 2,
ymid - length / 2 * Math.Sqrt(3) / 3);
pta[2] = new Point(xmid - length / 2,
ymid - length / 2 * Math.Sqrt(3) / 3);
pta[3] = pta[0];
pl.Points.Add(pta[0]);
for (int j = 1; j < pta.Length; j++)
{
double x1 = pta[j - 1].X;
double y1 = pta[j - 1].Y;
double x2 = pta[j].X;
double y2 = pta[j].Y;
double dx = x2 - x1;
double dy = y2 - y1;
double theta = Math.Atan2(dy, dx);
SnowflakePoint = new Point(x1, y1);
SnowFlakeEdge(canvas, depth, theta, length);
}
}
}
}
When the program recursively draws a line segment, it begins by drawing a third of the length of the segment in its current direction. It then turns 60 degrees and draws another third of the length of the segment. Next, it turns -120 degrees and draws another third. Finally, it turns 60 degrees again and draws yet another third of the length of the original segment. This is why you define the dTheta in the form:
double[] dTheta = new double[4] { 0, Math.PI / 3, -2 * Math.PI / 3, Math.PI / 3 };
Recall from basic calculus that when y = f(x), then y, the dependent variable, is a function of the independent variable x. Y prime, or y', or f'(x), is the derivative of the equation set equal to f(x). If y = f(x) = x raised to the 3rd power, then f'(x) is 2x squared. It also might help to think of a recursive function as one that calls itself. The SnowFlakeEdge method recursively draws a segment (by adding the point to the polyline's point collection) that starts at snowflakePoint and moves in the direction theta by a length of distance. When it is finished, it leaves the value of the snowflakePoint to indicate the endpoint of the segment. This makes it easier to perform all of the necessary recursive calls one after another. The DrawSnowFlake method calls the SnowFlakeEndge method to draw each of the sides of the initial triangle. Inside this method, the Atan2 function takes the parameters dy and dx, which are the changes in a line segment's Y and X coordinates, respectively. It returns the angle with the tangent of dy/dx. Now, if the Start button is pressed, the program starts drawing the snowflake.
This article's content contains material that has been referenced from the works of Jack Xu, a leader in advanced .NET graphics and WPF development.
