[scotty79]

I really don't see how any proof is necessary.

Taking midpoint between a point and tringle vertex is a transformation that scales everything by 1/2 with this vertex as pivot.

By choosing one of such three transformations randomly you are scaling the whole triangle into three smaller copies of itself that it cosists of.

If you start with a point belonging to Sierpinski trinagle, you are adding more and more points belonging to that triangle.

Fun thing is that you can use the same algorithm with different number and kind of transformations to get other fractals with such random walk. For exaple a fractal tree or fern leaf or Sierpinski carpet.

Another interesting thing is you can start with a point not belonging to a fractal and it pretty quickly coverges. It's because fractals are attractors.

[codeflo]

But you don’t start with a point belonging to the triangle, that’s the whole idea!

[gus_massa]

There are probably many better explanations out there, but I'll try one:

It's important t note that if you pick any point p in the Sierpinsky triangle and you calculate f1(p), f2(p) and f3(p) you get tree points that are also in the Sierpinsky triangle. [f1, f2, f3 as defined in the top comment]

---

You pick any point in the plane, let's call it q, and you draw it in the screen.

You pick any point in the Sierpinsky triangle, let's call it p, p is a secret point.

The important number is the distance between p and q. You could have pick a better point in the Sierpinsky triangle but anyone you have choose is fine.

Now you select one of the functions f1, f2, f3, let's call it f. And you calculate p'=f(p) and q'=f(q) (the same functions for both).

Now you have two new points p' and q'. p' is a again a point in the Sierpinsky triangle as I said at the beginning. q' is a point that you draw in the screen.

Again, the important number is the distance between p' and q'. What happens if you compare the distance between p' and q' with the initial distance between p an q? The new distance is one half of the initial distance, so q' is closer to p'. You could have pick a better initial point p in the Sierpinsky triangle or pick now a better point p*in the Sierpinsky triangle but don't worry, p' is fine.

And now you repeat the process with cut&paste...

You select one of the functions f1, f2, f3, let's call it f. It may be the same functions as before or another one. You calculate p''=f(p') and q''=f(q') (the same functions for both).

Now you have two new points p'' and q''. p'' is a again a point in the Sierpinsky triangle as I said at the beginning. q'' is a point that you draw in the screen.

Again, the important number is the distance between p'' and q''. What happens if you compare the distance between p'' and q'' with the previos distance between p' and q' and the initial distance between p an q? The new distance is one half of the previous distance and one quarter of the initial distance, so q'' is closer to p''. You could have pick a better initial point p in the Sierpinsky triangle or pick now a better point p**in the Sierpinsky triangle but don't worry, p'' is fine.

And now you repeat the process with cut&paste...

...

After enough halvings, the distance between p'''''...'''' and q'''''...'''' is smaller that any level of precision you select initially, like 1E-15. If you need more precision because you are using a high zoom level, just add more steps and more halvings.

Now you have a sequence of points q, q', q'', q''', q'''', ... that are drawn in the screen and p, p', p'', p''', p'''', ... that are only in your imagination.

Except a few of the initial points, all the other points q'''''...'''' are very close to the Sierpinsky triangle. One trick is to not draw the initial 1000 points, so you don't get some points in weird locations. You should prove that 1000 is enough, or use a bigger number or just cross your fingers and hope nobody notices them.

Note that this method actually doesn't draw the Sierpinsky triangle. It just draw a cloud of points that very close to the Sierpinsky triangle. (Unless you are very lucky, and the initial point q is also in the Sierpinsky triangle or something like that.)

[scotty79]

Yeah, it's easier if you don't start with a random point in a triangle (it doesn't even have to be in a triangle) but with one of the vertices.

To understand why you can start with any point you'd have to understand why fractals are attractors and that's some serious math I presume, with epsilons and quantifiers.

[floatingatoll]

Tell us some more serious math! You’re doing great so far and that’s where the “huh?” ends up answered.

[klyrs]

The point here is that you'll almost certainly end up inside the Sierpinski triangle within a logarithmic number of steps.

Let's do the 1-dimensional version, the Cantor set.

  init_x = (anything)
  while 1:
    draw(x)
    if flip_coin() == HEADS:
       x = (x+1)/2
    else:
       x = x/2

Supposing we start with a large negative number N, and our coin is secretly TAILS on both sides, our sequence will be

  N, N/2, N/4, N/8, N/16...

So we'll rapidly converge on the point 0, but never quite make it into the interval [0, 1] because N is negative. But, if we draw our point with a diameter of say, 1/128, it will rapidly become visually indistinguishable from zero.

If the coin is fair, then something really cool happens -- if we hit a HEADS and x was already in the interval [-1, 0] then our result will be in the interval [0, 1/2] -- which is inside the interval [0, 1] where the problem is easier to think about. Approaching the problem in this way requires a bunch of case analysis, but the gist is that an attractor will quickly suck any point into the fractal -- if you get really unlucky, it will only get very close to the fractal in question.

[scotty79]

I'd be happy to tell you if I actually knew it. I just know it exists. Sorry if I gave the wrong impression.

If I were to look for it I think I'd search for proof that Iterated Function System has a fixed point or attractor https://en.m.wikipedia.org/wiki/Iterated_function_system

[jheriko]

the algorithm ensures that the point is approximately in the triangle. using the midpoint with one of the vertices, excludes the triangle in the middle...