A Pythagoras tree (or Pythagorean tree) is a fractal tree built from squares. It starts with a square that forms the tree’s base.

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.

You can multiply a vector by a number S to make a new vector that is S times as long as the original vector.

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

The following code shows the `VectorF` class that the program uses to represent a vector.

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); } }

Most of the `VectorF` class is relatively straightforward. Two methods that I want to point out are `PerpendicularCCW` and `PerpendicularCW`. Those methods find vectors that are perpendicular to the given vector. If you try an example on graph paper, it should be easy to see that the vectors perpendicular to vector <x, y> are <y, -x> and <-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(α)

To convert those lengths into a vector, use the corresponding vector (either the base vector or the height vector) from the parent branch, divide it by its length to get a vector of length 1, and the multiply it by the appropriate length from the preceding equations.

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

The following code shows the main `DrawBranch` method.

// 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); } }

The method first uses the square’s lower left corner and base vector to find the square’s vertices. It then uses the `Graphics` object it receives as a parameter to draw and optionally fill the square.

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.

The following picture shows a depth 15 tree. In this tree, the angle α is 60° so the tree is asymmetric.

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

thank’ssss

It took me a while but I added a save to picture file feature, but wondered how to add transparency. I can send you what I did if you like. Also I thought a nice extra feature would be to start with an initial brown rectangular or trapezium shaped trunk and have the the colours slowly change from brown to green. Other features I also thought about: how to make the tree a lot bigger to show more detail by adding a scroll-able window and how to save and stitch together successive pictures to make an animated gif or video file to make the tree appear that it is growing or swaying with that nice curvy structure. Thanks for your nice Pythagoras tree example.

All good ideas!

To change colors or for transparency, look at the

DrawBranchmethod. It takes aPenand aBrushas parameters and draws with them. For transparency, pass in a transparent brush. For example, the following brush is semi-opaque red:To change colors, either:

DrawBrushmethod modify the pen and brush before calling itself recursively. For example, it could increase the amount of green in the colors. (You can simply change the brush’sColorproperty to give it a new color.)DrawBrushmethod use thedepthto calculate the color it should use. For example, smaller depths might mean more green.Stitching pictures together would be interesting. The program is pretty fast, so you could try using a timer to redraw with slightly different angles 10 or 20 times per second. It would only work with relatively small depth of recursion, but might give an interesting result. You could also animate increasing side lengths and numbers of levels to make the tree “grow.”

Look at the

Panelcontrol withAutoScroll = trueto get easy scrolling. Zooming in might be nice, too, although harder.Thanks for replying Rod. I found some image stitching examples on codeproject: A Simple C# Wrapper for the AviFile Library and Avi from Image Files in One Click. The “A Simple C# Wrapper for the AviFile Library” has all sorts of examples like Create a new video stream from a list of bitmaps, Add sound from a .wav file to the video, Add frames to an existing video stream, compressed or not, Insert frames into a stream.

Copy or delete frames from a stream, etc. Hopefully it might be useful in helping me create a basic image stitcher to avi video program in csharp. I made a basic image stitcher to avi video program in vb6, but need to get used to using csharp.

Hi Rod. I recently made a Pythagoras Tree using just lines and midpoints (the triangles are always right angled). It is at http://www.planetsourcecode.com/vb/scripts/ShowCode.asp?txtCodeId=75592&lngWId=1 In my one, the fill tends not to work reliably for upper levels. I like how you used vectors (this is probably a better approach than mine using just lines) and how you alter the angles of the triangles to skew the tree. I was wondering with your example, how would you go about alternating the fill colours and transparency, between the triangles and the squares? and also how could you make the background transparent? I like seeing how to do similar things in different programming languages so I learn to understand things better.

Vectors are handy if you want to rotate things. A vector implicitly keeps track of its direction so it’s easier to figure out how to rotate the next level of the tree. That’s particularly helpful if the angles are not simple ones like 90° or 45°.

how would you go about alternating the fill colours and transparency, between the triangles and the squares?

The

DrawBranchmethod fills its square and then recursively calls itself to draw its branches. Just modify it so it also fills the triangle between the branches. You can use code similar to the following after the method has finished drawing the branches.Here I’m assuming that the method takes new

triangle_penandtriangle_brushparameters that determine how the triangle is drawn.also how could you make the background transparent?

This is easier. Simply clear the

Graphicsobject with the colorTransparentlike this:In this example, there’s nothing behind the drawing to show through, so the result is black. The result would be more useful if you were to draw on a bitmap and then save the result in a png file. Then you could import the image into another drawing and it would be transparent around the tree. (As long as the drawing program understands transparency. MS Paint does not really.)

You could also change the transparency of the pens and brushes used to draw the tree. For example, the following code creates a semi-transparent blue brush.

Again this will be most interesting if you are drawing on top of something previously drawn or if you draw on a bitmap and save it into a png file.

Thanks for the info. Rod. In my Vb6 version I calculated the centroid of 3 points (for the triangles) and 4 points (for the squares) to fill the regions. I realised my 45 degree triangle version using midpoints was not as accurate as your variable angle vector version, when increasing the levels of recursion. I will try to play around with your suggestions in C#. I made a dashed line thicker than 1 pixel in Vb6 code using the Logbrush. It took me a while to understand the image layers and updating and refreshing when drawing lines dynamically in Vb6 so hopefully I might apply similar principles when using gdi brushes for C#. Thanks for the advice.