Title: Draw Padovan triangles in Python

[Padovan triangles drawn in Python]

My post Draw Fibonacci squares in Python explained how you can draw Fibonacci squares. The numbers in the Fibonacci sequence are defined by the recurrence relation Fibonacci(i) = Fibonacci(i - 1) + Fibonacci(i - 2). The widths of the Fibonacci squares follow the same relation so each square's width equals the sum of the widths of the two previous squares. If you arrange the squares properly, you can make them form a spiral.

The Padovan sequence is similar but it is defined by the following recurrence relation.

P(0) = P(1) = P(2) = 1 P(i) = P(i - 2) + P(i - 3)

This post shows how you can draw the Padovan triangles that satisfy this recurrence relation.

A New Relation

The following list shows the first few numbers in the Padovan sequence.

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, ...

The picture at the top of this post shows how you can use the Padovan sequence to generate a sequence of triangles. These are equilateral triangles where each triangle's side length equals the sum of the side lengths of the triangles two and three earlier in the sequence. For example, look at the four largest triangles in the picture with side lengths 6, 12, 16, and 21. The last triangle has side length 21, which equals 12 + 6.

If you study the picture for a while, you'll see that each triangle has a side that coincides with sides of the triangles one and five earlier in the sequence. In other words, if W is the width of a triangle, then W(i) = W(i - 1) + W(i - 5).

This recurrence relation is somewhat similar to the Padovan sequence's relation, but it's not exactly the same. To show that we really are drawing Padovan triangles, we need to show that the two recurrence relations are equivalent.

To do that, we can write P(i) using the two relations and show that the two versions are equal as in the following picture.

[Another definition of the Padovan recurrence relation]

The first line shows the two versions of P(i). We expand the P(i - 2) and P(i - 1) terms using the original definition of the Padovan sequence to get the second line. You can see that the terms in the second line are the same, so the two definitions of the sequence match.

This is important because it's not obvious from the picture that a triangle's width W(i) equals W(i - 2) + W(i - 3), but it is obvious that W(i) = W(i - 1) + W(i - 5).

Defining the Triangles

The program uses the following get_padovan_triangles function to build a list of Padovan triangles.

def get_padovan_triangles(num_triangles): '''Return a list of Vector2 points forming Padovan triangles.''' triangles = [] # Find the first 7 points. p0 = pygame.Vector2(0, 0) p1 = pygame.Vector2(0.5, -0.5 * math.sqrt(3)) p2 = pygame.Vector2(1, 0) p3 = pygame.Vector2(0.5, 0.5 * math.sqrt(3)) p4 = pygame.Vector2(-0.5, 0.5 * math.sqrt(3)) p5 = pygame.Vector2(-1.5, -0.5 * math.sqrt(3)) p6 = pygame.Vector2(-0.5, -3 * 0.5 * math.sqrt(3)) # Make the first 5 triangles. triangles.append((p0, p1, p2)) triangles.append((p0, p2, p3)) triangles.append((p0, p3, p4)) triangles.append((p1, p4, p5)) triangles.append((p1, p5, p6)) # Generate other triangles. for i in range(5, num_triangles): # Make triangle number i (with numbers starting at 0). # It shares an edge with triangles[i - 1] and triangles[i - 5]. triangles.append(get_triangle(triangles[i-5][2], triangles[i-1][2])) return triangles

[Padovan triangles labeled by index in Python]

This code uses the W(i) = W(i - 1) + W(i - 5) recurrence relation to generate its triangles. Because it looks back five positions in the sequence, the program needs to define the first five triangles explicitly so it can look back that far. The function begins by defining those triangles. The picture on the right shows how points p0 through p6 define the triangles. Here the triangle's text shows each triangle's index in the sequence rather than its side length.

After it defines the initial triangles, the code uses a loop to create the remaining triangles. For triangle i, the code calls the get_triangle function described next to find the points that define triangle i. It passes that function the points triangles[i-5][2] and triangles[i-1][2], which are the points on the earlier triangles that define the new triangle's edge.

For example, consider triangle number 5. Its right side has end points p2 and p6. Point p2 is the lower left corner of triangle 0 and p6 is the lower left corner of triangle 4. (You need to look at each triangle with its orientation to figure out which corner is lower left.)

Defining One Triangle

The program uses the following get_triangle function to generate a single triangle.

def get_triangle(p0, p1): '''Return an equilateral triangle with this upper right side.''' # Find the triangles' vertices as Vector2 objects. v01 = p1 - p0 v02 = v01.rotate(60) p2 = p0 + v02 # Return the points as (x, y) coordinate pairs. return (p0, p1, p2)

The function takes as inputs the points p0 and p1 that give the triangle's upper and lower right corners. To find the third point, the code creates the vector from point p0 to point p1 and then rotates the vector 60°. It adds the rotated vector to point p0 to get point p2.

The code then returns the points in the order p0, p1, p2.

Conclusion

This is one of those programs where figuring out what to draw takes a bit of thought but, once you get it all straight, the code is surprisingly short.

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