Eine weitere Aufgabe war das Füllen eines Bildbereiches über eine rekursive Funktion.
Dazu wird ein sogenannter Impfpixel an einem Startpunkt definiert. Von diesem Start-Impfpixel liest man einen Wert aus, und alle Pixel in der Umgebung mit demselben Wert werden auf einen neuen Farbwert gesetzt (inklusive des Start-Impfpixels).
In der Fill-Funktion wird als erstes u. a. abgefragt ob der neue Impfpixel außerhalb des gültigen Bereichs der Matrix liegt und vor allem ob der Farbwert dieses Pixels ungleich des ursprünglichen Farbwertes vom Start-Impfpixel ist (denn es sollen nur Bereiche mit identischem Farbwert gefüllt werden) – wenn diese Bedingungen zutreffen wird aus der Rekursion zurückgesprungen.
Ansonsten wird der Wert des Impfpixels auf den neuen Wert gesetzt. Anschließend wird die Funktion rekursiv für die vier angrenzenden (Diagonalen zählen nicht) Nachbarpixel aufgerufen, im Uhrzeigersinn.
Die Rekursion funktioniert weitergehend folgendermaßen: Er geht solange vom Impfpixel ausgehend nach oben bis er einen Pixel mit einem anderen Farbwert als den, den er austauschen soll, findet – oder bis er an die Grenzen der Matrix stösst. Auf dem Weg dahin werden natürlich diese Pixel mit dem neuen Farbwert gefüllt.
Wenn der Weg erschöpft ist geht er einen Pixel nach rechts (sofern möglich), füllt ihn, und versucht anschließend wieder nach oben zu gehen usw. usf.. Dies im Uhrzeigersinn, aber die Reihenfolge ist eigentlich irrelevant.
Ein Kommilitone verglich den Weg des Algorithmus mit einem Schneckenhaus, das trifft es ganz gut. Das Programm funktioniert nur mit graustufigen PGM-Bildern.
Nun weiss ich auch wie das Quoten - das Umschließen mit doppelten Anführungszeichen für Dateipfade mit Leerzeichen - in C(++) funktioniert. Das sieht dort folgendermaßen aus:
Eigentlich muss in C(++) bei einer Funktion mit zweidimensionalen Arrays nur die Größe der zweiten Dimension angegeben werden - siehe hier - aber ich habe beide Dimensionen im Prototypen festgelegt.
Nachfolgend der Quellcode, dieses Mal mit Syntax-Highlighting. BlogEngine.NET unterstützt beim Highlighting eigentlich nur C# und nicht C(++), aber die Stichwörter sind eigentlich identisch.
/*
* =====================================================================================
*
* Filename: FillPicture
*
* Description:
*
* Version: 1.0
* Created:
* Revision: none
* Compiler: gcc
*
* Author: Thomas Kramer
* Company:
*
* =====================================================================================
*/
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <ctype.h>
#include <time.h>
#include <assert.h>
#include <string.h>
#define Max_Zeilen 1000
#define Max_Spalten 1000
#define PIX_MAX 1000
unsigned char Bild[Max_Zeilen][Max_Spalten];
unsigned char Bild2[Max_Zeilen][Max_Spalten];
/* m: Bildmatrix, nx, ny: Bildgröße, is, js: Koordinate Impfpixel, oldval bzw. newval: alter bzw. neuer Farbwert*/
void fill(unsigned char m[PIX_MAX][PIX_MAX],
int nx, int ny,
int is, int js,
unsigned char oldval,
unsigned char newval);
int main()
{
FILE *infile;
FILE *outfile;
char typ[3];
int b=0;
int h=0;
int graumax=0;
int z=0;
int s=0;
int temp=0;
unsigned char temp2;
/*-----------------------------------------------------------------------------
* Datei einlesen, Format prüfen
*-----------------------------------------------------------------------------*/
infile = fopen("C:\\Pfad\\bild.pgm", "r");
if (infile == NULL) {
printf("\nDatei konnte nicht geöffnet werden");
exit(1);
}
typ[0]=fgetc(infile);
typ[1]=fgetc(infile);
typ[2]=fgetc(infile);
if ((typ[0]!='P') || (typ[1]!='2') || (typ[2]!='\n'))
{
printf("\nCodierung des Dateityps falsch!\n");
fclose(infile);
exit(1);
}
/*-----------------------------------------------------------------------------
* Inhalte von Datei einlesen
*-----------------------------------------------------------------------------*/
if (fscanf(infile, "%i %i %i", &b, &h, &graumax)==3)
{
//printf("Breite: %i", b);
//printf(", Höhe: %i", h);
//printf(", max. Grauwert: %i", graumax);
if ((b>Max_Spalten) || (h>Max_Zeilen))
{
printf("\nBild zum Einlesen zu groß!\n");
fclose(infile);
exit(1);
}
else if ((b<=1) || (h<=1))
{
printf("\nBildgröße ergibt keinen Sinn!\n");
fclose(infile);
exit(1);
}
for (z=0;z<h;z+=1)
{
for (s=0;s<b;s+=1)
{
if (fscanf(infile, "%i", &temp)==1)
{
if ((temp>=0) && (temp<=graumax))
{
Bild[z][s]=temp;
}
else
{
printf("\nBild falsch codiert!\n");
fclose(infile);
exit(1);
}
}
}
}
fclose(infile);
/*-----------------------------------------------------------------------------
* Bild in neues Array kopieren
*-----------------------------------------------------------------------------*/
for (z=0;z<h;z+=1)
{
for (s=0;s<b;s+=1)
{
Bild2[z][s]=Bild[z][s];
}
}
/*-----------------------------------------------------------------------------
* Bild bearbeiten
*-----------------------------------------------------------------------------*/
printf("Neuen Grauwert für Pixel an der Stelle x=10, y=10 eingeben: ");
scanf("%c", &temp2);
fill(Bild2, b, h, 10, 10, Bild2[10][10], temp2);
/*-----------------------------------------------------------------------------
* in neue Datei ausgeben, aus dem neuen Array
*-----------------------------------------------------------------------------*/
outfile = fopen("C:\\Pfad\\bild.out.pgm", "w");
if (outfile == NULL) {
printf("\nDatei konnte nicht erstellt werden");
exit(1);
}
fprintf(outfile, "%c%c\n", typ[0], typ[1]);
fprintf(outfile, "%i %i\n", b, h);
fprintf(outfile, "%i\n", graumax);
for (z=0;z<h;z+=1)
{
for (s=0;s<b;s+=1)
{
fprintf(outfile," %3i", Bild2[z][s]);
}
}
fclose(outfile);
}
/*-----------------------------------------------------------------------------
* Ausgabe-Bilddatei öffnen
*-----------------------------------------------------------------------------*/
system("\"C:\\Pfad\\bild.out.pgm\"");
return 0;
}
void fill(unsigned char m[PIX_MAX][PIX_MAX],
int nx, int ny, // Bildgroesse
int is, int js, // Koord. Impfpixel
unsigned char oldval, // alter Farbwert
unsigned char newval) // neuer Farbwert
{
if (m==NULL ||
nx < 1 || nx > PIX_MAX || ny < 1 || ny > PIX_MAX ||
is < 0 || is >= nx || js < 0 || js >= ny ||
oldval < 0 || oldval == newval || newval < 0 ||
m[js][is] != oldval)
return;
m[js][is]=newval;
// nach oben
fill(m, nx, ny, is, js-1, oldval, newval);
// nach rechts
fill(m, nx, ny, is+1, js, oldval, newval);
// nach unten
fill(m, nx, ny, is, js+1, oldval, newval);
// nach links
fill(m, nx, ny, is-1, js, oldval, newval);
}
