Beispiel Angabe

Kürzel:asciishop-A03-PP
Name:AsciiShop, Runde#3
Kette:Asciishop PP
Kategorie:Bildverarbeitung

Mitgelieferte Datei(en):
Abzugebende Datei(en): AsciiShop.java
Optional abzugebende Datei(en):
Ausführbar: AsciiShop

Die Klasse AsciiShop ist zu erstellen und soll eine ausführbare Klasse sein und muss daher die public static void main(String[] args) Methode beinhalten. Ihr Programm wird automatisch auf Korrektheit überprüft. Die Überprüfung erfolgt durch die Ausführung der als ausführbar bezeichneten Klasse (AsciiShop).

Kurzbeschreibung:

Das Programm liest eine angegebene Anzahl von Zeilen eines ASCII-Bildes ein. Dabei gilt es zu überprüfen, ob alle Zeilen gleich lang sind. Anschließend kann ein fill-Befehl eingegeben werden, dessen Parameter die Position der zu füllenden Fläche beschreibt. Abschließend wird das veränderte Bild sowie seine Breite und Höhe ausgegeben.

Lernziele:

Aufgabenstellung Klassen und Methoden Ein- und Ausgabedaten Bewertung und Kriterien
Hinweise FAQ Fehlerbehandlung Testen

 

Aufgabenstellung:

Einlesen des Bildes

Wie bereits in Runde 1 gilt es, ein ASCII-Bild von der Standardeingabe einzulesen. Vor dem Einlesen des Bildes wird zusätzlich der Befehl read erwartet, dessen Parameter die Anzahl der einzulesenden Zeilen angibt. So bedeutet der Befehl read 5, dass genau 5 Zeilen eingelesen werden sollen. Werden anschließend mehr oder weniger Zeilen als angegeben eingegeben, so soll "INPUT MISMATCH" ausgegeben werden. Die Fehlermeldung soll ebenfalls ausgegeben werden, wenn nicht alle Zeilen gleich lang sind.

Speicherung des Bildes: Einsatz eines Array-Objekts

In dieser Beispielrunde soll folgende Datenstruktur zum Speichern des Bildes verwendet werden: Ein Bild besteht aus mehreren gleich langen Zeilen. Jede Bildzeile ist ein String. Alle Zeilen eines Bildes werden gemeinsam in einem Array aus Strings (Typ String[]) gespeichert.

Bildkoordinaten

Die einzelnen Zeichen des Bildes sind über ihre Koordinaten (x, y) zugreifbar. Die Position (0, 0) befindet sich dabei links oben. Beispielsweise ist das Zeichen mit der Position (9, 2) das zehnte Zeichen in der dritten Bildzeile.

Operationen am Bild:

Wurde das Bild erfolgreich eingelesen, ist danach entweder gar kein Befehl, oder ein- oder mehrmals folgender Befehl zulässig:

Ausgabe

Geben Sie im letzten Schritt das veränderte Bild zeilenweise aus, gefolgt von dessen Breite und Höhe. Sollte kein fill-Befehl eingelesen werden, so soll das unveränderte Bild gefolgt von dessen Breite und Höhe ausgegeben werden.

Füllalgorithmus (Floodfill)

Nach dem Einlesen der Bildzeilen kann optional ein oder mehrmals der Befehl fill folgen, dessen Parameter die Position des Startpixels und das Füllzeichen für einen Floodfill Algorithmus (vgl. Floodfill) darstellen. Es soll eine entsprechende Methode geben, die dann ausgeführt werden soll:

In diesem Beispiel soll der Floodfill Algorithmus rekursiv implementiert werden. Dafür wird eine Methode public static void fill(String[] image, int x, int y, char c) benötigt, die sich selbst rekursiv aufruft. Die Methode soll nur mit zulässigen aktuellen Parameterwerten aufgerufen werden, also gültigen Koordinaten (x, y) (Die Methode darf davon ausgehen, dass die aktuellen Paremeterwerte gültig sind, d.h. die Einhaltung der Vorbedingungen wurden vom Aufrufer der Methode überprüft). Die Methode ersetzt das Zeichen an der angegebenen Position mit dem neuen Zeichen und macht diesen Schritt für alle benachbarten Positionen mit dem selben Zeichenwert in dem sie sich selbst rekursiv aufruft. Als Nachbarschaft wird eine sogenannte Vierer-Nachbarschaft (vgl. Vierer-Nachbarschaft) vorausgesetzt, sprich jeder Pixel hat vier Nachbarn: die über und unter dem Pixel, sowie die links und rechts vom Pixel. Die Methode überprüft für alle vier Nachbarpixel des aktuellen Pixels, ob diese dem zu ersetzenden Zeichen entsprechen (also dasselbe Zeichen beinhalten wie an der aktuellen Position vor der Änderung). Ist das der Fall, wird die Methode an der entsprechenden Nachbarposition rekursiv aufgerufen (Achten Sie auf die Einhaltung von Vorbedingungen). Hat der aktuelle Pixel nicht die zu ersetzende Farbe, so wird dieser Aufruf nicht durchgeführt.


Floodfill mit 4er-Nachbarschaft Wird fill mit der blau gekennzeichneten Position aufgerufen, so werden alle orange gekennzeichneten Pixel gefärbt, da sie mit dem Ausgangspunkt zusammenhängen und die selbe Farbe wie der Ausgangspixel haben.


Foldende Tabelle beinhaltet einen beispielhaften Ablauf der Methode fill:


++++++#
+#+++##
###++#+
+#++#++
+####++
Das Ausgangsbild image mit mehreren Regionen. Es gibt unter Verwendung der Vierer-Nachbarschaft zwei nicht zusammehängende Regionen, die aus dem Zeichen '#' gebildet werden und drei Regionen, die aus dem Zeichen '+' gebildet werden.
++++++#
+#+++##
#o#++#+
+#++#++
+####++
Der Aufruf fill(image, 1, 2, 'o') bewirkt eine Änderung des entsprechenden Zeichens ('#' an der Position (1, 2) wird zu 'o'). Zusätzlich überprüft die Methode welche Nachbarn mit dem Zeichen '#' es gibt (die also zur selben Region zu zählen sind).
++++++#
+#+++##
oo#++#+
+#++#++
+####++
Dabei beginnt die Methode beispielsweise mit dem linken Nachbarn. Dieses Zeichen ist ebenfalls zu ändern, da es den Wert '#' hat. Die Methode ruft daher sich selbst mit den aktuellen Parametern fill(image, 0, 2, 'o') auf. An dieser Position (0, 2) gibt es keine weiteren Nachbarn, die geändert werden sollen (daher führt dieser Aufruf zu keinem weiteren Aufruf).
++++++#
+o+++##
oo#++#+
+#++#++
+####++
Der nächste Nachbar von (1,2) wird geprüft und fill(image, 1, 1, 'o') wird aufgerufen. Auch hier gibt es keinen weiteren Nachbarn der geändert werden muss.
++++++#
+o+++##
ooo++#+
+#++#++
+####++
Der nächste Nachbar von (1,2) wird geprüft und fill(image, 2, 2, 'o') wird aufgerufen. Auch bei diesem Aufruf gibt es keinen weiteren Nachbarn der geändert werden muss.
++++++#
+o+++##
ooo++#+
+o++#++
+####++
Die Überprüfung des unteren Nachbarn von (1,2) führt zum rekursiven Aufruf fill(image, 1, 3, 'o'), da dieser Pixel einen zu ändernden Wert hat.
++++++#
+o+++##
ooo++#+
+o++#++
+o###++
fill(image, 1, 3, 'o') ruft wegen der Überpüfung der Nachbarn von (1,3) wiederum fill(image, 1, 4, 'o') auf.
++++++#
+o+++##
ooo++#+
+o++#++
+oo##++
Für fill(image, 1, 4, 'o') gibt es einen zu ändernden Nachbarn (rechts). Der Aufruf führt daher zu einem weiteren Aufruf...
++++++#
+o+++##
ooo++#+
+o++#++
+ooo#++
... und dieser zu einem weiteren Aufruf (Zeichen rechts) ...
++++++#
+o+++##
ooo++#+
+o++#++
+oooo++
... und dieser zu einem weiteren Aufruf (Zeichen oberhalb) ...
++++++#
+o+++##
ooo++#+
+o++o++
+oooo++
und dieser Aufruf führt schließlich zu keinem weiteren Aufruf, da es keine Nachbarn gibt die geändert werden sollen.

 

Klassen und Methoden:

AsciiShop
Diese Klasse verarbeitet die Eingaben und gibt das Bild aus.
public static void main(String[] args)
Liest Daten und Befehle ein, macht die Fehlerbehandlung und gibt das Ergebnis aus.
public static void fill(String[] image, int x, int y, char c)
Ersetzt das Zeichen an der Position (x,y) mit dem Zeichen c und ruft sich ggfs. selbst rekursiv auf (mit neuen Werten von (x,y) die den Nachbarpositionen entsprechen).

 

Allgemeine Hinweise:

 

Hinweise:

Beachten Sie die allgemeinen Hinweise zur Installation und zur Ein-/Ausgabe, sowie zur Abgabe und zur Beurteilung in den FAQ. Beispiele zum Umgang mit Ein-/Ausgabe sowie den Methoden der Klasse String finden Sie im Skriptum oder in den Vorlesungsfolien.

Einlesen des Bildes

Verwenden Sie zum Einlesen des Bildes von der Standardeingabe die Klasse Scanner. Relevant sind insbesondere die Methoden next und hasNext bzw. nextLine und hasNextLine.

Zeilenlänge

Zum Bestimmen der Zeilenlänge bietet die Klasse String die Methode length.

Zugriff auf Zeichen des Bildes

Für den Lesezugriff ein einzelnes Zeichen einer Bildzeile steht die Methode charAt(int) für Strings zur Verfügung. Soll ein Zeichen geändert werden, muss die gesamte Bildzeile neu erzeugt werden.

Ausgabe

Für die Ausgabe über die Standardausgabe verwenden Sie die Methoden System.out.print und System.out.println.

Testen

Es gibt zwei Möglichkeiten Ihr Programm zu testen: Sie können einerseits Eingaben in der Console vornehmen - entweder per direkter Eingabe oder auch per Einfügen von der Zwischenablage. Um die Eingaben in der Console abzuschließen, geben Sie einen Zeilenumbruch gefolgt vom EOF-Zeichen (Tastenkombination Strg+Z (Windows) bzw. Strg+D (Mac, Linux)) ein. Das EOF-Zeichen muss dabei am Anfang einer Zeile stehen, geben Sie also beispielsweise nach der letzten Bildzeile Enter und dann Strg+Z/Strg+D ein.
Andererseits können Sie den Inhalt einer Datei als Eingabe verwenden: java MyProgram < input.txt > output.txt. Hierbei wird der Inhalt der Datei input.txt gelesen und als Eingabe an MyProgram weitergereicht. Die gesamte Ausgabe wird in die Datei output.txt geschrieben.

Nicht-Funktionale Anforderungen

Im Rahmen des Abschlussgesprächs wird die Abgabe nach Kriterien wie Einhaltung der in der Angabe beschriebenen nicht-funktionalen Anforderungen, sowie Dokumentation (sprich Kommentare), Übersichtlichkeit des Codes, Verständnis, etc. beurteilt.

Wenn Sie Fragen zur Implementierung oder auch zu Java haben, können Sie das Informatik-Forum nutzen. Im Rahmen der wöchentlichen Laborien stehen Tutoren für Fragen zur Verfügung.
Informatik-Forum Laborien

 

Eingabedaten:

Ein read Befehl gefolgt von der Anzahl an Zeilen, die einzulesen sind, sowie den einzelnen Zeilen eines ASCII-Bildes. Es darf davon ausgegangen werden, dass das Bild keine Leerzeichen enthält. Nach dem Einlesen des Bildes kann ein fill Befehl gefolgt von einer x - position, einer y - position und dem Füllzeichen eingegeben werden.

Ausgabedaten:

Das veränderte ASCII-Bild sowie dessen Höhe und Breite.

Fehlerbehandlung:

Geben Sie "INPUT MISMATCH" aus und brechen Sie die weitere Verarbeitung ab, falls einer der folgenden Fehler auftritt:

Geben Sie "OPERATION FAILED" aus und brechen Sie die weitere Verarbeitung ab der folgende Fehler auftritt:

Testen:


In
read 27
============,.V+.;============
===========;.X##..;===========
===========..####..===========
==========,.##M###.:==========
=========;.R##WW##=.;=========
=========..##MWMW##,.=========
========:.I##WWMWW#W.,========
=======;.:##WWWWWW##I.;=======
=======:.W########M##..=======
=======.:############V.;======
=======.####...,.,M###,.======
======,.###:..+++;,B..#.;=====
=====;.#;.#i+YXVVY:#V.#..:====
====:..#..##.RYYIt##...#=.,===
==;..+#;...#######W....##W..:=
:..t###......iVV=....,.+#iM#..
.B#i,#..,,..........,,..#,..#I
V#...#..,,,,,.,,,,:,,,..R#..V#
;#+.i#..,,,,,,,,,.,,,,,.iX.X#,
.i#=MV..,,,,.,,,,,,.,,,..###..
,.t##..,,,,,,,,,,,,,,:,..V##.;
..M#M..,,,,.,.,,,,,,,:,,.=##..
i###M..,...........,,:,,..###.
.####........=II;.....,,.;##R.
,...#....X####MW###B.....Wi..:
==;,##,###;........##i...#;,==
===,.IVi..,;======:..B#B#t.;==
fill 2 28 m
Out
OPERATION FAILED
Beschreibung Die Füllkoordinaten können zwar eingelesen werden liegen aber außerhalb des Bildbereichs.


In
27
============,.V+.;============
===========;.X##..;===========
===========..####..===========
==========,.##M###.:==========
=========;.R##WW##=.;=========
=========..##MWMW##,.=========
========:.I##WWMWW#W.,========
=======;.:##WWWWWW##I.;=======
=======:.W########M##..=======
=======.:############V.;======
=======.####...,.,M###,.======
======,.###:..+++;,B..#.;=====
=====;.#;.#i+YXVVY:#V.#..:====
====:..#..##.RYYIt##...#=.,===
==;..+#;...#######W....##W..:=
:..t###......iVV=....,.+#iM#..
.B#i,#..,,..........,,..#,..#I
V#...#..,,,,,.,,,,:,,,..R#..V#
;#+.i#..,,,,,,,,,.,,,,,.iX.X#,
.i#=MV..,,,,.,,,,,,.,,,..###..
,.t##..,,,,,,,,,,,,,,:,..V##.;
..M#M..,,,,.,.,,,,,,,:,,.=##..
i###M..,...........,,:,,..###.
.####........=II;.....,,.;##R.
,...#....X####MW###B.....Wi..:
==;,##,###;........##i...#;,==
===,.IVi..,;======:..B#B#t.;==
fill 1 2 m
Out
INPUT MISMATCH
Beschreibung Der erste Befehl ist nicht read.


In
read 27
============,.V+.;============
===========;.X##..;===========
===========..####..===========
==========,.##M###.:==========
fill 1 2 m
Out
INPUT MISMATCH
Beschreibung Es wurden zu wenige Zeilen eingegeben.


In
read 27
============,.V+.;============
===========;.X##..;===========
===========..####..===========
==========,.##M###.:==========
=========;.R##WW##=.;=========
=========..##MWMW##,.=========
========:.I##WWMWW#W.,========
=======;.:##WWWWWW##I.;=======
=======:.W########M##..=======
=======.:############V.;======
=======.####...,.,M###,.======
======,.###:..+++;,B..#.;=====
=====;.#;.#i+YXVVY:#V.#..:====
====:..#..##.RYYIt##...#=.,===
==;..+#;...#######W....##W..:=
:..t###......iVV=....,.+#iM#..
.B#i,#..,,..........,,..#,..#I
V#...#..,,,,,.,,,,:,,,..R#..V#
;#+.i#..,,,,,,,,,.,,,,,.iX.X#,
.i#=MV..,,,,.,,,,,,.,,,..###..
,.t##..,,,,,,,,,,,,,,:,..V##.;
..M#M..,,,,.,.,,,,,,,:,,.=##..
i###M..,...........,,:,,..###.
.####........=II;.....,,.;##R.
,...#....X####MW###B.....Wi..:
==;,##,###;........##i...#;,==
===,.IVi..,;======:..B#B#t.;==
fill 0 0 $
fill 20 1 #
Out
$$$$$$$$$$$$,.V+.;############
$$$$$$$$$$$;.X##..;###########
$$$$$$$$$$$..####..###########
$$$$$$$$$$,.##M###.:##########
$$$$$$$$$;.R##WW##=.;#########
$$$$$$$$$..##MWMW##,.#########
$$$$$$$$:.I##WWMWW#W.,########
$$$$$$$;.:##WWWWWW##I.;#######
$$$$$$$:.W########M##..#######
$$$$$$$.:############V.;######
$$$$$$$.####...,.,M###,.######
$$$$$$,.###:..+++;,B..#.;#####
$$$$$;.#;.#i+YXVVY:#V.#..:####
$$$$:..#..##.RYYIt##...#=.,###
$$;..+#;...#######W....##W..:#
:..t###......iVV=....,.+#iM#..
.B#i,#..,,..........,,..#,..#I
V#...#..,,,,,.,,,,:,,,..R#..V#
;#+.i#..,,,,,,,,,.,,,,,.iX.X#,
.i#=MV..,,,,.,,,,,,.,,,..###..
,.t##..,,,,,,,,,,,,,,:,..V##.;
..M#M..,,,,.,.,,,,,,,:,,.=##..
i###M..,...........,,:,,..###.
.####........=II;.....,,.;##R.
,...#....X####MW###B.....Wi..:
==;,##,###;........##i...#;,==
===,.IVi..,;======:..B#B#t.;==
30 27
Beschreibung Ein Bild wird eingelesen und danach wird zwei mal der fill-Befehl aufgerufen


In
read 27
============,.V+.;============
===========;.X##..;===========
===========..####..===========
==========,.##M###.:==========
=========;.R##WW##=.;=========
=========..##MWMW##,.=========
========:.I##WWMWW#W.,========
=======;.:##WWWWWW##I.;=======
=======:.W########M##..=======
=======.:############V.;======
=======.####...,.,M###,.======
======,.###:..+++;,B..#.;=====
=====;.#;.#i+YXVVY:#V.#..:====
====:..#..##.RYYIt##...#=.,===
==;..+#;...#######W....##W..:=
:..t###......iVV=....,.+#iM#..
.B#i,#..,,..........,,..#,..#I
V#...#..,,,,,.,,,,:,,,..R#..V#
;#+.i#..,,,,,,,,,.,,,,,.iX.X#,
.i#=MV..,,,,.,,,,,,.,,,..###..
,.t##..,,,,,,,,,,,,,,:,..V##.;
..M#M..,,,,.,.,,,,,,,:,,.=##..
i###M..,...........,,:,,..###.
.####........=II;.....,,.;##R.
,...#....X####MW###B.....Wi..:
==;,##,###;........##i...#;,==
===,.IVi..,;======:..B#B#t.;==
fill 0 0 $
fill 0 u
Out
INPUT MISMATCH
Beschreibung Die Parameter des zweiten fill-Befehls können nicht eingelesen werden


Bemerkung: Diese Beispiele dienen nur zur Verdeutlichung der Spezifikation und müssen nicht korrekt formatiert sein. Die korrekte Formatierung entnehmen Sie bitte dem mitgelieferten Outputfile. Zum Testen Ihrer Lösung können Sie aus den mitgelieferten Eingabedaten wie folgt eine Ausgabedatei erzeugen:
java AsciiShop < asciishop-A03-PP.i1 > asciishop-A03-PP.out1

Das erzeugte File asciishop-A03-PP.out1 können Sie dann mit dem mitgelieferten Outputfile asciishop-A03-PP.o1 vergleichen.