Rekursion: wie sieht hierfür der Quelltext aus?
Für das Dreieck
4 Antworten
Das Stichwort "Sierpinski-Dreieck" wurde schon zur Genüge erwähnt.
Der entscheidende Punkt ist die "Selbstähnlichkeit" der Figur - in diesem Fall:
Das komplette Dreieck besteht aus drei Teildreiecken im Maßstab 1:2, die jeweils eine Ecke mit dem Originaldreieck gemeinsam haben und deren übrige Ecken Seitenmitten des ursprünglichen Dreiecks sind.
Selbstähnlichkeit ist immer ein Hinweis darauf, dass sich das Problem auf Rekursion zurückführen lässt. (Natürlich kann man in der Praxis niemals unendlich viele Rekursionsschritte durchführen - das geht nur in der Mathematik.) Als Rekursionsvorschrift benötigt man / bietet sich an die Abbildungsvorschrift der Selbstähnlichkeit.
In diesem Fall ist es egal, ob man die Teildreiecke dreht oder nicht. (Z. B. bei der Hilbert-Kurve ist die Drehung / Spiegelung der Teilquadrate aber entscheidend; hier kommt man um eine Abbildungsmatrix nicht herum, oder ein Äquivalent einer Abbildungsmatrix.)
Bei geometrischer Selbstähnlichkeit/Selbstaffinität wie beim Sierpinski-Dreieck ist es m. E. am einfachsten, mit den Ortsvektoren der Punkte zu arbeiten und Größe, Orientierung, Seitenverhältnisse etc. der Ausgangsfigur ganz am Anfang zu behandeln. (Z. B. das Verhältnis von Höhe zu Basis des Dreiecks wird ganz zu Anfang ein einziges Mal ausgerechnet.)
Das Dreieck D0 wird in die Teildreiecke D1, D2 und D3 aufgeteilt.
Das Dreieck D0 besteht aus den Punkten A0, B0 und C0, das Dreieck D1 aus A1, B1 und C1 etc.
Dann erhalten wir (z. B. bzw. am einfachsten):
A1 = A0, B1 = 1/2 (A0 + B0), C1 = 1/2 (A0 + C0)
A2 = 1/2 (A0 + B0), B2 = B0, C2 = 1/2 (B0 + C0)
A3 = 1/2 (A0 + C0), B3 = 1/2 (B0 + C0), C3 = C0
Auf diese 3 Teildreiecke wendet man die Ursprungsfunktion an, bis die vorgegebene maximale Rekursionstiefe erreicht ist. Dann zeichnet man das übergebene Dreieck, anstatt noch weiter zu rekurrieren. Aber das sollte ja klar sein, wenn man das Thema "Rekursion" schon mal behandelt hatte.
Das Sierpinski-Dreieck kannst du z.B. rekursiv implementieren:
using System.Windows.Forms;
public class MainForm : System.Windows.Forms.Form
{
private Graphics graphics;
public MainForm()
{
InitializeComponent();
Text = "Sierpinski-Dreieck";
Width = 800;
Height = 600;
graphics = CreateGraphics(); // Erzeugt ein Grafikobjekt für das Zeichnen auf dem Hauptfenster.
Paint += OnPaint; // Verknüpft die Ereignisbehandlungsmethode mit dem Paint Ereignis des Hauptfensters.
}
private void OnPaint(object sender, PaintEventArgs e)
{
ZeichneSierpinskiDreieck(200, 400, 600, 400, Color.FromArgb(0, 0, 0), 0, 4); // Aufruf der Methode mit maximaler Rekursionstiefe 4
}
// Diese Methode wird aufgerufen, wenn das Hauptfenster gezeichnet wird. Sie enthält 3 rekursive Aufrufe.
private void ZeichneSierpinskiDreieck(float x1, float y1, float x2, float y2, Color farbe, int tiefe, int maximaleTiefe)
{
float faktor = (float) Math.Sqrt(3) / 2; // Skalierungsfaktor für die Höhe der gleichseitigen Dreiecke
if (tiefe == maximaleTiefe) // Wenn maximale Rekursionstiefe erreicht, dann Koordinaten setzen und gleichseitiges Dreieck ausfüllen
{
PointF[] dreieck = new PointF[]{new PointF(x1, y1), new PointF(x2, y2), new PointF((float) ((x1 + x2) / 2 + faktor * (y2 - y1)), (float) ((y1 + y2) / 2 + faktor * (x1 - x2)))};
graphics.FillPolygon(new SolidBrush(farbe), dreieck); // Füllt das gleichseitige Dreieck mit den gesetzten Koordinaten der als Parameter angegebenen Farbe aus.
}
else // sonst Methode für jeden der 3 Teilbereiche rekursiv aufrufen
{
// Definiert Farben mit RGB-Werten.
Color rot = Color.FromArgb(255, 0, 0), grün = Color.FromArgb(0, 255, 0), blau = Color.FromArgb(0, 0, 255);
// Rekursive Aufrufe der Methode für das Zerlegen des aktuellen Dreiecks in 3 Teilbereiche mit halber Breite und Höhe.
ZeichneSierpinskiDreieck(x1, y1, (x1 + x2) / 2, (y1 + y2) / 2, rot, tiefe + 1, maximaleTiefe);
ZeichneSierpinskiDreieck((x1 + x2) / 2, (y1 + y2) / 2, x2, y2, grün, tiefe + 1, maximaleTiefe);
ZeichneSierpinskiDreieck((float) ((3 * x1 + x2) / 4 + faktor * (y2 - y1) / 2), (float) ((3 * y1 + y2) / 4 + faktor * (x1 - x2) / 2), (float) ((x1 + 3 * x2) / 4 + faktor * (y2 - y1) / 2), (float) ((y1 + 3 * y2) / 4 + faktor * (x1 - x2) / 2), blau, tiefe + 1, maximaleTiefe);
}
}
}
aber auch Iterativ (das was man eher in der Mathematik macht):
private void BerechneKoordinaten(ref List<float> x1Werte, ref List<float> y1Werte, ref List<float> x2Werte, ref List<float> y2Werte, ref List<Color> farben)
{
double faktor = Math.Sqrt(3) / 2; // Skalierungsfaktor für die Höhe der gleichseitigen Dreiecke
List<float> neueX1Werte = new List<float>(), neueY1Werte = new List<float>(), neueX2Werte = new List<float>(), neueY2Werte = new List<float>();
List<Color> neueFarben = new List<Color>();
int anzahlDerTeilDreiecke = farben.Count;
for (int i = 0; i < anzahlDerTeilDreiecke; i++)
{
float x1 = x1Werte[i], y1 = y1Werte[i], x2 = x2Werte[i], y2Werte[i];
neueX1Werte.Add(x1);
neueY1Werte.Add(y1);
neueX2Werte.Add((x1 + x2) / 2);
neueY2Werte.Add((y1 + y2) / 2);
neueX1Werte.Add((x1 + x2) / 2);
neueY1Werte.Add((y1 + y2) / 2);
neueX2Werte.Add(x2);
neueY2Werte.Add(y2);
neueX1Werte.Add((float) ((3 * x1 + x2) / 4 + faktor * (y2 - y1) / 2));
neueY1Werte.Add((float) ((3 * y1 + y2) / 4 + faktor * (x1 - x2) / 2));
neueX2Werte.Add((float) ((x1 + 3 * x2) / 4 + faktor * (y2 - y1) / 2));
neueY2Werte.Add((float) ((y1 + 3 * y2) / 4 + faktor * (x1 - x2) / 2));
}
x1Werte = neueX1Werte;
y1Werte = neueY1Werte;
x2Werte = neueX2Werte;
y2Werte = neueY2Werte;
}
private void ZeichneDreieck(float x1, float y1, float x2, float y2, Color farbe)
{
double faktor = Math.Sqrt(3) / 2; // Skalierungsfaktor für die Höhe der gleichseitigen Dreiecke
PointF[] dreieck = new PointF[]{new PointF(x1, y1), new PointF(x2, y2), new PointF((float) ((x1 + x2) / 2 + faktor * (y2 - y1)), (float) ((y1 + y2) / 2 + faktor * (x1 - x2)))};
graphics.FillPolygon(new SolidBrush(farbe), dreieck); // Füllt das gleichseitige Dreieck mit der als Parameter angegebenen Farbe aus.
}
Wenn man sich schon die Mühe einer iterativen Umsetzung machen möchte, dann vielleicht gleich ein L-System, da kann man viel mehr Spaß mit haben udn experimentieren ;-).
Ich habe ihn nicht ausprobiert.
Ich hatte es einfach nur von Wikipedia (die Seite die ich verlinkt habe ganz oben) kopiert.
Die Methode ist dann wohl gelungen.
Das ist ein Sierpinski-Dreieck, dafür wird man zahlreiche Code-Beispiele finden.
https://forourutopia.wordpress.com/2011/06/26/sierpinski-dreieck-in-java-per-rekursion/
Eine Umsetzung geht sogar ganz ohne Iteration oder Schleife.
Die Approximation eines Sirpinski-Dreiecks (ein exaktes Sierpinski-Dreieck würdest du nicht sehen, da alle 2D-Kanten unendlich schmal wären) erhälst du die Eigenschaft seiner Baryzentrischen Koordinaten nutzt:
https://en.wikipedia.org/wiki/Sierpi%C5%84ski_triangle#Properties
Dann brauchst du quasi nur die Koordinaten und kannst in O(1) ausrechnen, ob die Stelle gefüllt ist oder nicht.
Vermutlich wird in der Aufgabenstellung ausdrücklich Rekursion gefordert. (Rekursion dürfte das Thema der aktuellen Unterrichtseinheit sein.)
Hast du den Code ausprobiert? Da ist ein Syntaxfehler in der Zeile
(vermutlich sollte es heißen
) (Kleinere Fehler sind übrigens eine verbreitete Methode, 1:1-Kopien identifizieren zu können)