I was asked recently how difficult it would be to write a program that draws trees. Not the same tree every time but something that could be used to create a forest. You might think that at this point I would go off into the subject of fractals and advanced graphics. In fact I was tempted to call this project trees without fractals. Drawing visually interesting trees is relatively easy if you use the power of recursion.

In this project we solve the problem of drawing a tree using an algorithm that essentially draws lines. To make sure that it's easy to convert the code to other languages and graphics systems the approach has been kept simple and although WPF is used as the graphics system the drawing hasn't been integrated into the WPF class hierarchy. If you would like to see how the job should be approached from a stronger WPF angle then see Custom Shapes which uses the tree drawing function developed here as an example.

What is a tree?

If you are a programmer you might well come up with a definition that goes something like – a tree is a trunk, i.e. a main branch, with a tree attached to it.

This is the essence of a recursive definition but it would be simpler to say that a tree is branch with two trees attached. This narrows things down to  “binary” trees but they still look surprisingly good.

Recursive trees

The basic idea is to write a function that draws a branch, i.e. a line at a starting location x,y at a given angle t and length L. It then calls the same function, i.e. itself, to draw two more branches from the end points of the branch just drawn.This is the recursive part of the algorithm.

The two new branches are rotated from the angle of the first branch by an amount dt and are shorter by a factor s, i.e. a Scaling factor.

This continues either to infinity or, more practically, to a predetermined limit – the depth of the tree d. This is recursion in action and you should be surprised at how much structure you get for so little code.

DrawBranch -> Draw a tree

Start a new C# WPF project or whatever you prefer as a graphics language and place a Canvas layout object on the form. The Canvas is just one of the many layout objects we could use but it has the advantage of being simple and allowing objects to be positioned using x,y co-ordinates.

Define the start of the new function:

private void DrawBranch(
 double x,
 double y,
 double L,
 double s,
 double t,
 double dt,
 int d)

The meaning of all of the parameters has been introduced in the discussion of how the recursion works in the previous section.

The first thing the function has to do is to draw the branch from x,y of length L at angle t. This is simple trigonometry coupled with the use of the Line shape class:

double x1 = x + L * Math.Cos(
                   t * Math.PI / 180);
double y1 = y - L * Math.Sin(
                   t * Math.PI / 180);

The PI/180 converts the angle in degrees to radians.

We could create a Line object and add it to the Canvas in two steps but it is just as easy to do the job in one combined instruction which has the advantage of not needing another variable:

canvas1.Children.Add(
 new Line()
  {X1=x,Y1=y,
   X2=x1,Y2=y1,
   Stroke=Brushes.Black,
   StrokeThickness=2});

With the one line drawn we now have to move on to the recursive part and draw two more lines from the line's endpoint.

The end point is at x1,y1 and hence we need to draw two lines starting at x1,y1 but only if we haven’t yet reached the target depth of the tree:

if( d > 1) 
{
 DrawBranch(x1, y1, 
     L * s, s, t + dt, dt, d - 1);
 DrawBranch(x1, y1, 
     L * s, s, t - dt, dt, d - 1);
}

Notice that the two recursive calls draw a branch that is L*s long i.e. reduced by the scale factor and at an angle of t+dt and t-dt. The depth of the tree is also reduced by one as we have already drawn a line i.e. one level of the tree. Eventually d becomes less than one and the recursion stops. 

<ASIN:0470477229>

<ASIN:0071357815>

<ASIN:1430225394>

<ASIN:1568814690>