C_Kurs_5Blatt

/*
Willkommen zum fünften Aufgabenblatt vom Programmierkurs. Auf diesem Aufabenblatt geht es um Rekursion.

Um die Tests für dieses Blatt zu kompilieren und zu starten, führen Sie den folgenden Befehl aus:
cc -std=c11 -g -Wall 05ex_test.c -o 05ex_test.o -lm && ./05ex_test.o
*/

#include "05_canvas.h"
#include <stdio.h>
#include <math.h>

/*
Aufgabe 1a:
Zeichnen Sie eine horizontale Linie der Länge `width`, deren am weitesten links liegender Pixel bei `(x, y)` ist.

_Benutzen Sie keine Schleifen - Die Aufgabe soll über Rekursion gelöst werden!_

*/
Canvas recursive_line(Canvas c, int x, int y, int width) {

   //nicht rekursive Loesung:
   /* while(width){

        if(x>=0&&y>=0&&x<canvas_width(c)&&y<canvas_height(c)){
            canvas_set_black(c, x, y);
        }
        width--;
        x++;
    }

    return c;
    */
    if(width){

        if(x>=0&&y>=0&&x<canvas_width(c)&&y<canvas_height(c)){
            canvas_set_black(c, x, y);
        }
        x++;
        width--;
        recursive_line(c,x,y,width);
        }

    return c;
}

/*
Aufgabe 1b:
Zeichnen Sie ein Rechteck mit der Breite `width` und der Höhe `height`. Der Pixel der linken unteren Ecke liegt bei `(x, y)`.

_Benutzen Sie keine Schleifen, die Aufgabe soll über Rekursion gelöst werden!_
*/
Canvas recursive_rectangle(Canvas c, int x, int y, int width, int height) {

    /* nicht rekursive loesung:

    while(height){

        recursive_line(c,x,y,width);
        y++;
        height--;
    }

    */

    if(height){
        recursive_line(c,x,y,width);
        y++;
        height--;
        recursive_rectangle(c,x,y,width,height);
    }

    return c;
}

/*
Aufgabe 2:
Der *Sierpinski Carpet der Ordnung 0* ist ein einzelnes schwarzes Pixel.
Der *Sierpinski Carpet der Ordnung n+1* besteht aus acht Sierpinski Carpets der Ordnung n, angeordnet als drei-mal-drei
Quadrat dessen Mittelstück fehlt.

Beispiele (`X` stellt schwarze Pixel dar)
=========================================

Ordnung 0:

X

Ordnung 1:

XXX
X X
XXX

Ordnung 2:

XXXXXXXXX
X XX XX X
XXXXXXXXX
XXX   XXX
X X   X X
XXX   XXX
XXXXXXXXX
X XX XX X
XXXXXXXXX

Siehe auch die Datei `05sierpinski.jpg`

Aufgabe 2a:
Um in der nächsten Aufgabe den Sierpinski-Carpet auf die Canvas zeichnen zu können müssen Potenzen berechnet werden.
Implementieren Sie die Berechnung der Potenz einer nicht-negativen, ganzzahligen Basis `b` mit einem
nicht-negativen, ganzzahligen Exponenten `exp`.

_Benutzen Sie keine Schleifen, die Aufgabe soll über Rekursion gelöst werden!_
*/
int power(int b, int exp){

    int res;

    if (exp == 0) res = 1;
    else if (exp == 1) res = b;

    else{
    exp--;
    res = power(b, exp)*b;
    }

    return res;
}

/*
Aufgabe 2b:
Diese Funktion soll den Sierpinski Carpet der Ordnung `n` auf die Canvas zeichnen, mit unterer linker Ecke an Koordinate `(x, y)`.

_Benutzen Sie keine Schleifen, die Aufgabe soll über Rekursion gelöst werden!_
*/
Canvas sierpinski_carpet(Canvas c, int n, int x, int y){

    if(n==0){
        canvas_set_black(c,x,y);
    }
    /*
    else if(n==1){

        //linke 3 punkte des quaders
        canvas_set_black(c,x,y); //f
        canvas_set_black(c,x,y+1); //d
        canvas_set_black(c,x,y+2); //a

        // oberer unt unterer punkt
        canvas_set_black(c,x+1,y); //g
        canvas_set_black(c,x+1,y+2); //b

        //rechte 3 punkte des quaders
        canvas_set_black(c,x+2,y);    //j
        canvas_set_black(c,x+2,y+1);   //e
        canvas_set_black(c,x+2,y+2);   //c
    }
    */
    else{ // muessen 8 "punkte"/einheiten faerben ;

        // abc
        // d e
        // fgj

        //fuer f startkoordinate = immer (x,y)
        //fuer b = (x+1,y+2) bei n=1; b =(x+3, y+6) bei n=2 ; b = (x+9, y+18) bei n=3 -> (x+1*3^(n-1), y+2*3^(n-1))
        //fuer g = (x+1,y) bei n=1; g = (x+3,y) bei n=2; g = (x+9, y) -> (x+1*3^(n-1), y)
        //fuer d = (x, y+1) bei n=1; -> (x, y+1*3^(n-1))
        //fuer a = (x, y+2) bei n=1; -> (x, y+2*3^(n-1))
        // j = (x+2, y) -> (x+2*3^(n-1), y)
        // e = (x+2, y+1) -> (x+2*3^(n-1), y+1*3^(n-1))
        // c = (x+2, y+2) -> (x+2*3^(n-1), y+2*3^(n-1))

        int n_prev = n-1;

        int x_1 = x + 1*power(3, n_prev);
        int x_2 = x + 2*power(3, n_prev);
        int y_1 = y + 1*power(3, n_prev);
        int y_2 = y + 2*power(3, n_prev);


        sierpinski_carpet(c,n_prev,x,y); // bei (x,y) anfangen und 3x3 teppich zeichnen; aequvalent zu f
        sierpinski_carpet(c,n_prev,x,y_1); // d
        sierpinski_carpet(c,n_prev,x,y_2); // a

        sierpinski_carpet(c,n_prev,x_1,y); //g
        sierpinski_carpet(c,n_prev,x_1,y_2); //b

        sierpinski_carpet(c,n_prev,x_2,y); //j
        sierpinski_carpet(c,n_prev,x_2,y_1); //e
        sierpinski_carpet(c,n_prev,x_2,y_2); //c
    }
    return c;
}

/*
Aufgabe 3:
Implementieren Sie einen schwarzen Fülleimer. Gegeben eine Koordinate `(x, y)` auf einer (bereits bemalten) Canvas, soll die komplette
zusammenhängende Fläche aller Pixel der selben Farbe (schwarz oder weiß) schwarz gefärbt werden.
Zwei Pixel sind Teil der selben Fläche wenn sie die selbe Farbe haben und direkt benachbart sind. Jeder Pixel hat bis
zu vier direkte Nachbarn - die Diagonalen zählen nicht.

Funktionen, um die Farbe eines Pixels auf der Canvas zu bestimmen, sind im Headerfile der Canvas dokumentiert.
*/

// Idee - betrachten ein Pixel und gehen in alle 4 richtungen (betrachten die Nachbarn), faerben die solange sie zur flaeche gehoeren
// oder solange wir kein ende des canvas erreichen
// das ganze wird rekursiv gemacht fuer jeden pixel der flaeche


Canvas bucket_fill(Canvas c, int x, int y) {

    if(x<0 || x>canvas_width(c)-1 || y<0 || y>canvas_height(c)-1) return c; //passt nicht auf canvas
    else {
        if(pixel_is_black(c,x,y)==0){ //muessen faerben

            canvas_set_black(c,x,y); //faerben den punkt und betrachten seine nachbarn
            bucket_fill(c,x+1,y);
            bucket_fill(c,x-1,y);
            bucket_fill(c,x,y+1);
            bucket_fill(c,x,y-1);
        }

    }

    return c;
}