Kochkurven

Koch-Applet

Algorithmus

Der ursprünglich Algorithmus zur Konstruktion einer Kochkurve basiert auf einem rekursiv-iterativen Prozess. Dies erschien mir für eine Berechnung im Computer etwas zu aufwändig. Stattdessen schwebte mir ein iteratives Verfahren vor, welches die n-te Iteration an einem Stück berechnet. Nach längeren Diskussionen kam dann von einem Freund die entscheidende Idee für einen solchen Algorithmus. Anschaulich kann man sich diesen Algorithmus als Ameise vorstellen, die die Kurve Stück für Stück abläuft. Die Rekursion der Originalvorschrift wird dabei durch eine Iteration über einem Stack ersetzt.

boolean bf[n][3];
bf[i][j] := false (i = 1..n, j = 1..3);
double len = len0 / (3^n);
zeichne startlinie;
while (!bf[i][j] für einige i, j) {
  finde min i0, j0 mit bf[i0][j0]==false;
  if (j0==0 OR j0==2) zeichne Links-Eck;
  else zeichne Rechts-Eck;
  setze bf[i0][j0] = true;
  bf[i][j]=false (i < i0, j = 0..2);
endwhile;

In diesem Fall wird der Stack durch das Array bf repräsentiert. Die drei Elemente einer Zeile von bf stehen für die Ecken einer Teilkurve. Die genauere Erklärung ergibt sich am besten über den Induktionsbeweis:

Induktionsanfang n=1: Hier wird ein Dreieck über einer Strecke errichtet. Dies entspricht dem ersten Iterationsschritt bei der Konstruktion der Kochkurve => OK

Induktionshypothese: Der Algorithmus gibt für die Eingabe n den n-ten Konstruktionsschritt der Kochkurve aus.

Induktionsschritt n->n+1: Das Array bf wird am oberen Ende um eine Zeile erweitert. Mit den darunter liegenden Zeilen wird der Konstruktionsschritt n erstellt. Die neue Zeile verknüpft nun vier solcher Schritte zu einer neuen Kurve. Dies ist der n+1-te Konstruktionsschritt.

Implementierung

Den vorgestellten Algorithmus habe ich als Java-Applet implementiert (siehe oben). Als Breite der Kurve habe ich 729 (=3⁶) Pixel gewählt, um mögliche Rundungsfehler zu minimieren. Gleichzeitig ergab sich so die Beschränkung der Iterationstiefe auf maximal n=6. Für diesen Wert wird jede Linie gerade noch durch einen Pixel dargestellt.

Zusätzlich zur Konstruktion der Iterationsschritte verfügt das Applet auch über die Möglichkeit, eine "Koch-Küstenlinie" zu konstruieren. Dies erfolgt mit der Option Coastline. Dabei werden manche Dreiecke bei der Konstruktion in die entgegengesetzte Richtung gezeichnet, die Entscheidung erfolgt per Zufallsgenerator.

Download: koch-curve-src.tar.bz2 (16 kB)

Dank

Besonderer Dank gebührt Stefan Schenk für die Idee zu dem Algorithmus und für viele nicht nur wissenschaftliche Diskussionen.

Diese Datei: http://www.informatik.uni-augsburg.de/~klugeflo/koch-applet.html Letzte Änderung: 17.11.2008 FAK