A Curious Algorithm¶

During a lecture in a summer calculus class, I took to drawing random geometric patterns around the edges of my notes. As I was toying with different shapes and ideas for simple space filling curves, I came across an algorithm that happened to result in consistent patterns when drawn within triangles. Consider this simple algorithm below:

1. Given any triangle, $P$, pick a point anywhere along one of $P$'s edges and call it current_point.
2. From current_point, draw to the farthest edge of $P$, such that the line drawn is perpindicular to the chosen edge.
3. Set current_point equal to the end of this drawn perpindicular line, and repeat this recursive process for some number of steps.

Following this "right angle algorithm" in detail on paper, I noticed a couple curious properties. The most prominent property I noticed was that given any "initial triangle" and any starting point, the algorithm would quickly converge to some repeating shape, which I will call the "ultimate shape".

Interested in finding the exact properties of this ultimate shape and putting my drawing skills to the test, I went home and wrote a program to generate a triangle and implement this right angle algorithm on it, graphing the result. This write up is a description of what I found when testing this algorithm, highlighting its more interesting features.

If you would like to see the code I wrote for this, visit the GitHub repository linked here.

Putting the Algorithm to the Test¶

The algorithm starts drawing from some point along the edge of the initial triangle, and draws a line to the farthest perpinducular edge, repeating the process from its new location in a recursive manner. When the algorithm is faced with two equal distances, it randomely picks one of the two edges to draw to. With this basic understanding of the algorithms' internals, we are equipt to begin the exploration into why it produces the ultimate shapes it does.

Picking an equilateral triangle to begin, I started the algorithm at one of its vertices and let it run for 100 steps, resulting in the graph shown below.

NOTE: The function return_points takes two angles and the right point of the triangle to build, returning the necessary points to make the triangle with the passed exact angles and right end point. The function drawTriangle takes (number_of_iterations, starting_point, outer_triangle_points, steps_to_show) where number_of_iterations is the number of steps the algorithm will execute, starting_point is where the algorithm will being drawing, outer_triangle_points is the set of three points generated by return_points to define the outer triangle, and finally steps_to_show is the index-range of steps to graph.

As you can see, after just a few steps the algorithm converged to a different triangle within the outer one. It can be seen that the ultimate triangle has each edge perpindicular to one of the outer triangle's edges, with all three of its vertices touching the outer triangle's edges.

One way I like to think of the outer triangle is an initial condition to this algorithm that will "mold" the lines into their "natural resting points" over time. You can see the result of this above. It seems that with every new step, the outer triangle is forcing the algorithm into its final repeating shape.

To eak some more information out of this pattern, I wrote a function, give_info to return the inner angles of this ultimate triangle. Below those inner angles are printed along with the last steps the algorithm took for more clarity.

Right off the bat, we notice that not only does this algorithm converge to triangle, but this ultimate triangle is similar to the outer one, as all the interior angles are the same! This is a rather interesting result.

As this initial equilateral outer triangles is scaled up and down, the convergence of the algorithm is not affected, however notice what happens when we change the starting point of the algorithm from $(4, 0)$ to $(3,0)$ and $(1, 0)$, where the final steps the algorithm took for each situation are graphed below.

As the starting point of the algorithm shifted, the ultimate triangle flipped around the axis defined by $x=2$. Infact, when the starting point is to the left or right of $2$, the ultimate triangle will always be pointing in one direction or the other; unless the algorithm starts at the edge points of $(0,0)$ and $(4,0)$, where the ultimate triangles orientation will be determined randomely. When the starting point is at 2, the algorithm picks a random side to follow due to the symmetry of the triangle, and the ultimate triangle will be oriented to either the left or right.

Curiousely enough, regardless of where the algorithm starts drawing from, the inner ultimate triangle is always the same size and has the same interior angles.

What if we applied this algorithm to an isosceles triangle? Take the example shown below, with the interior angles of both the ultimate inner triangle and initial triangle printed with the resulting graph.

As you can see, the same thing happened for this particular isosceles triangle; the ultimate triangle the algorithm converged to is similar to the outer triangle!

At this point, you are likely thinking that the ultimate shape may not always be a triangle, depending on the properties of the initial (outer) triangle! I will get to that, but first I am going to show that this property of convergence to similar triangles also holds for scalene triangles.

Once again, we can see the inner ultimate triangle is similar to the outer triangle. One natural question may be, "If the computational resources are not available to find this ultimate triangle, how else might it be found exactly"?

The answer would be that this exact inner triangle could be found with relative ease using geometry. Take a look at the general diagram below for one of these cases.

We know $a, b, c$, and $A, B, C$. It is also known that each of the edges of the inner triangle will be perpindicular with its corresponding edge on the outer triangle, and that the inner ultimate triangle will be similar to the outer one (same interior angles). With this information, all the inner angles can be found, giving enough information to solve for $x, y$, and $z$ shown in the diagram above. After finding these values, the points of the inner ultimate triangle can be found.

One interesting formula that can be used to approximate the side lengths of the inner ultimate triangle is given by

$$a' \approx \frac{sin(\gamma) \cdot a}{\varphi}$$

where $\gamma$ is the peak angle of the initial triangle, $a'$ is the inner side length to be approximated, $a$ is the corresponding outer side length, and $\varphi=1.61803 \cdots$, the Golden Ratio. The resulting error of the approximations when using this formula is highly dependent on the triangle being analyzed. In the example triangles I worked on, I saw side length approximations errors of the ultimate inner triangle between $0.1\%$ and $7\%$.

The side length to be solved for, $a'$, can be found exactly with

$$a' = \frac{sin(\gamma) \cdot a}{c}$$

where $c \approx \varphi$. I have a hunch $c$ is given by a function of the peak angle $\gamma$, however I have yet to find this function exactly, assuming it exists.

Other Ultimate Shapes¶

As alluded to earlier, when the angles of the outer triangle are adjusted, the algorithm can generate other interesting repeating shapes. One of the simpler repeating shapes is given below from an isosceles triangle. As a quick note, for most of the examples below I chose not to show the first steps the algorithm took as seeing them is usually not especially informative and they clutter the graph.

This is the first repeating ultimate shape we have seen that produces something other than a triangle. The above ultimate shape is nothing to get too excited about however, so lets start by slightly increasing and decreasing the interior angles of the isosceles triangle to see what else the algorithm comes up with.

Those patterns are much more interesting! Recall that the algorithm will always draw the longest possible line it can while still obeying the right angle rule, as we can see the result of this taking form in the previous two examples. For this specific isosceles triangle, we can see that as the top angle decreases, the number of "zig-zags" formed within the ultimate shape increases, as the angles are much steeper.

As shown below, scalene triangles succumb to a similar phenomena as well, producing different repeating shapes.

Lets take a look at what happens when we move the top angle in the other direction, starting with a $45-90-45$ triangle. In this case, it is interesting seeing all the steps the algorithm takes, so I plot them all below. The starting point is $(3.7, 0)$.

The final ultimate shape and its properties are shown below.

When the algorithm was implemented on the above right triangle, it produced some interesting results. The most immidiately noticeable of which being that the hourglass like ultimate shape, is built out of two $45-90-45$ triangles!

In the current implementation of the algorithm I have prevented it from drawing along edges or meeting the triangles vertices, to force it into developing the hourglass ultimate shape seen above. It is for this reason that on what looks to be the fourth step above (shown on the first graph of the triangle), the algorithm chose to draw down instead of up to the top vertice of the triangle. If the algorithm had been allowed to do so, the resulting inner shape would have been the two ultimate triangles flipped around the y-axis and scaled up, as pictured below by a previous implementation of the algorithm.

The algorithm is applied to a few more obtuse triangles to demonstrate this property of the algorithm converging to an "hour-glass" ultimate shape, composed to two similar triangles.

While this property is true for all obtuse triangles, note what happens as $\gamma$, the peak angle, approaches 180 degrees. As $\gamma \rightarrow 180$, the range of starting points from which the algorithm will converge to this ultimate hour-glass shape decreases, approaching the center of the triangle.

Notice what happens if the algorithm starts outside of this "critical range".

The algorithm gets "stuck" in a corner and approaches the left/right endpoints as the number of steps approaches infinity!

Finding the Ultimate Triangle¶

We have noticed that the ultimate shape may or may not be a triangle in different initial triangles. An important question is "can we define a set of angles for each type of triangle, where the algorithm will always converge to an ultimate triangle?".

Lets begin with finding rules for when an isosceles triangle will or will not result in an ultimate triangle. Consider the two initial isosceles triangles below. Notice the minute difference in their interior angles, and the large difference in the ultimate shapes.

As we can see in the third graph, the algorithm (starting at $(4, 0)$) seemed to be converging to a triangle, until on the 6th step it went up again instead of down, as drawing up again was just longer than drawing down. What this means is that we have found a "critical point" for lack of a better term. We already know of the first critical point for isosceles triangles; it is the $45-90-45$ triangle, where when the angles are at that point the ultimate shape will not be a triangle. The graphs above show us that the inflection point on the other end is when the interior angles are about $68.35-43.3-68.35$. Now that we know the two critical points, we can begin to define a range on which the initial triangles will have triangular ultimate shapes.

We will define each of the "foot" angles in an isosceles triangle as $x$, and the "peak" angle as $y$. From this we deduce the following rule for the interior angles of isosceles triangles

$$2x+y = 180$$ Treating $y$ as an unknown, we can solve for it and graph the equation $$y = -2x+180$$ Using this function and the found critical points, we know that when $45 < x < 68.35$, and $x$ is passed through the function $y = -2x+180$ the returned triangle defined by $x$ and $y$ will always result in an isosceles triangle with a triangular ultimate shape. When $x \leq 45$ and $x \geq 68.35$, the triangle produced with the angles given by the function $y = -2x+180$ will have an ultimate shape equal to something other than a triangle!

Visually, when the value of $x$ is shifted along this range of convergence towards $x=60$, the outer and ultimate triangle both approach the equilateral triangle, filling into it at $x=60$.

A similar process can be used to find the subset of angles that define a scalene triangle with an ultimate shape equal to a triangle. For example, if we take the line perpindicular to $y = -2x+180$ that passes through $(60, 60)$ we get $y = \frac{1}{2}x+30$. The points along this line give interior angles that can be used to construct scalene triangles, except when $x=60$.

Now, a pair of critical points can be found for scalene triangles, and the range of points between the two critical points along the line defined by $y = \frac{1}{2}x+30$ will define scalene triangles with triangular ultimate shapes!

We now have an easy method for determining if a given initial triangle will have a triangular ultimate shape or not!

Given these findings, we are in a position to make some simple conjectures and explore other questions.

Conjecture¶

For any given triangle $P$, there may exists a single similar triangle $P'$, such that when $P'$ is placed within $P$, $P'$ can touch all three of $P$'s edges, and will form a right angle with each of $P$'s edges. Such a triangle $P'$ does not exist for triangles with an angle greater than or equal to $90$ degrees, and does not exist for specific accute triangles. A $P'$ does exist however for every equilateral triangle.

In my belief, the best or perhaps only way of testing this conjecture is by using this "right angle algorithm" on a triangle $P$ to see if such a triangle $P'$ can be found.

Furthur Exploration¶

This project was certainly a lot of fun, however I have many more ideas I would like to explore and questions I would like to have answered. I list some of these below.

Questions & Exploration:

1. Is it possible to create chosen shapes or patterns by passing the some unique engineered polygon to the algorithm?
2. This leads into the question of how this algorithm would respond when applied to higher dimensional shapes. For example, given some 3D shape, and applying some form of this algorithm to it, will other repeating shapes emerge? Other repeating shapes similar to the "outer" 3D shape?
3. In the cases when the algorithm does converge to a triangle, why does it do so? Specifically, what is special about the "molding" characteristics of certain initial triangles that force the ultimate shape into some specific repeating pattern?
4. Do the ranges I defined along the lines describe all the isosceles/scalene triangles that have triangular ultimate shapes?
5. Is there anything particularly special about the equilateral triangle and its predictable ultimate shape? Or is the equilateral triangle just a triangle that happens to have a triangular ultimate shape?
6. Is there anything particularly special about the critical points that bound the ranges?
7. One of the next things I would like to explore is what kind of repeating shapes, if any, this algorithm would produce on any polygon other than a triangle. For every polygon, does there exists at least one repeating shape that can be developed by applying this algorithm to it?
8. I would like to continue searching for an exact formula that can be used to find the side lengths of any interior ultimate triangle given the initial triangle (assuming a formula of this kind exists).
9. A fun project I am currently working on is a second program that can be used to recursively nest these "ultimate triangles" within eachother, to create some rather visually appealing patterns.