Comment programmer une fractale?
https://stackoverflow.com/questions/425953
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je n'ai aucune expérience de la programmation des fractales. Bien sûr, j'ai vu les fameuses images de Mandelbrot et autres.
Pouvez-vous me fournir des algorithmes simples pour les fractales.
Le langage de programmation n'a pas d'importance, mais je connais surtout ActionScript, C #, Java.
Je sais que si je recherche des fractales sur Google, j'obtiens beaucoup d'informations (compliquées), mais je voudrais commencer avec un algorithme simple et jouer avec.
Des suggestions pour améliorer l'algorithme de base sont également les bienvenues, comme la façon de les fabriquer dans ces couleurs magnifiques et autres.
La solution
Programmer le Mandelbrot est facile.
Mon code quick-n-dirty est présenté ci-dessous (non esquissé, mais un bon contour).
Voici le contour: L'ensemble de Mandelbrot se situe complètement dans un cercle de rayon 2 dans la grille complexe.
Alors, commencez par balayer tous les points de cette zone rectangulaire. Chaque point représente un nombre complexe (x + yi). Itérer ce nombre complexe:
[nouvelle valeur] = [ancienne valeur] ^ 2 + [valeur originale] tout en gardant une trace de deux choses:
1.) le nombre d'itérations
2.) la distance de [nouvelle valeur] à l'origine.
Si vous atteignez le nombre maximal d'itérations, vous avez terminé. Si la distance par rapport à l'origine est supérieure à 2, vous avez terminé.
Une fois terminé, colorez le pixel d'origine en fonction du nombre d'itérations effectuées. Passez ensuite au pixel suivant.
public void MBrot()
{
float epsilon = 0.0001; // The step size across the X and Y axis
float x;
float y;
int maxIterations = 10; // increasing this will give you a more detailed fractal
int maxColors = 256; // Change as appropriate for your display.
Complex Z;
Complex C;
int iterations;
for(x=-2; x<=2; x+= epsilon)
{
for(y=-2; y<=2; y+= epsilon)
{
iterations = 0;
C = new Complex(x, y);
Z = new Complex(0,0);
while(Complex.Abs(Z) < 2 && iterations < maxIterations)
{
Z = Z*Z + C;
iterations++;
}
Screen.Plot(x,y, iterations % maxColors); // depending on the number of iterations, color a pixel.
}
}
}
Certains détails laissés de côté sont:
1.) Apprenez en quoi consiste exactement le carré d'un nombre complexe et comment le calculer.
2.) Déterminez comment traduire la région rectangulaire (-2,2) en coordonnées d'écran.
Autres conseils
Vous devriez en effet commencer par le ensemble Mandelbrot et comprendre en quoi il consiste réellement.
L’idée sous-jacente est relativement simple. Vous commencez avec une fonction de variable complexe
f (z) = z 2 + C
où z est une variable complexe et C est une constante complexe . Maintenant vous le parcourez à partir de z = 0, c’est-à-dire que vous calculez z 1 = f (0), z 2 = f (z 1 ) , z 3 = f (z 2 ) et ainsi de suite. L'ensemble des constantes C pour lesquelles la séquence z 1 , z 2 , z 3 , ... est borné , c’est-à-dire qu’il ne va pas à l’infini, est l’ensemble de Mandelbrot (ensemble noir dans la figure de la page Wikipedia).
En pratique, pour dessiner l'ensemble de Mandelbrot, vous devez:
- Choisissez un rectangle dans le plan complexe (par exemple, du point -2-2i au point 2 + 2i).
- Couvrez le rectangle avec une grille rectangulaire appropriée de points (par exemple, 400 x 400 points), qui sera mappée en pixels sur votre moniteur.
- Pour chaque point / pixel, prenons C comme point, calculez, par exemple, 20 termes de la séquence itérée correspondante z 1 , z 2 , z 3 , ... et vérifiez s’il "va à l’infini". En pratique, vous pouvez vérifier, en effectuant une itération, si la valeur absolue de l'un des 20 termes est supérieure à 2 (si l'un des termes le permet, les termes suivants sont garantis comme étant non liés). Si un z_k le fait, la séquence "va à l'infini"; sinon, vous pouvez le considérer comme limité.
- Si la séquence correspondant à un certain point C est délimitée, tracez le pixel correspondant sur l'image en noir (car il appartient à l'ensemble de Mandelbrot). Sinon, dessinez-le dans une autre couleur. Si vous voulez vous amuser et créer de jolis graphes, dessinez-le de différentes couleurs en fonction de la magnitude des abdominaux (20ème trimestre).
Le fait étonnant concernant les fractales est de savoir comment obtenir un ensemble extrêmement complexe (en particulier, la frontière de l'ensemble de Mandelbrot) à partir d'exigences simples et apparemment anodines.
Profitez!
Si les nombres complexes vous donnent mal à la tête, vous pouvez formuler un large éventail de fractales à l’aide d’un système en L. Cela nécessite quelques couches en interaction, mais chacune est intéressante.
Vous avez d’abord besoin d’une tortue. En avant, en arrière, à gauche, à droite, Pen-up, Pen-down. Il y a beaucoup de formes amusantes à créer avec des graphiques de tortue utilisant la géométrie de tortue, même sans système L le pilotant. Recherchez "LOGO graphics" " ou "graphiques de tortue". Un système complet de LOGO est en fait un Lisp en utilisant un environnement de programmation non chiffré syntaxe Cambridge Polish . Mais il n’est pas nécessaire d’aller aussi loin pour obtenir de jolies images en utilisant le concept de tortue.
Ensuite, vous avez besoin d’une couche pour exécuter un système-L. Les systèmes L sont liés aux Post-systèmes et Systèmes de Semi-Thue , et comme Virii, ils chevauchent la frontière de la complétude de Turing. Le concept est la réécriture de chaîne . Il peut être implémenté sous la forme d'une macro-expansion ou d'un ensemble de procédures avec des contrôles supplémentaires pour lier la récursivité. Si vous utilisez une macro-expansion (comme dans l'exemple ci-dessous), vous aurez toujours besoin d'une procédure pour mapper les symboles sur les commandes de tortue et d'une procédure pour parcourir la chaîne ou le tableau afin d'exécuter le programme de tortue codé. Pour un ensemble de procédures de récursivité liée ( par exemple ), vous intégrez les commandes tortue dans les procédures et ajoutez des contrôles de niveau de récursivité à chaque procédure ou factorisez-les en une fonction de gestionnaire.
Voici un exemple d'arbre de Pythagore en post-scriptum utilisant une macro-expansion et un ensemble très abrégé de commandes de tortues. Pour quelques exemples en python et mathematica, voir mon code défi golf .
Il existe un excellent livre intitulé Chaos and Fractals qui contient un exemple de code simple à la fin de chaque chapitre qui implémente une fractale ou un autre exemple. Il y a longtemps, quand j'ai lu ce livre, j'ai converti chaque exemple de programme (dans un dialecte de base) en un applet Java s'exécutant sur une page Web. Les applets sont ici: http://hewgill.com/chaos-and-fractals/
L'un des exemples est une implémentation simple de Mandelbrot.
Une autre excellente fractale à apprendre est la fractale de Triangle de Sierpinski.
En gros, tracez les trois coins d’un triangle (un équilatéral est préférable, mais n’importe quel triangle fonctionnera), puis commencez par un point P à l’un de ces coins. Déplacez P au hasard vers l’un des 3 coins et tracez un point à cet endroit. De nouveau, déplacez P à mi-chemin vers n’importe quel coin, tracez et répétez.
Vous penseriez que le mouvement aléatoire créerait un résultat aléatoire, mais ce n'est pas le cas.
Le triangle de Sierpinski et la courbe de Koch sont des types spéciaux de fractales de flamme. Les fractales de flamme sont un type très généralisé de système de fonctions itéré, car ils utilisent des fonctions non linéaires.
Un algorithme pour IFS est le suivant:
Commencez par un point aléatoire.
Répétez plusieurs fois les opérations suivantes (au moins un million, selon la taille de l'image finale):
Appliquez l'une des N transformations prédéfinies (transformations de matrice ou similaires) au point. Un exemple serait que multiplier chaque coordonnée avec 0,5.
Tracer le nouveau point à l'écran.
Si le point se trouve en dehors de l'écran, choisissez-en un au hasard à la place.
Si vous voulez de belles couleurs, laissez la couleur dépendre de la dernière transformation utilisée.
Je commencerais par quelque chose de simple, comme un Koch Snowflake . Il s’agit d’un processus simple qui consiste à transformer une ligne en une ligne puis à la répéter de manière récursive jusqu’à ce qu’elle paraisse nette.
Quelque chose de très simple, comme prendre 2 points (une ligne), ajouter un 3ème point (faire un coin), puis répéter chaque nouvelle section créée.
fractal(p0, p1){
Pmid = midpoint(p0,p1) + moved some distance perpendicular to p0 or p1;
fractal(p0,Pmid);
fractal(Pmid, p1);
}
Je pense que vous ne pouvez pas voir les fractales comme un algorithme ou quelque chose à programmer. Fractals est un concept! C’est un concept mathématique de motif détaillé qui se répète.
Vous pouvez donc créer une fractale de nombreuses manières, en utilisant différentes approches, comme le montre l'image ci-dessous.
Choisissez une approche, puis étudiez comment l’appliquer. Ces quatre exemples ont été mis en œuvre à l'aide du Framework Marvin . Les codes sources sont disponibles ici
Le jeu mandelbrot est généré en évaluant de manière répétée une fonction jusqu’à ce qu’elle déborde (une limite définie), puis en vérifiant le temps qu’il vous a fallu pour déborder.
Pseudocode:
MAX_COUNT = 64 // if we haven't escaped to infinity after 64 iterations,
// then we're inside the mandelbrot set!!!
foreach (x-pixel)
foreach (y-pixel)
calculate x,y as mathematical coordinates from your pixel coordinates
value = (x, y)
count = 0
while value.absolutevalue < 1 billion and count < MAX_COUNT
value = value * value + (x, y)
count = count + 1
// the following should really be one statement, but I split it for clarity
if count == MAX_COUNT
pixel_at (x-pixel, y-pixel) = BLACK
else
pixel_at (x-pixel, y-pixel) = colors[count] // some color map.
Notes:
La valeurest un nombre complexe. un nombre complexe (a + b i) est mis au carré pour donner (a a-b * b + 2 * a b i). Vous devrez utiliser un type complexe ou inclure ce calcul dans votre boucle.
Voici un code simple et facile à comprendre en Java pour mandelbrot et d'autres exemples fractals
http://code.google.com/p/gaima/wiki/VLFImages
Téléchargez simplement le fichier BuildFractal.jar pour le tester en Java et exécutez-le avec la commande suivante:
java -Xmx1500M -jar BuildFractal.jar 1000 1000 par défaut MANDELBROT
Le code source est également gratuit à télécharger / explorer / modifier / développer.
Eh bien, simple et graphiquement attrayant ne va pas vraiment de pair. Si vous êtes sérieux au sujet de la programmation des fractales, je vous suggère de lire plus en détail les systèmes de fonction itérés et les progrès accomplis en matière de rendu.
Les personnes ci-dessus utilisent la recherche de points médians pour sierpinski et Koch. Je recommanderais davantage de copier et de redimensionner des formes, puis de les traduire pour obtenir le résultat "fractal". effet. Le pseudo-code en Java pour sierpinski ressemblerait à ceci:
public ShapeObject transform(ShapeObject originalCurve)
{
Make a copy of the original curve
Scale x and y to half of the original
make a copy of the copied shape, and translate it to the right so it touches the first copied shape
make a third shape that is a copy of the first copy, and translate it halfway between the first and second shape,and translate it up
Group the 3 new shapes into one
return the new shape
}
Parfois, je programme des fractales pour le plaisir et comme défi. Vous pouvez les trouver ici . Le code est écrit en Javascript avec la bibliothèque P5.js et peut être lu directement à partir du code source HTML.
Pour ceux que j'ai vus, les algorithmes sont assez simples, il suffit de trouver l'élément principal et de le répéter encore et encore. Je le fais avec des fonctions récursives, mais je peux le faire différemment.
