Title: Draw Pythagoras tree fractals in Python

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 orientation of a Pythagoras tree's branches are determined by the angles α and β] The program 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 as its hypotenuse. 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 provided by pygame's Vector2 class.

Using Vectors

Vectors are pretty interesting and it's fun to roll your own vector classes, but pygame's Vector2 class makes things even easier. The Vector2 class represents two-dimensional vectors. (The pygame library also has a Vector3 class that represents three-dimensional vectors, but we don't need that for this example.)

Vector arithmetic is pretty easy once you get the hang of 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 and pointing in the same direction.

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. Vectors are also covered briefly and used extensively in my book, Python Action Arcade! Vectors make things like drawing spaceships, bullets, and exploding rocks really easy.

Finding Branches

[A square is defined by its lower left corner and base vector]

The first way this example uses vectors is to specify a branch's square. The program specifies a square by giving the 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 orientation. You can use the Vector2 class's rotate method to rotate a vector and that's just what the doctor ordered for building and rotating the tree's squares.

For example, if you take the base vector and rotate it 90 degrees counter clockwise, you get the square's left edge. Let's call that the square's height vector v_height.

[To find the child's base vector, scale and rotate the parent's base 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(α).

To find the new branch's base vector, we simply scale the parent's base vector to the branch's width and then rotate it by angle α as shown in the picture on the right.

Next, we need to find the point at the new branch's lower left corner. That point is simply the parent branch's lower left corner plus its height vector.

You find other branch's width, base vector, and the lower left corner similarly.

When you look at the code, you'll see how easy this all is if you use vectors.

Writing Python Code

Without further ado, here's the make_branch method that generates the tree's squares.

def make_branch(branches, depth, ll_corner, v_base, alpha): '''Recursively generate points for a Pythagoras tree branch.''' # Alpha is in radians. # Find the box's corners. v_height = v_base.rotate(90) # Rotate 90 degrees counter clockwise. points = [ ll_corner, ll_corner + v_base, ll_corner + v_base + v_height, ll_corner + v_height, ] branches.append(points) # If depth > 0, generate the attached branches. if depth > 0: # *********** # Left branch # *********** # Calculate the new width. w1 = v_base.length() * math.cos(alpha) # The new base is the parent's base scaled and rotated. v_base1 = (v_base.normalize() * w1).rotate(math.degrees(alpha)) # Find the lower left corner. ll_corner1 = ll_corner + v_height # Create the left branch. make_branch(branches, depth - 1, ll_corner1, v_base1, alpha) # ************ # Right branch # ************ # Calculate the new width. beta = math.pi / 2 - alpha w2 = v_base.length() * math.cos(beta) # The new base is the parent's base scaled and rotated. v_base2 = (v_base.normalize() * w2).rotate(math.degrees(-beta)) # Find the lower left corner. ll_corner2 = ll_corner1 + v_base1 # Create the right branch. make_branch(branches, depth - 1, ll_corner2, v_base2, alpha)

This function takes the following parameters:

branches: A list to hold the tree's squares. Each square is a list holding its four corner points.
depth: The depth of recursion we want for this branch.
ll_corner: The location of the current square's lower left corner. (Here "lower left" is relative to the square's orientation.)
v_base: The vector pointing across the square's base.
alpha: The alpha value we're using for this tree.

The code first calculates v_height by rotating v_base 90 degrees counter clockwise. It then uses the vectors ll_corner, v_base, and v_height to build a list holding the current square's corners and adds the new square to the branches list.

That's the end of the code that actually creates squares! The rest of the code calculates the position of the child squares and passes them to a recursive call to make_branch.

If the depth of recursion is greater than 0, the code makes the child branches. First is calculates the width of the left child branch. It then scales and rotates the parent's base vector to get the child's vector.

To scale the vector, the code first calls its normalize method to get a vector pointing in the same direction but with the desired length. It then multiples tat vector by the desired length w1. The result is a vector in the same direction as the original but with length w1.

The code then calls the scaled vector's rotate method to rotate it by α degrees counter clockwise. This brings up one of more annoying issues that you'll encounter when working with vectors. The math library works with radians but the Vector2 class works with degrees. Be sure you convert between the two units as appropriate.

The code then adds the parent's lower left corner point to the parent's height vector to get the new branch's lower left point.

Having found the new branch's lower left corner and base vector, the code calls make_branch to recursively build the child branch.

The code then repeats those steps to make the other child branch. The only sneaky part is that the code rotates the parent's base vector by angle -β because we need to rotate the parent's vector clockwise.

Drawing the Tree

The hard part is done. The following code shows how the program uses the make_branch function to draw the tree.

def draw(self, *args): '''Draw the Pythagoras tree.''' # Get parameters. try: depth = int(self.depth_var.get()) length = -100 alpha = math.radians(float(self.alpha_var.get())) fill = self.fill_var.get() except: # If there's a problem, do nothing. return # Delete previous results. self.canvas.delete(tk.ALL) # Generate the tree's rectangles. branches = [] make_branch(branches, depth, Vector2(0, 0), Vector2(length, 0), alpha) # Transform to fit. margin = 10 self.canvas.update() wid = self.canvas.winfo_width() hgt = self.canvas.winfo_height() target_rect = (margin, margin, wid - margin, hgt - margin) branches = transform_list_of_lists(branches, target_rect) # Draw. if fill: fill_color = 'light blue' else: fill_color = '' for rect in branches: self.canvas.create_polygon(rect, fill=fill_color, outline='blue')

The code first gets the drawing parameters that you enter on the window. If anything goes wrong, like if the depth is blank or you type "A" in the Alpha field, the method just returns without drawing anything.

There are two little oddities here. First, because screen coordinates have Y increasing downward, everything is upside down. We can fix that by flipping everything 180 degrees by setting the initial square width to a negative value. That makes everything point left instead of right so the tree grows up instead of down.

Second, because we flipped everything, α and β are basically switched. The code subtracts the alpha value you entered from π/2 to correct that.

After getting the drawing parameters, the program deletes any previous drawing, creates a branches list, and calls make_branch to build the tree. Notice that the code puts the first branch's lower left corner at (0, 0) and it sets the initial square width to 100. Those values don't really matter because of the next step.

Figuring out the tree's dimensions ahead of time isn't easy. You may be able to figure it out for some special cases, but it can be tricky for different values of depth and alpha. Rather than trying to figure it out, the code just transforms the points to fit on the program's canvas. To see how that works, see my post Map points so they fit within a target area in Python.

Having transformed the tree's squares to fit, the code sets a fill color and then loops through the tree's squares and draws each.

Conclusion

Download the example to experiment with it and to see additional details. For example, try some alpha values other than 45 degrees so the result is asymmetric as in the following picture. [An asymmetric Pythagoras tree]