iterativer Ansatz für die Floodfill-Operation

IterativeFloodfillOperation.java

import java.util.*;

/**
 * Ein iterativer Ansatz für die Floodfill-Operation, weil Rekursion
 * gern mal zu Stack-Overflows führt.
 *
 * Danke an die LVA-Leitung von AlgoDat1, die mir diesen "Trick" beibrachte.
 *
 * Für jeden Punkt, der aus der Queue entnommen wird, werden der Queue vier
 * weitere Punkte hinzugefügt – es sei denn, der entnommene Punkt
 * gehört nicht zur Fläche, die wir füllen wollen, oder ist
 * außerhalb des Bilds. Das Verfahren terminiert also stets für alle
 * Bilder endlicher Größe.
 */
public class IterativeFloodfillOperation implements Operation
{
	/**
	 * Hilfsklasse für das Verfahren. Speichert einen Punkt.
	 */
	public static class FillPoint
	{
		/* Koordinaten */
		private int x, y;

		/**
		 * Konstruiert einen Punkt aus zwei Koordinaten.
		 * @param x x-Koordinate (horizontal)
		 * @param y y-Koordinate (vertikal)
		 */
		public FillPoint(int x, int y)
		{
			this.x = x;
			this.y = y;
		}

		/**
		 * Kopierkonstruktor: konstruiert einen Punkt mit den Koordinaten des übergebenen Punktes.
		 * @param pt Bestehender FillPoint, aus dem die Koordinaten kopiert werden.
		 */
		public FillPoint(FillPoint pt)
		{
			x = pt.x;
			y = pt.y;
		}

		/**
		 * Holt die x-Koordinate.
		 */
		public int getX()
		{
			return x;
		}

		/**
		 * Holt die y-Koordinate.
		 */
		public int getY()
		{
			return y;
		}

		/**
		 * Überprüft zwei Objekte auf Gleichheit.
		 * @param o Das andere Objekt, mit dem verglichen wird.
		 */
		public boolean equals(Object o)
		{
			// o ist kein FillPoint --> ungleich.
			if (!(o instanceof FillPoint))
				return false;

			return equals((FillPoint)o);
		}

		/**
		 * Üebrprüft zwei Punkte auf Gleichheit.
		 * @param o Der andere Punkt, mit dem verglichen wird.
		 */
		public boolean equals(FillPoint o)
		{
			return (x == o.x && y == o.y);
		}

		/**
		 * Vorgeschriebene Hash-Funktion. Muss bei Umdefinitionen von <code>equals</code> ebenfalls umdefiniert werden.
		 * Interessant nur f&uuml;r Hashtabellen und darauf aufbauende Konzepte wie <code>HashSet</code>s.
		 * Stoff von AlgoDat1.
		 *
		 * Es gilt: wenn zwei Punkte gleich sind, haben sie den gleichen Hashcode.
		 * Es gilt <b>nicht</b>: wenn zwei Punkte den gleichen Hashcode haben, sind sie gleich.
		 * (Implikation, nicht &Auml;quivalenz!)
		 */
		public int hashCode()
		{
			return (x << 16) + y;
		}
	}

	/** Koordinaten des Anfangspunktes. */
	int x, y;

	/** Zeichen, durch das ersetzt wird. */
	char c;

	/**
	 * Erstellt eine neue Floodfill-Operation (iterativer Ansatz).
	 * @param x <i>x</i>-Koordinate des Anfangspunktes.
	 * @param y <i>y</i>-Koordinate des Anfangspunktes.
	 * @param c Zeichen, mit dem die Fl&auml;che geflutet werden soll.
	 */
	public IterativeFloodfillOperation(int x, int y, char c) throws OperationException
	{
		this.x = x;
		this.y = y;
		this.c = c;

		if (x < 0)
			throw new OperationException("x kleiner als 0");
		if (y < 0)
			throw new OperationException("y kleiner als 0");
	}

	/**
	 * Erstellt ein neues AsciiImage, in dem die entsprechende Fl&auml;che mit dem entsprechenden Zeichen geflutet wird (siehe Konstruktor).
	 * @param img Bild, auf dem die Fl&auml;che geflutet werden soll.
	 */
	public AsciiImage execute(AsciiImage img) throws OperationException
	{
		// Grenzen-Check
		if (x >= img.getWidth())
			throw new OperationException("x gr\u00f6\u00dfer gleich der Breite des Bildes");
		if (y >= img.getHeight())
			throw new OperationException("y gr\u00f6\u00dfer gleich der H\u00f6he des Bildes");
		if (img.getCharset().indexOf(c) < 0)
			throw new OperationException("c nicht im Zeichensatz des Bildes");

		// f&uuml;hre &Auml;nderungen ja nicht am Ursprungsbild aus
		AsciiImage ret = new AsciiImage(img);

		// unsere Queue, das Herzst&uuml;ck des iterativen Verfahrens
		// (kann durch Stack ersetzt werden; &auml;ndert die Abklapperreihenfolge)
		Queue<FillPoint> q = new LinkedList<FillPoint>();

		// urspr&uuml;nglicher Pixelwert
		char old = ret.getPixel(x, y);

		// f&uuml;ge Startpunkt in die Queue ein
		q.add(new FillPoint(x, y));

		// solange die Queue nicht leer ist
		while (!q.isEmpty())
		{
			// hole Punkt aus Queue
			FillPoint punkt = q.remove();

			// speichere Koordinaten f&uuml;r schnelleren und angenehmeren Zugriff
			int px = punkt.getX();
			int py = punkt.getY();

			// ist dieser Punkt innerhalb der Gr&ouml;&szlig;e des Bildes?
			if (
				px < 0 || px >= img.getWidth() ||
				py < 0 || py >= img.getHeight()
			)
			{
				// mach mit n&auml;chstem Punkt in der Queue weiter
				continue;
			}

			// hat dieser Punkt die Farbe, die wir ersetzen?
			if (ret.getPixel(px, py) != old)
			{
				// nein; mach mit n&auml;chstem Punkt in der Queue weiter
				continue;
			}

			// f&auml;rbe diesen Punkt auf die neue Farbe ein (old --> c)
			ret.setPixel(px, py, c);

			// f&uuml;ge seine vier Nachbarn in die Queue ein
			q.add(new FillPoint(px-1, py  ));
			q.add(new FillPoint(px+1, py  ));
			q.add(new FillPoint(px  , py-1));
			q.add(new FillPoint(px  , py+1));
		}

		// gib das modifizierte Bild zur&uuml;ck
		return ret;
	}
}