Sierpinski-Dreieck
| Sierpinski-Dreieck |
| Sierpinski-Dreieck in der Ebene |
Ein Sierpinski-Dreieck (nach Wacław Sierpiński) ist ein Fraktal, das durch fortgesetzte rekursive Aufteilung eines Vorgängerdreiecks n-1 in vier weitere (zueinander kongruente) Dreiecke erhalten wird, die dem Ausgangsdreieck ähnlich im mathematischen Sinne sind. Geht n gegen unendlich, spricht man von einer Sierpinski-Fläche. Die fraktale Dimension der Sierpinski-Fläche beträgt D=log(3)/log(2)=1,58..., also zwischen Gerade (D=1) und Fläche (D=2).
Konstruktion
Am häufigsten wird zur Veranschaulichung ein gleichseitiges Dreieck gezeigt. Das ist aber nicht zwingend; es kann jedes beliebige Dreieck in ein Sierpinski-Dreieck zerlegt werden.
Der "klassische" Algorithmus, der zur grafischen Demonstration des Fraktalbegriffs verwendet wird, ist folgender:
- Zeichne ein Dreieck ("Initiator")
- Verbinde die Mittelpunkte der Seiten ("Generator")
- Verbinde die Mittelpunkte der Seiten an jedem der drei kleinen Dreiecke, die an den Ecken entstanden sind
- Gehe zu 3.
Dieser Algorithmus verdeutlicht den Zusammenhang. Es entstehen bei jedem Iterationsschritt an den Ecken 3 (zum Initator ähnliche) Dreiecke mit halber Seitenlänge und einem Viertel der Fläche die korrekterweise gefärbt werden müssten. Denn das vierte, das "innere" kleine Dreieck, welches dabei entsteht, muss man sich als aus der Dreiecksfläche des vorhergehenden Schritts "herausgeschnitten" vorstellen.
Das eigentliche Sierpinski-Dreieck im streng mathematischen Sinn ist das Grenzobjekt, das nach unendlich vielen Iterationsschritten übrigbleibt. Es besteht aus unendlich vielen "Eckpunkten". Zur Darstellung, die meist mit Computerprogrammen realisiert und nach Bedarf ausgedruckt wird, reicht aber meist schon eine Iterationstiefe von maximal 10. Bedingt durch die Auflösung des darstellenden Mediums (Monitor, Drucker etc...) und des menschlichen Auges sind diese Gebilde vom Grenzobjekt nicht mehr zu unterscheiden.
Mathematische Zusammenhänge
Als klassisches Fraktal, insbesondere mit einem gleichseitigen Dreieck als Initiator, ist das Sierpinski-Dreieck ein Musterbeispiel für exakte Selbstähnlichkeit: Die in jedem Schritt erzeugten Teildreiecke sind verkleinerte exakte Kopien des Ausgangsdreiecks. Jede Skalierung eines beliebigen Teils des Grenzobjekts erscheint wie das Gesamtobjekt selbst. Es ist somit skaleninvariant.
Von den zugrundeliegenden mathematischen Gesetzmäßigkeiten her ist das Sierpinski-Dreieck eng verwandt mit der Cantor-Menge. Es hat die reziproke fraktale Dimension derselben, nämlich log(3)/log(2) = 1,585. Dies resultiert daraus, dass bei jedem Schritt k genau 3^k neue Teildreiecke mit der Seitenlänge (1/2)^k erzeugt werden. Das Grenzobjekt entsteht, wenn k unendlich ist und es kann daher als "geometrisches Äquivalent" zu einem Grenzwert (Limes) aufgefasste werden. Aus der Bildungsvorschrift lässt sich auch berechnen, welche Punkte der ursprünglichen Fläche zum Grenzobjekt gehören.
Darstellung mittels Hutchinson-Operator
Ein Sierpinski-Dreieck lässt sich auch als Attraktor eines dynamischen Rückkopplungsprozesses, eines so genannten deterministisch iterierten Funktionensystems mit geeigneten Parametern aus nahezu jeder beliebigen geometrischen Figur darstellen. Dabei werden wiederholt Mehrfach-Transformationen des Ausgangsobjekt vorgenommen, diese Bilder mit einer Abbildungsvorschrift, dem Hutchinson-Operator, entsprechend angeordnet und diese Prozedur erneut auf das entstandene Gesamtbild angewandt usw. Mit zunehmender Iterationstiefe streben die entstehenden Bilder, falls geeignete Parameter gewählt wurden, einem Sierpinski-Dreieck zu, das in diesem Falle der Attraktor des Funktionensystems ist.
Sierpinski-Schwamm
Eine Darstellung des Sierpinksi-Dreiecks ist, analog zum Menger-Schwamm, auch in der dritten Dimension möglich: Der Initiator ist ein Tetraeder. Aus diesem wird als Iterationsschritt aus der Mitte ein Oktaeder mit halber Kantenlänge herausgeschnitten. Übrig bleiben vier Tetraeder, aus denen wieder je ein Oktaeder herausgeschnitten wird, usw. Die Dimension für dieses Gebilde ist D=log(4)/log(2)=2, obwohl es sich hierbei um eine Figur im dreidimensionalen Raum handelt. Mit einer zunehmenden Zahl von Iterationsschritten geht das Volumen der Figur gegen 0; die Oberfläche bleibt jedoch konstant.
|
|
|
|
|
|
|
| |
| Stufe | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
Chaos-Spiel
Abgesehen von der rekursiven Darstellung gibt es noch einen Zufallspunkt-Algorithmus zur näherungsweisen Konstruktion des Sierpinski-Dreiecks: Das Chaos-Spiel.
Dabei wird ein gleichseitiges Dreieck mit den Ecken A, B, C aufgezeichnet und ein zufälliger Punkt im Inneren des Dreiecks gewählt (er kann aber auch außerhalb liegen, ohne das Ergebnis wesentlich zu verändern). Nun wird pro Schritt eine Ecke zufällig ausgewählt (die Wahrscheinlichkeit für die Ecken sind gleich) und der Punkt gedanklich mit der gezogenen Ecke verbunden. Die Mitte dieser Strecke markiert nun den Punkt für die nächste Runde. Wiederholt man dies sehr oft, bilden die Punkte eine Näherung des Sierpinksi-Dreiecks. Wenn man die Punkte auch noch je nach ausgewählter Ecke unterschiedlich einfärbt, also z.B. A = grün, B = rot und C = blau, dann bekommt man drei unterschiedlich gefärbte Sierpinski-Dreiecke im Sierpinski-Dreieck.
Zusammenhang mit dem Pascalschen Dreieck
Mit dem Sierpinski-Dreieck verwandt ist auch das Pascalsche Dreieck. Um das zu verdeutlichen, stelle man sich die ungeraden Zahlen als schwarz markiert vor und die geraden als farblos. Die ungeraden Zahlen des Pascal-Dreiecks werden der Einfachheit halber als Doppelkreuze angegeben (und die geraden Zahlen weggelassen):
.
.
.
# # # # # # # . . . . . . . . . .
#
# #
# #
# # # #
# #
# # # #
# # # #
# # # # # # # #
Null-Meer # #
# # # #
# # # # # . . . . . .
# # # # # # # # #
# # # # #
# # # # # # # # #
# # # # # # # # #
# # # # # # # # # # # # # # # #. . . . . . . . .
1
1 1
# #
1 3 3 1
# #
# # # #
# # # # Null-See
# # # # # # # #
# #
# # # #
# # # #
# # # # # # # #
# # # #
# # # # # # # #
# # # # # # # #
# # # # # # # # # # # # # # # #
# #
# # # #
. .
. .
. .
Aber egal, wie weit man das Gebilde erweitert, es wird nie ein Sierpinski-Dreieck daraus. Wenn man wissen will, wo sich das Pascal-Dreieck ungefähr im Sierpinski-Dreieck lokalisieren lassen könnte: es ist ein gedachter mathematischer Punkt auf der Mitte der Strecke der rechten, oder wahlweise linken Seite des (initialen) Dreiecks. Das bedeutet, wenn man von 1 aus in irgend eine Richtung laufen würde, käme man nie an irgend einen Eckpunkt. Ebenso wenig könnte ein Beobachter, der das ganze Sierpinski-Dreieck von oben betrachten würde, je das Sierpinski-Dreieck so vergrößern, dass er den Läufer jemals sehen würde.
Code
Java-Programm
Eine Mögliche Realisierung des Problems mit Java - Java-Applet zur Demonstration des Dreiecks. Das Dreieck kann in der Ebene verschoben und seine Größe kann verändert werden. Parameter der rekursiven go-Methode: b: Kantenlänge, hpX und hpY: Koordinaten des Höhenfußpunktes, lh: Höhe, lvl: Rekursionstiefe.
public void triang(Graphics g, int x0, int y0, int x1, int y1, int x2, int y2){
g.drawLine(x0, y0, x1, y1);
g.drawLine(x1, y1, x2, y2);
g.drawLine(x2, y2, x0, y0);
}
public void go(Graphics g,int b, int hpX, int hpY, int lh, int lvl){
int x0,x1,x2,y0,y1,y2;
if (lvl<=0) return;
x0=hpX-(b/2); y0=hpY-(lh/2);
x1=hpX+(b/2); y1=hpY-(lh/2);
x2=hpX; y2=hpY;
triang(g, x0, y0, x1, y1, x2, y2);
go(g,(b/2), hpX, hpY-(lh/2), lh/2, lvl-1);
go(g,(b/2), hpX+(b/2), hpY, lh/2, lvl-1);
go(g,(b/2), hpX-(b/2), hpY, lh/2, lvl-1);
}
public void paint(Graphics g){
setBackground(Color.white);
triang(g, ihpX-ib, ihpY, ihpX+ib, ihpY, ihpX, ihpY-ilh);
go(g, ib, ihpX, ihpY, ilh, ilvl);
}
Pascal-Programm
Beispiel-Code in Object Pascal (Delphi) zur grafischen Darstellung eines Sierpinski-Dreiecks:
procedure Sierpinski(Canvas: TCanvas; x1, y1, x2, y2, x3, y3: Extended; t: Integer);
begin
if t > 0 then
begin
Canvas.MoveTo(Round(x1), Round(y1));
Canvas.LineTo(Round(x2), Round(y2));
Canvas.LineTo(Round(x3), Round(y3));
Canvas.LineTo(Round(x1), Round(y1));
Sierpinski(Canvas, x1, y1, x1 + (x3 - x1) / 4, ((y1 - y2) / 2) + y2, x2, y1, t - 1);
Sierpinski(Canvas, x1 + (x3 - x1) / 4, ((y1 - y2) / 2) + y2, x2, y2, x1 + (x3 - x1) / 4 * 3,
((y1 - y2) / 2) + y2, t - 1);
Sierpinski(Canvas, x2, y1, x1 + (x3 - x1) / 4 * 3, ((y1 - y2) / 2) + y2, x3, y3, t - 1);
end;
end;
var
Image1: TImage; // muss initialisiert werden
--- Beispielaufruf
Sierpinski(Image1.Canvas, 20, 350, 220, 50, 420, 350, 6);
Logo-Programm
to sierpinski :stufe :laenge make "stufe :stufe - 1 make "laenge :laenge / 2 if :stufe > 0 [repeat 3 [sierpinski :stufe :laenge fd :laenge * 2 rt 120]] if :stufe = 0 [repeat 3 [repeat 3 [fd :laenge rt 120] fd :laenge * 2 rt 120]] end
Beispielaufruf: sierpinski 6 300
Logo-Programm mit „Pfeilspitzen“-Fraktal
Das Pfeilspitzen-Fraktal bietet eine sehr gute Näherung für ein Sierpinski-Dreieck:
|
Dieses Pfeilspitzen-Fraktal hat die Stufe 6, damit man die |
Das zu dem Pfeilspitzen-Fraktal dazu gehörige LOGO-Programm sieht so aus:
to pfeilspitze :stufe :laenge rpfeil :stufe :laenge end to rpfeil :stufe :laenge make "stufe :stufe - 1 make "laenge :laenge / 2 if :stufe > 0 [rt 60 lpfeil :stufe :laenge lt 60 rpfeil :stufe :laenge lt 60 lpfeil :stufe :laenge rt 60] if :stufe = 0 [rt 60 fd :laenge lt 60 fd :laenge lt 60 fd :laenge rt 60] end to lpfeil :stufe :laenge make "stufe :stufe - 1 make "laenge :laenge / 2 if :stufe > 0 [lt 60 rpfeil :stufe :laenge rt 60 lpfeil :stufe :laenge rt 60 rpfeil :stufe :laenge lt 60] if :stufe = 0 [lt 60 fd :laenge rt 60 fd :laenge rt 60 fd :laenge lt 60] end
Beispielaufruf: pfeilspitze 12 300
TI(r)-Taschenrechner Programm
Aus dem Handbuch zum TI-84 Plus Silver Edition (leichte Änderungen meinerseits) Der TR muss auf Englisch gestellt sein, sonst haben die Kommandos andere Namen.
PROGRAM:SIERPINS
:Disp "SAVE PIC?" findet man in PRGM, (>)
:Disp "0:No"
:Disp "1:Yes"
:Input J findet man in PRGM, (>)
:If J=1 findet man in PRGM
:Input "Location:",T
:FnOff :ClrDraw findet man in CATALOG
:PlotsOff findet man in CATALOG
:AxesOff findet man in CATALOG
:0->Xmin:1->Xmax findet man in VARS\Window..., -> STO>
:0->Ymin:1->Ymax findet man in VARS\Window...
:rand->X:rand->Y MATH, 3x (>)
:For(K,1,3000) PRGM
:rand->N
:If N<=1/3 2nd, MATH (Test), 6
:Then PRGM
:.5X->X
:.5Y->Y
:End PRGM
:If 1/3<N and N<=2/3 2nd, MATH,(>)
:Then
:.5(.5+X)->X
:.5(1+Y)->Y
:End
:If 2/3<N
:Then
:.5(1+X)->
:.5Y->
:End
:Pt-On(X,Y) CATALOG
:End
:If F=1
:StoreGDB T 2nd, PRGM (Draw),3x (>) - wenn man genug
RAM hat kann man auch StorePic nehmen
:Stop PRGM
Siehe auch: Sierpiński-Kurve
Weblinks
- http://www.seefsen.de/sierp.html Java-Applet zur Demonstration des Dreiecks
- http://www.jgiesen.de/ChaosSpiel/Chaos.html - Erklärung und Java-Applet zum Chaos-Spiel
- http://www.beisenkamp.schulnetz.hamm.de/Logo/sierp.htm - Logo-Code für das Dreieck
