Ruprecht Karls Universität Heidelberg

Fun Mandelbrot

From Informatik-Vorkurs
Jump to: navigation, search


Weil es Spass macht: ApfelmÀnnchen plotten

Bestimmt kennen Sie die schönen Bilder des 'ApfelmÀnnchens', das die Mathematiker als 'Mandelbrot-Menge' bezeichnen. Infos und sehr schöne Bilder sind bei Wikipedia zu finden. Von da stammt auch dieses Bild:

Mandelbrot Menge (aus Wikipedia)

Wie funktioniert das?

Man betrachtet eine Folge von komplexen Zahlen z(n). Im n-ten Schritt wird aus z(n) eine neue Zahl z(n+1) nach der Formel z(n+1)=z(n)*z(n)+c errechnet. FĂŒr ein festes c (c ist auch eine komplexe Zahl) beginnt man z.B. mit z(0)=0, errechnet z(1)=c, dann z(2)=c*c+c und so weiter. Man iteriert das immer wieder und prĂŒft, ob die Zahlenfolge z(n) divergiert, ob also die z(n) sehr groß werden. Man bricht z.B. ab, wenn der (reelle) Betrag von z(n) grĂ¶ĂŸer als 1000 geworden ist. Das Verhalten der Folge hĂ€ngt nun - ĂŒberraschenderweise ! - sehr von der Wahl von c ab. Das ApfelmĂ€nnchen stellt nun in der komplexen Zahlenebene dar, was fĂŒr die unterschiedlichen c passiert. In der schwarzen Mitte divergieren die Folgen nicht, außen tun sie das. Die FĂ€rbung gibt an, wie schnell die Folge anwĂ€chst, also nach wie vielen Iterationen man z.B. den Betrag 1000 ĂŒberschreitet. Jeder Punkt des Bildes entspricht also einem Punkt der komplexen Zahlenebene c, und in der Farbe ist codiert, wie schnell die Folge der z(n) divergiert.

Ein einfaches Programm

Um ein erstes ApfelmÀnnchen im Textfenster darzustellen, braucht man keine 20 Zeilen Code:

  • Benutzen Sie die <complex> Klasse aus der Standardklassenbibliothek stl, um die Mathematik zu vereinfachen. Finden Sie heraus, wie man eine Variable damit definiert (template!). Den Betrag bekommen Sie dann mit abs(z).
  • Schreiben Sie eine (doppelte) Schleife, die komplexe Zahlen c erzeugt, z.B. je 40 Werte in x und y. Decken Sie z.B. Realteile von -1.5...0.5 und ImaginĂ€rteile von -1.0...1.0 ab.
  • Iterieren Sie jeweils z mit Startwert 0 und bestimmen Sie, wie viele Iterationen benötigt werden, bis der Betrag von z ĂŒber 1000 liegt. Achten Sie darauf, dass die Iteration auch irgendwie abbricht, wenn die Folge nicht divergiert!
  • Geben Sie auf dem Bildschirm ein 'X' oder ein ' ' aus, je nachdem ob es weniger oder mehr als (z.B.) 20 Iterationen dauert.

Farbgrafik

Um eine schöne Farbgrafik zu erstellen, können wir z.B. ein Grafikfile erzeugen, und dieses dann mit einem geeigneten Programm anschauen. Die ĂŒblichen Pixel-Formate benötigen jeweils noch diverse Zusatzinformationen, die die Erzeugung erschweren. Eine einfache Möglichkeit ist wieder die Nutzung von Postscript. Der folgende Postscript Code erzeugt eine einfache Farbgrafik mit 2x2 Pixeln:

%!PS
2.835 dup scale  % one unit = 1mm
5 30 translate   % shift 5mm right and 30mm up
200 200 scale    % one unit (=image size) = 20 cm
/PicW    2 def   % number of pixels in X (A)
/PicH    2 def   % number of pixels in Y (B)
/picstr { 3 PicW mul string } bind def
PicW PicH 8 [PicW 0 0 PicH neg 0 PicH] {currentfile picstr readhexstring pop} false 3 colorimage
0000ff00ff00
ff0000ffffff
showpage

Probieren Sie das aus, indem Sie den Code in ein test.ps File ĂŒbertragen und mit ghostview test.ps & oder (auf den CIP pool Rechnern) mit evince test.ps & anzeigen lassen.

Zum VerĂ€ndern des Bildes mĂŒssen nur die Zeilen (A), (B) und die 2 Zeilen vor 'showpage' modifiziert werden:

  • Zeile (A) legt die Anzahl der Pixel in x-Richtung fest, hier NX=2
  • Zeile (B) legt die Anzahl der Pixel in y-Richtung fest, hier auch NY=2
  • Die Zeilen vor 'showpage' enthalten die Farbinformation fĂŒr NX*NY Pixel, und zwar 24 Bit pro Pixel, die sich in je 8 Bit fĂŒr Rot, GrĂŒn und Blau aufteilen. Die RGB Werte reichen also jeweils von 0 bis 255. Sie werden als zweistellige Hexadezimalzahlen angegeben. So ist der erste Wert, 0x0000ff, ein reines Blau (R=0, G=0, B=0x255), und der vierte Wert 0xffffff ist weiß.

(Die ZeilenumbrĂŒche im Postscript-File sind nicht nötig, ebensowenig der Kommentartext ('%' und Text danach). Achtung: im Datenfeld sind keine Kommentare erlaubt!)

FĂŒr Neugierige: Wozu ist der Rest im Postscript File gut? ZunĂ€chst muss man wissen, dass Postscript eine Programmiersprache ist, die mit einem Stapel arbeitet, auf den immer zuerst die Argumente, und dann die Funktion gelegt werden (also z.B. 1 2 add).

  • %!PS identifiziert das File als Postscript File
  • 2.835 dup scale skaliert das Bild so, dass eine Einheit = 1 Millimeter ist. Dazu wir 2.835 auf den Stack gelegt, der Wert dupliziert (jetzt liegen also 2 Zahlen auf dem Stack, man hĂ€tte anstelle 'dup' auch nochmal 2.835 schreiben können) und der Skalier-Befehl 'scale' ausgefĂŒhrt.
  • 5 30 translate verschiebt den Ursprung des Koordinatensystems (links unten!) ein bisschen zur Blattmitte (5mm in x, 30mm in y)
  • 200 200 scale macht eine Einheit nun 20cm lang. Da unser Bild spĂ€ter genau eine Einheit groß ist, ist das also einfach die GrĂ¶ĂŸe des Bildes. Sie kann auch in x- und y- unterschiedlich gewĂ€hlt werden.
  • /PicW 2 def definiert eine Variable 'PicW' fĂŒr die Bildbreite und weist ihr den Wert 2 zu
  • /PicH 2 def definiert entsprechend eine Variable fĂŒr die Bildhöhe
  • /picstr { 3 PicW mul string } bind def ist schon komplizierter. Hier wird zur Vereinfachung und Beschleuningung die Funktion 'picstr' definiert. Diese berechnet die Zahl der Werte pro Zeile als 3 * PicW, was in Postscript mit 3 PicW mul gemacht wird. Dieser Wert und der Belehl string wird beim Aufruf von 'picstr' auf den Stapel gelegt. Diese Funktion vereinfacht einfach nur die nĂ€chste Zeile...
  • PicW PicH 8 [PicW 0 0 PicH neg 0 PicH] {currentfile picstr readhexstring pop} false 3 colorimage fĂŒhrt schließlich den eigentlichen Befehl 'colorimage' aus. Die Parameter auf dem Stack sind: die Breite und Höhe (PicW und PicH), die Anzahl Bit pro Farbwert (8), eine Matrix, mit der das Bild gepiegelt und skaliert werden kann ([...]), eine Funktion, mit der die Farbwerte beschafft werden ({...}), ein Flag, das angibt, dass die RGB Werte nicht getrennt sind, sondern pro Pixel gemeinsam gegeben werden (false), und die Anzahl der FarbkanĂ€le pro Pixel (3). Die Funktion in Klammern gibt an, dass die Farbwerte aus dem aktuellen File gelesen werden (das beginnt nach 'colorimage') und als hex-Werte vorliegen. (Man kann die Farbwerte hier auch direkt mit <..> reinschreiben, bei zu großen Bildern lĂ€uft dann aber der Stack ĂŒber...)
  • 0000ff00ff00 etc. sind dann die Datenwerte. Es muss genau die richtige Anzahl vorliegen, sonst klappt es nicht!
  • showpage schließlich wirft die Seite aus. Dahinter kann man mit weiteren Kommandos weiter machen.

Ein schickes Programm

  • Erweitern Sie nun das erste Programm, indem Sie ein Postscript File öffnen, den obigen Header hineinschreiben (mit geeigneten NX und NY) und als Farbwerte zunĂ€chst z.B. 000000 und ffffff (also Schwarz und Weiss) ausgeben. Schließen Sie das File mit 'showpage' ab. Probieren Sie zunĂ€chst eine kleine Grafik aus und ĂŒberprĂŒfen Sie durch Anschauen im Editor oder mit more file.ps, dass alles richtig ist. Können Sie die Grafik mit 'ghostview' oder 'evince' anschauen? Wenn es nicht klappt: ÜberprĂŒfen Sie genau den Text im Postscript File und prĂŒfen Sie, dass die Anzahl Datenwerte genau stimmt! Die 'for' Schleifen fĂŒr NX udn NY sollten daher mit 'unsigned int' gemacht sein, nicht mit 'float'!
  • Bauen Sie nun Kommandozeilenparameter ein, mit denen Sie die BildgrĂ¶ĂŸe festlegen können.
  • Nun wollen wir endlich Farbe erzeugen. Legen Sie dazu z.B. eine Klasse ColorScale an, in der Sie die RGB Anteile z.B. als float abspeichern. Überladen Sie den '<<' stream Operator so, dass eine Variable vom Typ ColorScale als genau sechsstellige Hex-Zahl ausgegeben wird. Definieren Sie z.B. eine Methode set(int value, int max), die aus value eine geeignete Farbe macht, wobei value z.B. von 0 bis max laufen kann. (Man könnte auch set(float) verwenden.) Weisen Sie z.B. sehr hohen Werten die Farbe Blau zu, mittleren Werten GrĂŒn und niedrigen Werten Rot. Die ÜbergĂ€nge können Sie fließend machen.
  • Erweitern Sie die Kommandozeilenparameter so, dass Sie die Region in der komplexen Ebene festlegen können (z.B. Realteil und ImaginĂ€rteil der Mitte, und die GrĂ¶ĂŸe des Bildausschnittes).


Personal tools