An algorithm

[Mark]

Hello,
I am new to these forums and was unsure where to post this topic. Since last summer I've been generating two dimensional plots of algorithmic, discontinuous functions which consist of an iterating element I refer to as a 'particle' and two or more poles with constant position. Both poles and the particle have an x and y coordinate on the two dimensional plane but only the particle changes its position, relative to the distances and directions from particle to either pole. This sounds more complicated than it is, the following is an image of the parameters used by my algorithm:



The position of the particle is written to a two dimensional voxel map array[1600,900] with dimensions corresponding to my computer screen size (for example if the particle is at position paritcle.x=123.456; particle.y=654.321; the algorithm would round the positions to the nearest integer and add 1 occurrence as follows: array[123,654]+=1;) after a million or so steps the relative occurrences are plotted to the screen. (from left to right low to high occurrences: black -> brown -> orange -> yellow → green → blue ->purple ->pink-> white).

A very simple, yet the most interesting algorithm yields the following image:


In this algorithm the particle has a 50% chance of either moving towards pole A at length BP or towards pole B at length AP.

I've been trying to find any form of information to this simple algorithm but couldn't find anything on the internet or from my friends in university.

Regards,

Mark

[kram1032]

Nice image.
If I understand you right, each step the particle is randomly attracted by one of two poles.
How far does it travel towards the attracted pole? Your image suggests that AP and BP are the distance from each pole of the particle. If it were to travel exactly that distance, it'd just end up at precisely the two points of the pole, so it can't be that.

Is the particle traveling a relative amount or a fixed amount?
Like, say, the distance to the pole it currently is attracted to is 5. Will it travel, like 20% of the way (1 distance) or will it always travel, say, .5 distance no matter the distance from the pole?

In case it is the relative kind, this seems related to the random Sierpinski triangle:
http://www.jcu.edu/math/vignettes/chaosgame.htm
Which would be the same idea but with 3 poles instead of 2 and without discretization (rounding to integer)

Edit: Though the Chaos Game would never give rise to such images.
http://mathworld.wolfram.com/ChaosGame.html

[Mark]

I've run this with up to 12 poles but It never resulted in a Sierpinski gasket fractal. I did not use any factors for the above algorithm. By chance either Pole A or Pole B is chosen. If pole A is chosen, the distance from the particle to pole B is measured (hence distance PB) and the particle is displaced in the direction towards pole A at the distance to pole B. No factors:
This image explains it a bit better:


the black point P is the starting position, and the green point P_new is the new position.
edit: I forgot to label the distance from P to P_new. It should be labeled BP with a line on top, since it is equivalent in length to the distance between P and B.

A more classical way to describe my algorithm, Euclidean style:

Flip a coin. If it's heads draw a line PA that passes through point P and A and a circle O that passes through B and has point P as its center. Where the Line PA intersects the circle O, is the new position of the particle.
If it's tails draw a line PB that passes through point P and B and a circle O that passes through A and has point P as its center. Where the Line PB intersects the circle O, is the new position of the particle.

[cKleinhuis]

it definately is related to the chaos game, but you are using a different method to generate a new point, in the chaos game the exact halve distance is taken from a choosen point to the current, and you do some different approach

i wonder how you handle more than 2 poles, how does the relative position of the poles and the starting points affect the resulting image !?

i think  you do not need to discretize your point all the time, the discretisation should be only done when inserting it into the map, that way your result might differ and produce a more decent attractor area

in the chaos game it does not matter where the starting point resides, after a few iterations the attractor area is reached and basically never left

[Mark]

When I started to make this algorithm I didn't first enumerate all the positions of one particle, instead I created 2k to 20k independent particles with a random starting position that all followed the same algorithm, one of my objectives was to create an algorithm that wouldn't end up at either poles (=attractor), but rather enter a stable orbit around the poles. I believe that this algorithm does just this. Independent of the starting position, the particle will end up after very few steps on a position on the field, and stay in that field for eternity, I do not have any mathematical proof for this but I'd say its a safe assumption. What do you mean by 'generate a more decent attractor area' ?

[kram1032]

Thanks for the clarification. Makes sense now

I can give you a simple counter-example when that is not the case:

If your particle P happens to be equidistant from two different poles A and B (e.g. the two poles lie on a circle of radius equal to the distance from the particle) and the chosen pole distance is either A or B and the chosen pole to hone in on is the other of the two, your particle will end up exactly at A or at B.

This also works with more poles. Once any two poles happen to be the same distance from the particle, there is a chance the particle will land on a pole. And discretizing will enhance to probability of that happening, since all distances within a unit length will be equal, as far as the algorithm is concerned.

And for the Chaos game, unless you start within a given attractor, the point will actually never be exactly on the attractor, although it will approach it arbitrarily closely.

[cKleinhuis]

When I started to make this algorithm I didn't first enumerate all the positions of one particle, instead I created 2k to 20k independent particles with a random starting position that all followed the same algorithm, one of my objectives was to create an algorithm that wouldn't end up at either poles (=attractor), but rather enter a stable orbit around the poles. I believe that this algorithm does just this. Independent of the starting position, the particle will end up after very few steps on a position on the field, and stay in that field for eternity, I do not have any mathematical proof for this but I'd say its a safe assumption. What do you mean by 'generate a more decent attractor area' ?

i meant that you create an excess of rounding errors in the long run, so, i assume the result would differ slightly when you do not round in every step,
the border of your area would become a little more washed out

[Mark]

No, there there is a sharp cutoff point for the thing, it hasnt to do with rounding mistakes. The Positions of the particles are 32bit floating points, which is not rounded in every step. When the particles positions are written to a separate array of fixed size, then the positions must be rounded. I could increase the resolution to 3200x1800 and probably yes, it woud be a bit smoother, but I find it clear enough for my purposes.

The Orbits often show fractal like patterns, I can remember rendering something similar to this:



The Chaos Game shares elements with my approach, so this comes to no surprise. I've read of the chaos game, I guess I shoud have read more on the subject. But something about the Image that I started this thread with intrigues me and makes me believe it is connected to other things than I am aware of. For example I was thinking about how the particle jumps from from one location to another and if it ispossible to bend the two dimensional plane in such a way that it creates a continuous trajectory... this may or may not require more than 3 dimensions but certainly goes way too much into math topology than I can comprehend.

[cKleinhuis]

aha, now we are talking the above upper left definately is a form of "cantor dust"  http://en.wikipedia.org/wiki/Cantor_set more specific a 2dimensional variant of it, known as the sierpinski carpet
http://en.wikipedia.org/wiki/Sierpinski_carpet and there is a 3d equivalent as well, which i expect to arise from a 3dimensional implementation of yours http://en.wikipedia.org/wiki/Menger_sponge


there is a nice anecdote concerning the chaos game, because the inventor once stated that any image can be resembled through an iterated functions system ( which is how the chaos game is actually calculated) with the only drawback that it would consume far more input data than just the pixels of the image

what you have here is a attractor ( please correct me if i am wrong ) which means that your resulting image is determined by the configuration ( the propability of the points, and the rules ) so, what you do have here is an iterated function system ( not using affine transformations, but hey, a function is a function .... )

what you see as a result is determined by your starting config, so, definately it proves that random/propabilistic approaches lead to deterministic results, e.g. the upper left two images of yours recent image

it is a chaotic process, and it is a quite interesting approach, extending it to a 3 dimensional point set up should be no problem

and yes, if you find some topological answers that arise from it, you are welcome to share your insights, but this is quite above my head as well

nevertheless, we are quite interested in all approaches that lead to fractal structures, and you have given obviously a method to achieve a sierpinski carpet through a different approach, the insight may lay somewhere else, because - in my point of view - certain methods lead to similar ( if not equal ) results, we have developed quite a few approaches on how to achieve certain already known fractals through different methods

you might be interested in "the scale -2 mandelbox" and the "space folding fractals"
because i just want to advertise my own show, get an idea of what is inside the mandelbox using my video:
<a href="https://www.youtube.com/v/UEtWydW50VI&rel=1&fs=1&hd=1" target="_blank">https://www.youtube.com/v/UEtWydW50VI&rel=1&fs=1&hd=1</a>

and the mandelbox which has been encountered here in the forums from the page of its inventor, contains many different fractals ( along the sierpinski carpet )
https://sites.google.com/site/mandelbox/what-is-a-mandelbox

and the generalised folding providing a menger sponge, i am afraid i do not have the direct link in the forums here, but it is called "KIFS" which just folds the space around certain lines to get classic fractals like the sierpinski or the menger sponge!

[kram1032]

cKleinhuis, that last image of his was not output of his algorithm but rather variations of the chaos game, as found here (last image)
http://mathworld.wolfram.com/ChaosGame.html

He just said his algorithm at times does produce something similar.

Mark are the attractors you get always bounded? I may be wrong but I have a feeling that certain setups (certain starting positions for your particle) could actually cause the whole image to explode as distances happen to grow and grow. Randomness would probably make this rare but I can see it potentially happen.

The Chaos Game is guaranteed to never grow unboundedly because the distance to the attractor, which is fully bounded by the convex hull of all the poles or corner points you set, keeps shrinking proportionally.
(Actually this makes me wonder: In a projective setting, you could add in the point at infinity and, instead of using euclidean lengths, you could use projective arc distances or something like that. As a result you should get the equivalent of a sierpinski triangle with an additional attractor at infinity. How would that look like?)

Of course this isn't a requirement for your algorithm. If it sometimes diverges, it might still give pretty pictures. Though it's kind of a neat feature of the chaos game. (I say just after proposing a way to make a chaos game with infinity. Talk about hypocrisy <.<)

[Softology]

Mark,

It would be easier if you shared a snippet of code or algorithm to avoid confusion.

Then we all could have a play with these attractors.

Jason.

[cKleinhuis]

cKleinhuis, that last image of his was not output of his algorithm but rather variations of the chaos game, as found here (last image)
http://mathworld.wolfram.com/ChaosGame.html

He just said his algorithm at times does produce something similar.

ah, ok, got it 

[Mark]

Once I get home Ill upload my application and you guys can fool around with it, be ware though its computational power is crap and the built in commandline box is confusing and limited. Im not sure how to implement infinity, nor non-eucledian geometry into the program, but I would be defenitly interested in ways to program this. I was thinking of writing a programm that allows the user to change just the code of the particle while the program is running to make it easier to analyze such algorithms. I can also check my harddrive for more interesting images I generated with the program.

[Mark]

<a href="http://www.youtube.com/v/0KiXAp9oOPw&rel=1&fs=1&hd=1" target="_blank">http://www.youtube.com/v/0KiXAp9oOPw&rel=1&fs=1&hd=1</a>

<a href="http://www.youtube.com/v/MceVsT0SqMY&rel=1&fs=1&hd=1" target="_blank">http://www.youtube.com/v/MceVsT0SqMY&rel=1&fs=1&hd=1</a>

I cannot even remember the exact code I used to iterate the particles. What I do know is that one of the attractors rotates, and that the particles are 'shifted' to the right, as in every step some constant is subtracted from the x coordinate ( x-=constant ).

[kram1032]

Those look nice
Your third video looks great too.
Btw, if you link a YouTube video with the full adress but with http, rather than https, it'll be automatically embedded in the post:
<a href="http://www.youtube.com/v/CiqlJp23R8M&rel=1&fs=1&hd=1" target="_blank">http://www.youtube.com/v/CiqlJp23R8M&rel=1&fs=1&hd=1</a>