  ### Generalized Sierpenski Fractals

This article introduces a type of fractal that can be generated with no more arithmetic than averaging, and yet yields a large number of different interesting images. ### Introduction ### The Sierpinski Triangle

The Sierpinski triangle is an example of a fractal that can be generated with a simple algorithm. Let's start by giving the algorithm for the Sierpinski triangle itself. Later we will generalize the algorithm.

# Sierpinski Algorithm

```Choose three points (the triangle's vertices).

Create a moving point P.
Start P on one of the vertices.

Repeat
Pick one of the three vertices at random,
Move P half way to the selected vertex,
Plot P.
Until the triangle fills in
```

The more points you generate, the more the triangle fills in. The examples below show roughly how the triangle fills in as you plot more points.

### Algorithm Progress   1000 points 2000 points 3000 points   4000 points 5000 points 6000 points

The above images speak to one of the advantages of the moving point algorithm for the Sierpinski triangle: speed and uniform fade-in. With only 1000 points plotted the triangle is already visible. If you are trying to get a fractal to appear right away, the moving point algorithm yields immediate results that improve with time.

### The Influence of the Corners

Let's look at how the points behave by coloring them. First we will associate the colors red, green, and blue with the vertices of the triangle and show, by color intensity, how many times various plotted points were moved toward the corners in their recent past. We increase the intensity of a color each time we move toward its associated corner and decrease the intensity otherwise.

### Algorithm Progress, By Corners         2000 points 4000 points 6000 points

Now, look at the Sierpinski triangle we get by merging the three colored corners to get a colorful display of the influence of all three vertices. Click the image for a larger version. All the Sierpinski triangles we've seen so far have their three vertices chosen to be the vertices of an equilateral triangle. This was done for reasons of tidiness, not necessity. If you move one of the corners and rerun the algorithm, the triangle moves smoothly along with the corner. As a demonstration of this we offer the following animation. A Dancing Sierpinski Triangle

# Sierpinski "Squares"   50% 48% 46%

When recreational programmers first hear about the Sierpinski triangle, they want to generalize it. The natural thing to do is to try running the algorithm with a different number of points, like 4. With four points what you end up doing is moving by halves on the horizontal and vertical axies. The result? The square just fills in. The left image above is just such a filled in square, with a red, green, yellow, and blue corner so that you can get a sense of the influence of the corners.

One method of trying to make the filled-in square look interesting yields a useful generalization. If you move less than half way to the corner of the square you've randomly selected then you don't fill in the square. The middle and right images, above, show what happens when you take the moving point 48% or 46% of the way to the corner. The next idea we need is that of a Markov chain. A Markov chain is a probabilty system with a bit of memory. In this case the system will remember what corner was just picked when picking the next one. Instead of picking any corner of the square for the moving point to move toward, the Markov chain only allows some corners to be next. Which corners you can pick next for the moving point to move toward will depend on which one you just picked. It is easiest to summarize this sort of thing with a diagram like the one to the left. Each corner points at the corners you can pick next if you just picked it.

What the diagram says is that, from a given corner, you can pick the same corner again, the corner counter-clockwise of the current one, or the corner diagonally across from the current one. The only corner you cannot pick is the one clockwise of the current corner. We call this diagram the Markov dependency for the fractal. With this restriction on the next corner in place, let's generate the resulting limited Sierpinski square and see what it looks like:

### The counterclockwise generalized Sierpinski square

Now we can combine our two generalizations. In addition to limiting which corner can come next, we can change the percent of the distance to the next point that we move. For the full Seirpinski squares, there was no empty space when we moved half way to the point that was picked. This means the only sensible option was reducing the fraction of the way to the next point we moved. The counter-clockwise Seirpinski square has empty space when the move is set to 50%. This means we could move more than half way as well as less.

 Moving various fractions of the way to the chosen corner   45% 50% 55%

One way to understand what is happening to the moving point is to think of its new position as a weighted average of its old position with the position of the point we picked. If we set the distance moved to 50%, then it is just the standard average. For fractions other than 50% it is a weighted average. Below 50%, when the weighting favors the current position of the moving point, the fractal gets sparser. Above 50%, when the weighting favors the point you are moving toward, the fractal gets fuzzier. We call this parameter the averaging parameter for the fractal. Turning this parameter up and down lets us make the fractal more or less sparse in a continuous fashion.

Now let's take a look at what happens when we change the Markov dependency in three different ways:

 Changing the Markov dependencies      Hourglass Lilly Menu Border

There is no reason we are limited to a triangle, square, or any other particular shape. Any set of points could be used. We can place whatever Markov dependency on them we wish. We can pick the averaging parameter as we wish. Finally we can assign a different color to each point, averaging that color into the current color when the point is picked. There is one additional problem: if some points cannot ever be reached from others, then they are ignored. This problem is solved by having one moving point for each fixed point, initialized to start on that fixed point.

# Generalized Sierpinski Algorithm

```Choose a set of points S in the plane.

Choose for each s in S a subset T of S
that are the possible next points that
can be chosen after s.  This is the
Markov dependency.

Choose an averaging parameter A.

Create a set of moving points P.

Assign a color to each point in S.

Initialize a current color for each moving point.

Start each p in P on a distinct s in S.

Repeat
For each moving point p
Pick a valid next point n.
Move A of the way toward n.
Average n's color with p's current color.
Plot p in the new color.
End for
Until the fractal fills in
```

### Building Generalized Sierpinski Fractals

Now we're going to look at these fractals and see what some examples look like.

For the now familiar fractal shown above, the specification is as follows (notice that the positive y-axis is downward).

 ```4 //number of points in S 0.5 //averaging parameter (0,0) //point 0 position (1,0) //point 1 position (1,1) //point 2 position (0,1) //point 3 position 0 : 0,2,3 //points that may follow 0 1 : 0,1,3 //points that may follow 1 2 : 0,1,2 //points that may follow 2 3 : 1,2,3 //points that may follow 3 ```

Here are other examples in the same format. They still use a set of points S that are all on a circle. Notice, also, that all the points are in the unit square. The x and y coordinates are all between 0 and 1.

 Five points, stay or move 2 or 3 counter-clockwise. ```5 0.618033 0.5 1 0.0244717 0.654508 0.206107 0.0954915 0.793893 0.0954915 0.975528 0.654508 0 2 3 1 3 4 2 4 0 3 0 1 4 1 2 ``` Six points, stay or move 2, 3, or 4 counter-clockwise. ```6 0.50 0.960 0.500 0.750 0.066 0.250 0.066 0.040 0.500 0.250 0.933 0.750 0.933 0 2 4 3 1 3 5 4 0 2 4 5 1 3 5 0 0 2 4 1 1 3 5 2 ``` It is practical to make far more complex fractals in this manner. The examples below have many points and carefully chosen colors assigned to the points to yield the given appearances. Click on the images to get larger versions.

Back to Blog