Sierpiński-Dreieck

Sierpiński-Dreieck

Zielgruppe sind StudentInnen und ambitionierte Informatik-Amateure

Grundkenntnisse der Geometrie werden vorausgesetzt, solche der Informatik und der Tabellen-Kalkulation sind hilfreich.


Live Sierpiński-Dreieck



Algorithmus des Sierpiński-Dreiecks


Der Algorithmus des Sierpiński-Dreiecks in der Formulierung der Geometrie:
Zeichne ein gleichseitiges Dreieck
Verbinde die Mittelpunkte der Seiten durch gerade Linien. Dabei entstehen 4 kleinere, ebenfalls gleichseitige Dreiecke.
Das mittlere Teil-Dreieck bleibt unverändert, jedes der 3 anderen Teil-Dreiecke wird selbst zum Ausgangspunkt ① der nächsten Generation von (noch kleineren) Teil-Dreiecken.

Diesen Algorithmus kann man mit Papier und Bleistift auch ohne besondere Fachkenntnisse leicht ausprobieren. Dabei erkennt man anschaulich:
Man könnte den Algorithmus unendlich oft fortsetzen, wenn man die immer kleiner werdenden Dreiecke noch zeichnen könnte.
Man könnte das Dreieck ausschneiden, kopieren und daraus neue, immer größer werdende Sierpiński-Dreiecke herstellen. Auch in diese Richtung könnte man den Algorithmus unendlich oft fortsetzen.



Translation bedeutet Verschiebung des Koordinaten-Systems (in eine vorgegebene Richtung um einen vorgegebenen Betrag).  Beim Sierpiński-Dreieck erfolgt eine Translation um den halben Umkreis-Radius in 3 verschiedene Richtungen.

Rotation bedeutet Drehung des Koordinaten-Systems (um einen vorgegebenen Winkel).  Beim Sierpiński-Dreieck wird keine Rotation angewendet, das macht das Beispiel zum Einstieg besonders einfach.

Skalierung bedeutet eine Änderung des Maßstabs, normalerweise eine Verkleinerung jeder nachfolgenden Generation.  Beim Sierpiński-Dreieck beträgt die Skalierung von einer Generation zur nächsten jeweils 1/2 aller Längen-Werte.



Erfahrene EntwicklerInnen analysieren den Algorithmus vor Beginn der 'eigentlichen' Programmierung und formulieren die anzuwendenden Formeln abstrakt und allgemein. Das kostet viel Zeit und meist einige Vor-Versuche. Dabei muss man u.a. diese Teil-Aufgaben lösen:

Welche spezielle Vorgaben (konkrete Zahlen-Werte) sind (nur) für die 1.Generation nötig? Die Anzahl der Vorgaben sollte so klein wie möglich sein und darf keine redundanten Werte enthalten.

Der Algorithmus ist so zu formulieren, dass nur die Zahlenwerte der Vorgaben oder Konstanten verwendet werden.

Am Ende der Berechnung einer Generation muss das transformierte Koordinaten-System der folgenden Generation berechnet werden.



In allen Beispielen dieser Seite wird zur Festlegung der Position der Mittelpunkt des Dreiecks verwendet. Das individuelle Koordinaten-System wird in den Mittelpunkt verlegt. Dieser hat daher die XY-Koordinaten M1(0,0)
Das wird in den Beispiele dieser Seite so formuliert:
mx[1] = 0
my[1] = 0
Der Index [1] bezeichnet die 1.Generation.

Es wäre ein Fehler, mehr als 1 Referenz-Punkt festzulegen (z.B. alle 3 Eckpunkte).

Alternativ könnte man auch andere Referenz-Punkte verwenden, z.B. jeden der Eckpunkte. Weiters könnte man an Stelle der cartesischen XY-Koordinaten auch Polar-Koordinaten verwenden. Damit ließe sich der Algorithmus einfacher beschreiben. Allerdings verwenden alle gängigen Zeichen-Programme XY-Koordinaten, daher müsste man die Ergebnisse zum Zeichnen umrechnen.



Vorgaben der folgenden Generation

r[n+1]r[n]/2
Punktxy
MAmx - r*sqrt(3)/4my - r/4
MBmx + r*sqrt(3)/4my - r/4
MCmxmy + r/2
Der neue Radius r[n+1] ist für alle Elemente der nächsten Generation gleich. Die Lage der Mittelpunkte unterscheidet sich: Mit MA wird der Mittelpunkt des neben dem Eckpunkt A angeordneten Teil-Dreiecks bezeichnet, usw.
Zur Berechnung der nächsten Generation werden die aktuellen Vorgaben (r, mx, my) durch die neuen ersetzt.

Die hier verwendeten Formeln sind in dieser Form kaum zu finden. Man muss sie daher selbst ableiten. Das kann (bei jeder ähnlichen Aufgabe, insbesondere bei jedem Fraktal) relativ viel Zeit in Anspruch nehmen.

In der IT-Grafik liegt der Ursprung des Koordinaten-Systems ohne weitere Maßnahmen immer in der linken oberen Ecke. Die Y‑Koordinate wird von oben nach unten gemessen, nicht wie sonst allgemein von unten nach oben. Daher muss man entweder bereits in IT-Koordinaten rechnen (und alle hier angegebenen Formeln entsprechend ändern) oder die Vorzeichen aller berechneten Y‑Koordinaten zum Zeichnen umkehren.
Ausnahme: In der ↓ Tabellen-Kalkulation wird die Y‑Koordinaste so wie in der Mathematik üblich gemessen.

Sierpiński-Dreieck mit Tabellen-Kalkulation


Hier wird die Programmierung von 2 Generationen des Sierpiński-Dreiecks vorgestellt.

Wenn sie wenig Erfahrung haben, dann können sie die hier angegebenen Formeln zur Programmierung verwenden.
Als Beispiele können das Live-Beispiel dieser Seite oder die zum ↗ Download angebotene fertige Lösung dienen.

Wenn sie fortgeschrittene Kenntnisse haben, dann sollten sie versuchen, die Aufgabe ohne Anleitung zu lösen.



Nach Festlegung eines Namens kann man in jeder weiteren Formel an Stelle der Adresse B2 den Namen r_1 verwenden.
In den Beispielen dieses Kapitels sind die verwendeten Namen unter den jeweiligen Werten und Formeln in blauer Farbe eingetragen.

In den Formeln des Beispiels werden keine Adressen verwendet sondern ausschließlich Namen. Damit nähert man sich einer allgemeinen Formulierung:
Man kann die hier gezeigten Sub-Tabellen kopieren und zur Berechnung der 3.Generation einsetzen: In diesem Fall muss man lediglich die Namen in den Formeln entsprechend ändern, z.B. des Umkreis-Radius von r_2 auf r_3 usw.


 ABC
1Vorgaben  
2r[1]
10
r_1
 
3M[1]xy
4 
0
M1_x
0
M1_y


 ABC
7S[1]xy
8A=M1_x-r_1*WURZEL(3)/2=M1_y-r_1/2
9B=M1_x+r_1*WURZEL(3)/2=M1_y-r_1/2
10C=M1_x=M1_y+r_1
11D[1]=M1_x+r_1*WURZEL(3)/4=M1_y+r_1/4
12E[1]=M1_x-r_1*WURZEL(3)/4=M1_y+r_1/4
13F[1]=M1_x=M1_y-r_1/2


 ABC
16 xy
17M[2][A]=M1_x-r_1*WURZEL(3)/4
M2A_x
=M1_y-r_1/4
M2A_y
18M[2][B] =M1_x+r_1*WURZEL(3)/4
M2B_x
=M1_y-r_1/4
M2B_y
19M[2][C] =M1_x
M2C_x
=M1_y+r_1/2
M2C_y
20r[2]=r_1/2
r_2


 ABC
23S[2][A]xy
24D[2][A] =M2A_x + r_2*WURZEL(3)/4 =M2A_y + r_2/4
25E[2][A] =M2A_x - r_2*WURZEL(3)/4 =M2A_y + r_2/4
26F[2][A]=M2A_x =M2A_y - r_2/2


 ABC
29S[2][B]xy
30D[2][B] =M2B_x + r_2*WURZEL(3)/4 =M2B_y + r_2/4
31E[2][B] =M2B_x - r_2*WURZEL(3)/4 =M2B_y + r_2/4
32F[2][B]=M2B_x =M2B_y - r_2/2


 ABC
35S[2][C]xy
36D[2][C] =M2C_x + r_2*WURZEL(3)/4 =M2C_y + r_2/4
37E[2][C] =M2C_x - r_2*WURZEL(3)/4 =M2C_y + r_2/4
38F[2][C]=M2C_x =M2C_y - r_2/2


So fügt man weitere Diagramm-Linien zu einem bereits sichtbaren Diagramm hinzu:

Zuletzt werden die Diagramm-Linien formatiert. yyy



Erzeugen sie eine neue Hilfs-Tabelle ähnlich dem hier gezeigten Beispiel als 'Übergang zur 3.Generation A'. (3 solcher Tabellen sind möglich). Geben sie den Zellen sprechende Namen neue 'sprechende Namen'.

Erzeugen sie Kopien der Hilfs-Tabellen für die Dreiecke der 3.Generation. In den Formeln braucht man nur in allen Namen die Ziffer 2 der 2. Generation durch die Ziffer 3 der 3.Generation zu ersetzen.

Sierpiński-Dreieck mit Objekt-Grafik


Die ↑ animierte Grafik dieser Seite wurde mit einer Kombination aus mehreren Web-Technologien erstellt:
  • Die Grundlage ist eine Webseite in dem aktuellen Version HTML-5.
  • Die Objekt-Grafik ist mit SVG programmiert und in die Webseite eingebettet.
  • Alle Elemente sind mit CSS formatiert.
  • Die Animation ist mit Javascript programmiert.
Die Anweisungen ('Programme') aller Komponenten sind im ↗ Quelltext enthalten. Ihr Browser hat aus den Programmen das animierte Bild des Sierpiński-Dreiecks erzeugt.



<defs>
<path id="s" d="M86.6,-50 L-86.6,-50 L0,100 Z"/>
</defs>
Mit dem d-Attribut wird der zu zeichnende Pfad programmiert.
M (MoveTo) bewegt zu den angegebenen X- und Y-Koordinaten.
L (LineTo) zeichnet eine Linie zum angegebenen Endpunkt
Z zeichnet eine Linie zum Anfangspunkt.
Die Zahlenwerte der Koordinaten ergeben sich aus dem ↑ Algorithmus, wenn man als Umkreis-Radius r=100 (Bildpunkte, Pixel) einsetzt.



<path d="M-173.2,100 L173.2,100 L0,-200 Z"/>
<use id="s0" xlink:href="#s"/>
Die Zahlenwerte der Koordinaten ergeben sich aus dem ↑ Algorithmus, wenn man als Umkreis-Radius r=100 (Bildpunkte, Pixel) einsetzt.



<path d="M-173.2,100 L173.2,100 L0,-200 Z"/>
<use id="s0" xlink:href="#s"/>
<g transform="translate(-86.6,50) scale(0.5)">
<use id="sa" xlink:href="#s"/>
</g>
<g transform="translate(86.6,50) scale(0.5)">
<use id="sb" xlink:href="#s"/>
</g>
<g transform="translate(0,-100) scale(0.5)">
<use id="sc" xlink:href="#s"/>
</g>



<path d="M-173.2,100 L173.2,100 L0,-200 Z"/>
<use id="s0" xlink:href="#s"/>

<g transform="translate(-86.6,50) scale(0.5)">
<use id="sa" xlink:href="#s"/>
<g transform="translate(-86.6,50) scale(0.5)">
<use id="saa" xlink:href="#s"/>
</g>
<g transform="translate(86.60254,50) scale(0.5)">
<use id="sab" xlink:href="#s"/>
</g>
<g transform="translate(0,-100) scale(0.5)">
<use id="sac" xlink:href="#s"/>
</g>
</g>

<g transform="translate(86.6,50) scale(0.5)">
<use id="sb" xlink:href="#s"/>
<!-- ... -->
</g>

<g transform="translate(0,-100) scale(0.5)">
<use id="sc" xlink:href="#s"/>
<!-- ... -->
</g>

Animation mit Javascript


Alle verwendeten Javascript-Programme sind im ↗ Quelltext enthalten. Sie werden verwendet, um Teile der Grafik schrittweise sichtbar und wieder unsichtbar zu machen.
Das Verständnis der Details erfordert fortgeschrittene Kenntnisse.