Web Page
"Who is Will and why do they keep firing at him?" - Muneer
Main Pictures About Best Psych Blog login

Sierpinski's triangle

When I was in high school, I was doing some work on evolutionary models and competition. While I was doing that using binary grids, I discovered a simple pattern that mimicks Sierpinski gasket which is made using the Chaos game or by recursively dividing the sides of a triangle. This method however does not create ever small triangles, but makes progressively larger ones. IE, it is not truly a fractal, but can be used to generate the image of one.

So how does this work? Let me explain using words prior to providing the algorithm. First, you begin with a grid - such as a graph paper. Start at the top of the grid in the center box. Place an X in that box. now you will move down one row and construct this row using the row above it. The rule is simple. For every box in this row, place an X if one and ONLY one diaganol in the row above it has an X. once done with this row, repeat for every row below it. This will give you an image similar to a Sirpinski triangle.

Next step. breaking this down algorithmically
assume a matrix of size M rows and 2 * M - 1 columns
we will define this matrix as grid[M][2 * M - 1]. Furthermore, just so the triangle looks complete, let us say that a full triangle will be made for all M such that M > 0 and that for all integers n, M is in the set of 2^n.

then in pseudocode, what we have in the above is

binary grid[M][2*M - 1];
integer i, j;

grid[0][M] = 1;
for i = 1 to M - 1
for J = 0 to 2 * M - 2
if grid[i - 1][j - 1] xor grid[i - 1][j + 1] == 1 then
grid[i][j] = 1
grid[i][j] = 0
end if
next i

notes on the above code. First, one the final row, it will try to address an area out of bounds using most computer languages. you may need to pad a 0 containing column on either side (a column at -1 and at 2 * M).

So, on more analysis, one may see that there is a relationship between this triangle and Pascal's triangle. If we were to write out Pascals triangle with the following transformation, one would see that it is identical to the above expansion. for every number in the triangle do n mod 2.

References for thsoe wanting more information:
Pascal's Triangle

Sierpinski triangle

Post by User: muneer
interesting.....its been too long since i did math.....and the pseudocode will have to be explained to me......

You must be logged in to post a reply


Your post