Title: Draw a Pythagoras tree fractal in C#

The program then makes the Pythagoras tree by recursively attaching two smaller branches to the original branch. The new branches are also squares and are arranged so their bases form a right triangle with the previous branch's ending side. The picture on the right shows the original branch in blue and the new branches in green.

One of the new branches makes angle α with the original branch. The other new branch makes angle β = 90 - α.

Because all of the branches are squares, the new branches are basically copies of the original branch suitably resized, rotated, and translated. Normally you would use sines and cosines to determine the new branches' widths, but there are a couple of ways that you can figure out how to position the new branches. For this example, I decided to use vector arithmetic.

Vector arithmetic is pretty easy once you get used to it. A two-dimensional vector is represented by changes in X and Y coordinates surrounded by pointy brackets. For example, the vector <2, 5> means move 2 units in the X direction and 5 units in the Y direction.

The rules of vector arithmetic explain how points and vectors combine to form new points and vectors. The following list summarizes the three most basic rules.

• A point minus a point gives a vector pointing from the second point to the first.
• A point plus a vector gives the new point where you would end up if you started at the first point and moved along the vector.
• A vector plus a vector gives a new vector that is equivalent to following one vector and then the other.

All of these operations work one coordinate at a time. For example, if A = <1, 2> and B = <4, 6>, then A + B = <1 + 4, 2 + 6> = <5, 8>.

I don't want to spend any more time on vector arithmetic because it's fairly straightforward and not really central to this example. For more information, google "vector arithmetic." There are tons of pages that explain the topic. Vector arithmetic is also covered briefly (but less briefly than it is here) in my book, WPF 3d, Three-Dimensional Graphics with WPF and C#.

VectorF

public class VectorF { public float X, Y; public VectorF(float x, float y) { X = x; Y = y; } public VectorF(PointF point1, PointF point2) { X = point2.X - point1.X; Y = point2.Y - point1.Y; } public VectorF(VectorF v) { X = v.X; Y = v.Y; } public static VectorF operator +(VectorF v1, VectorF v2) { return new VectorF(v1.X + v2.X, v1.Y + v2.Y); } public static VectorF operator -(VectorF v1, VectorF v2) { return new VectorF(v1.X - v2.X, v1.Y - v2.Y); } public static PointF operator +(PointF point, VectorF vector) { return new PointF(point.X + vector.X, point.Y + vector.Y); } public static PointF operator -(PointF point, VectorF vector) { return new PointF(point.X - vector.X, point.Y - vector.Y); } public static VectorF operator -(VectorF vector) { return -1 * vector; } public static VectorF operator *(VectorF vector, float scale) { return new VectorF(vector.X * scale, vector.Y * scale); } public static VectorF operator *(float scale, VectorF vector) { return vector * scale; } public static VectorF operator /(VectorF vector, float scale) { return new VectorF(vector.X / scale, vector.Y / scale); } public float Length { get { return (float)Math.Sqrt(X * X + Y * Y); } set { float scale = value / Length; X *= scale; Y *= scale; } } // Return a scaled version of the vector. public VectorF Scale(float scale) { return this * scale / Length; } // Make the vector unit length. public void Normalize() { Length = 1; } // Find the perpendicular vector in the // counterclockwise direction. public VectorF PerpendicularCCW() { return new VectorF(Y, -X); } // Find the perpendicular vector in the // clockwise direction. public VectorF PerpendicularCW() { return new VectorF(-Y, X); } }

The PerpendicularCCW method finds the perpendicular vector given by rotating the original vector in the counterclockwise direction. Similarly, the PerpendicularCW method finds the clockwise perpendicular vector.

Finding Branches

The first way I'm going to use vectors is to specify a branch's square. The program specifies a square by giving a point at its lower left corner and a vector across the square's base. The picture on the right shows how the point ll_corner and the vector v_base define a square.

The reason the program uses this method is that the vector nicely represents both the square's side length and its rotation.

Note that you can use the VectorF class's PerpendicularCCW method to find the vector along the square's left edge. Let's call that the square's height vector.

The first step in positioning a new branch is finding its side width. Suppose the original branch has width S as shown in the picture on the right. Then the width of the first new branch is S * Cos(α).

Now that we know the new branch's width, we need to find the point at its lower left corner and its base vector. The point at its lower left corner is simply the parent branch's lower left corner plus its height vector.

To find the new branch's base vector, we find the vector's components in the directions of the parent branch's base and height vectors. Those are the dashed vectors in the picture on the right.

The upper dashed vector is parallel to the parent branch's top, so the angle it makes with the new branch's base is also α as shown in the picture. We know that this triangle's hypotenuse has length S * Cos(α), so the lengths of the dashed vectors are the following.

S * Cos(α) * Cos(α)
S * Cos(α) * Sin(α)

After you find the dashed component vectors, you simply add them together to get the new branch's base vector.

You find the lower left corner, width, and base vector for the other child branch similarly.

Drawing Code

// Recursively draw a binary tree branch. private void DrawBranch(Graphics gr, Pen pen, Brush brush, int depth, PointF ll_corner, VectorF v_base, float alpha) { // Find the box's corners. VectorF v_height = v_base.PerpendicularCCW(); PointF[] points = { ll_corner, ll_corner + v_base, ll_corner + v_base + v_height, ll_corner + v_height, }; // Draw this box. if (brush != null) gr.FillPolygon(brush, points); gr.DrawPolygon(pen, points); // If depth > 0, draw the attached branches. if (depth > 0) { // *********** // Left branch // *********** // Calculate the new side length. double w1 = v_base.Length * Math.Cos(alpha); // Decompose the new base vector in terms of // v_base and v_height. float wb1 = (float)(w1 * Math.Cos(alpha)); float wh1 = (float)(w1 * Math.Sin(alpha)); VectorF v_base1 = v_base.Scale(wb1) + v_height.Scale(wh1); // Find the lower left corner. PointF ll_corner1 = ll_corner + v_height; // Draw the left branch. DrawBranch(gr, pen, brush, depth - 1, ll_corner1, v_base1, alpha); // ************ // Right branch // ************ // Calculate the new side length. double beta = Math.PI / 2.0 - alpha; double w2 = v_base.Length * Math.Sin(alpha); // Decompose the new base vector in terms of // v_base and v_height. float wb2 = (float)(w2 * Math.Cos(beta)); float wh2 = (float)(w2 * Math.Sin(beta)); VectorF v_base2 = v_base.Scale(wb2) - v_height.Scale(wh2); // Find the lower left corner. PointF ll_corner2 = ll_corner1 + v_base1; // Draw the right branch. DrawBranch(gr, pen, brush, depth - 1, ll_corner2, v_base2, alpha); } }

Next, if the depth of recursion is greater than zero, the code draws two child branches. It calculates the left branch's width. It then finds the lengths of the two dashed vectors shown in the earlier figure. The code multiples the parent branch's base and height vectors by the appropriate lengths and adds the results to get the new branch's base vector.

The code then finds the child branch's lower left corner. Next, the method recursively calls itself, passing itself the new lower left corner and base vector.

The code repeats the steps to recursively draw the right child branch. Note that the calculations are similar but slightly different.

The program uses the following code to redraw the tree when you change on of the tree parameters or resize the form.

// Draw the tree. private void picCanvas_Paint(object sender, PaintEventArgs e) { e.Graphics.Clear(picCanvas.BackColor); e.Graphics.SmoothingMode = SmoothingMode.AntiAlias; try { int depth = (int)nudDepth.Value; int length = (int)nudLength.Value; float alpha = (float)((double)nudAlpha.Value * Math.PI / 180.0); float root_x = picCanvas.ClientSize.Width / 2; float root_y = picCanvas.ClientSize.Height * 0.9f; VectorF v_base = new VectorF(length, 0); PointF ll_corner = new PointF(root_x, root_y) - v_base / 2; Brush brush = null; if (chkFill.Checked) brush = Brushes.Green; DrawBranch(e.Graphics, Pens.Black, brush, depth, ll_corner, v_base, alpha); } catch { } } This code simply gets the tree parameters and passes them to the DrawBranch method.

The following picture shows the tree's first four levels of recursion.

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