Sierpiński and Chaos!
I talked about making Sierpinski triangles by using Pascal's triangle, this time we're going to make the Sierpinski triangle by plotting random points on a graph. Well, by "random" I mean plotting random points that adhere to a set of very simple rules. What are the rules?
1. Take 3 points in a plane to form a triangle, you need not draw it.
2. Randomly select any point inside the triangle and consider that your current position.
3. Randomly select any one of the 3 vertex points of the triangle.
4. Move half the distance from your current position to the selected vertex.
5. Plot the current position.
6. Repeat from step 3.
This is actually a very classic example of the Chaos Game, where fractals are drawn based on plotting points that adhere to a set of simple rules. Anyway, it would be crazy to see this actually work right? How does plotting random points like that make the Sierpinski triangle? Let's see:
Here I plotted 1,000 points based on the rule
1. Take 3 points in a plane to form a triangle, you need not draw it.
2. Randomly select any point inside the triangle and consider that your current position.
3. Randomly select any one of the 3 vertex points of the triangle.
4. Move half the distance from your current position to the selected vertex.
5. Plot the current position.
6. Repeat from step 3.
This is actually a very classic example of the Chaos Game, where fractals are drawn based on plotting points that adhere to a set of simple rules. Anyway, it would be crazy to see this actually work right? How does plotting random points like that make the Sierpinski triangle? Let's see:
Here I plotted 1,000 points based on the rule
10,000 Points:
100,000 Points
1,000,000 Points
I'm sure you can already see this algorithm works, but how?
Here it the catch: None of these points are actually on the Sierpinski triangle itself! These points are actually points in each inverted triangle (removed triangle), but since we repeated the process many times, the inverted triangles are practically the vertices of the upright triangles. If we plot infinite number of points, the side length of the upright triangles approach zero, so does the area of the upright and inverted triangles. Let's take a closer look at this:
Suppose we start with a point somewhere in the middle of the largest white (removed) triangle in the Sierpinski triangle. Where does this point move after one roll of the die? In the picture below, we see that this point hops into one of the three next-smaller triangles, since these triangles represent all points that are half the distance to the three vertices from points in the largest removed triangle. After one more iteration, this point then moves to the next smaller-sized triangle. And so forth.
Here it the catch: None of these points are actually on the Sierpinski triangle itself! These points are actually points in each inverted triangle (removed triangle), but since we repeated the process many times, the inverted triangles are practically the vertices of the upright triangles. If we plot infinite number of points, the side length of the upright triangles approach zero, so does the area of the upright and inverted triangles. Let's take a closer look at this:
Suppose we start with a point somewhere in the middle of the largest white (removed) triangle in the Sierpinski triangle. Where does this point move after one roll of the die? In the picture below, we see that this point hops into one of the three next-smaller triangles, since these triangles represent all points that are half the distance to the three vertices from points in the largest removed triangle. After one more iteration, this point then moves to the next smaller-sized triangle. And so forth.
Eventually (after very few iterations), the point enters a small triangle that is for all intents and purposes invisible. Invisible in our case means smaller than one pixel of our screen... If we plot a point inside a triangle that's smaller than a pixel of our screen, it might be as well be on the vertices.
In actuality, the orbit of a point that starts in any of the removed triangles will never "reach'' the Sierpinski triangle. Rather, it will continue to lie in successively smaller removed triangles. Of course, these removed triangles very quickly become microscopic in size, so for all practical purposes the orbit looks like it lies on S (the Sierpinski triangle). Mathematicians says that the orbit of the seed is attracted to S. Sometimes S is called a strange attractor. (source)
You're probably wondering, "What if, instead of going to the mid-point (0.5 of the way), we only go 0.3 of the way? 0.7?
First, let's look at some extreme examples:
1) If you go all (1) the way, your current location after one iteration will always be on one of the vertices.
2) If you go zero of the way, your current location will always be your initial point.
Not that particularly exciting in my opinion...
But if we go 0.3 of the way:
In actuality, the orbit of a point that starts in any of the removed triangles will never "reach'' the Sierpinski triangle. Rather, it will continue to lie in successively smaller removed triangles. Of course, these removed triangles very quickly become microscopic in size, so for all practical purposes the orbit looks like it lies on S (the Sierpinski triangle). Mathematicians says that the orbit of the seed is attracted to S. Sometimes S is called a strange attractor. (source)
You're probably wondering, "What if, instead of going to the mid-point (0.5 of the way), we only go 0.3 of the way? 0.7?
First, let's look at some extreme examples:
1) If you go all (1) the way, your current location after one iteration will always be on one of the vertices.
2) If you go zero of the way, your current location will always be your initial point.
Not that particularly exciting in my opinion...
But if we go 0.3 of the way:
0.6 of the way:
0.1 of the way:
0.001 of the way:
Now that's what I call exciting! 0.001 can almost be abstract art if you ask me.
Haha, just kidding, 0.001 should actually approach a single point, the line you see is caused by the computer's round-off error.
Haha, just kidding, 0.001 should actually approach a single point, the line you see is caused by the computer's round-off error.
|
Here is an executable JAR file, you can play around with how far the point travels.
|
Note that all the above pictures are based on "how far the current point travels". If we base our algorithm on how far the point is from the origin and calculate from there, we should get different results. (For 0.5 we'd still get the Sierpinski Triangle, of course)
0.3
0.3
0.7
Isn't that fun? I think I should stop here; have fun with your triangles!
|
|
Last updated: 7 May 2015