Der Flood-Fill-Algorithmus

1. Aufgabe

Der Flood-Fill-Algorithmus ist ein so genannter Füll-Algorithmus. Er wurde in den Anfangstagen der Computertechnik in Grafikkarten eingesetzt, um umrandete Flächen auszufüllen. Das Innere der auszufüllenden Fläche muss durch ein geschlossenes Polygon umrandet sein. Viele bekannte Grafikprogramme (wie zum Beispiel MS Paint) verwenden diesen Algorithmus, wenn mit dem Farbeimer bestimmte Flächen mit einer anderen Farbe auszufüllen sind. Die zu füllende Kontur muss allerdings geschlossen sein. Ist irgendwo eine offene Stelle, „läuft“ die Farbe raus.

Wir konzipieren die Aufgabe an Hand des Model-View-Controller-Paradigmas. Wir schreiten für die Entwicklung der gesamten Anwendung in fünf Teilschritten voran:

  • Implementierung des Modells

  • Realisierung der Sicht

  • Realisierung des Controllers

  • Analyse des Speicherplatzverbrauchs des Modells

  • Zweite (iterative) Realisierung des Modells

1.1. Implementierung des Modells

Die auszufüllenden Flächen in dieser Aufgabe sind Polygone. Das Modell verwaltet ihre Koordinaten (Eckpunkte und Kanten). Zur Vereinfachung der Aufgabe bestehen die Polygone in dieser Aufgabe nur aus horizontal oder vertikal verlaufenden Linien, also keinen „schrägen“ Linien. Damit lässt sich das Polygon durch eine Liste von Pixeln beschreiben. Das Polygon wiederum befindet sich in einem Rechteck, der Zeichenfläche.

Zum Beginn des Programms ist die gesamte Zeichenfläche mit einer Farbe ungleich schwarz zu initialisieren (zum Beispiel weiß). Zusätzlich ist innerhalb der Zeichenfläche ein geschlossener Polygonzug mit schwarzen Pixeln darzustellen.

Für den Flood-Fill-Algorithmus benötigen wir des Weiteren einen Startpunkt (Start-Pixel). Ausgehend von diesem Pixel werden (innerhalb des Rands, der durch die schwarze Farbe des umgebenden Polygonzugs erkennbar ist) jeweils dessen Nachbarpixel darauf getestet, ob diese ebenfalls dieselbe (ursprüngliche) Farbe besitzen. Jedes auf diese Weise gefundene Pixel mit der alten Farbe wird dabei sofort durch die neue Farbe ersetzt. Siehe für weitere Details den folgenden Pseudo-Code der Methode FloodFill:

// globals
int oldColor;
int newColor;
....

void FloodFill (int x, int y)   // x,y: pixel coordinates
{
    if (GetPixel(x, y) == oldColor)
    {
        SetPixel (x, y, newColor);

        FloodFill (x, y + 1);  // unten
        FloodFill (x - 1, y);  // links
        FloodFill (x, y - 1);  // oben
        FloodFill (x + 1, y);  // rechts
    }
}

Zum Zwecke der Animation ist der Flood-Fill-Algorithmus zeitverzögert auszuführen. Mit einer Start-Methode wird der Algorithmus im Modell angestoßen. Mit Stopp bricht man die Ausführung des Algorithmus ab. Jede Änderung einer Pixelfarbe („Einfärbung“) ist durch ein Ereignis mitzuteilen. Weitere Details und Anregungen für die Entwicklung einer Klasse FloodFillModel finden Sie in Tabelle 1 vor. Bitte beachten Sie: Diese Klasse ist von der Klasse System.Object abzuleiten, sie besitzt also keine Oberfläche.

Element

Beschreibung

Eigenschaft Size

Dimension Size { set; }

Die Size-Eigenschaft dient zum Setzen der maximalen Breite und Höhe der grafischen Zeichenfläche, in der sich das auszufüllende Polygon befindet. Bei Bedarf dürfen Sie für den Datentyp Dimension eine C#-Struktur selbst definieren:

public struct Dimension
{
    public int Width { get; set; }
    public int Height { get; set; }
}

Methode Start

public void Start();

Stößt die Berechnungen des Flood-Fill-Algorithmus an. Ein Aufruf von Start nimmt nur den Auftrag zum Starten des Algorithmus entgegen, die Methode kehrt sofort zum Aufrufer zurück.

Methode Stop

public void Stop();

Bricht einen vorangegangenen Aufruf von Start vorzeitig ab, sofern dieser Auftrag noch aktiv ist.

Methode SetStartPosition

public void SetStartPosition (int x, int y);

Mit Hilfe der beiden Parameter x und y wird der Ausgangspunkt für den Flood-Fill-Algorithmus übergeben.

Methode SetPolygon

public void SetPolygon (List<Point> polygon);

Dient zum Festlegen des Polygons, dessen innere Fläche auszufüllen ist. Die Liste polygon, bestehend aus Point-Objekten, enthält alle Pixel des Polygonrands.

Ereignis PixelChanged

public event PixelChangedHandler PixelChanged;

Das PixelChanged-Ereignis ist auszulösen, wenn das Modell ein Pixel eingefärbt hat. Die Definition des Delegate-Typs PixelChangedHandler bleibt Ihnen überlassen.

Tabelle 1. Elemente der Klasse FloodFillModel.

1.2. Realisierung der Sicht

Eine Sicht der Anwendung könnte wie in Abbildung 1 gezeigt aussehen:

Sicht des Flood-Fill-Algorithmus (mit fest vorgegebenem Polygonzug).

Abbildung 1. Sicht des Flood-Fill-Algorithmus (mit fest vorgegebenem Polygonzug).


Eine Ansicht des Flood-Fill-Algorithmus benötigt Informationen zur Größe der Zeichenfläche. Hinzu kommt eine Methode SetPixel, um ein Pixel einzufärben (Tabelle 2). Entwickeln Sie eine Ansicht des Modells auf Basis eines WPF-User-Controls und versehen Sie das Steuerelement mit dem Namen FloodFillViewControl:

Element

Beschreibung

Eigenschaft Size

Dimension Size { set; }

Die Size-Eigenschaft dient zum Setzen der maximalen Breite und Höhe der grafischen Zeichenfläche, in der sich das auszufüllende Polygon befindet.

Methode GetStartPosition

public Point GetStartPosition ();

Liefert die Koordinaten (x- und y-Wert) des Start-Pixels zurück.

Methode SetPixel

public void SetPixel (int x, int y, Color color);

Mit Hilfe von x und y wird ein Pixel in der Zeichenfläche beschrieben, dass mit der Farbe color einzufärben ist.

Tabelle 2. Elemente der Klasse FloodFillViewControl.


Um für den Flood-Fill-Algorithmus einen Startwert zu haben, gibt es am FloodFillViewControl-Steuerelement die Methode GetStartPosition. Im Hauptfenster kann man vor dem Starten des Algorithmus so den Startwert bestimmen und an das Modell weiterreichen.

1.3. Realisierung des Controllers

Zum Starten des Algorithmus ist ein Startpunkt (Startpixel) festzulegen. Dies erfolgt durch einen Mausklick in der Ansicht.

In einem weiteren Steuerelement (ToolbarPanel) sind zwei Schaltflächen mit der Beschriftung „Start“ bzw. „Stopp“ anzuordnen. Bei Klick auf „Start“ startet die Anwendung, bei „Stopp“ wird sie abgebrochen. Einen Schnappschuss der laufenden Anwendung finden Sie in Abbildung 2 vor:

Teilausführung des Flood-Fill-Algorithmus.

Abbildung 2. Teilausführung des Flood-Fill-Algorithmus.


In Abbildung 2 finden wir neben den grauen Punkten (Polygonzug) bereits eine Menge grauer Punkte (Pixel) im Innern des Polygons vor, deren Farbe bereits geändert wurde. Die weißen Punkte im Polygonzug sind noch einzufärben.

1.4. Analyse des Speicherplatzverbrauchs des Modells

Der Algorithmus ist hochgradig rekursiv. Daher besteht prinzipiell ein hohes Risiko, dass der Algorithmus zu einem Stack-Überlauf führt. Ebenso benötigen die vielen Stack-Operationen durch die Rekursionen im Vergleich zu den eigentlichen Operationen des Algorithmus relativ viel Zeit. Zum Zwecke einer Analyse ergänzen Sie das Modell um den delegate-Typ StackSizeChangedHandler:

public delegate void StackSizeChangedHandler (int size);

Den Controller der Anwendung erweitern Sie wie in Abbildung 3 dargestellt:

Analyse der Stack-Tiefe des Flood-Fill-Algorithmus.

Abbildung 3. Analyse der Stack-Tiefe des Flood-Fill-Algorithmus.


Ergänzen Sie das Modell um ein Ereignis StackSizeNeeded, das angibt, welche Stapelgröße zum jeweiligen Zeitpunkt in der Ausführung des Algorithmus im Modell erforderlich ist. Im Controller der Anwendung (die bzgl. der Stapelgröße im Modell nun auch einen View-Charakter bekommt) zeigen Sie die aktuell benötigte Stapelgröße und die bislang im Verlauf maximal benötigte Stapelgröße an.

1.5. Zweite (iterative) Realisierung des Modells

Mit Hilfe eines Stapelspeichers, oder einer ähnlichen Datenstruktur, ist auch eine iterative Implementierung möglich. Dabei werden in einem Schritt des Algorithmus die Nachbarpixel-Koordinaten gespeichert und dann nacheinander sequentiell abgearbeitet. Die Reihenfolge, in der die Koordinaten aus der Datenstruktur ausgelesen werden, spielt dabei keine Rolle.

Siehe für weitere Details den folgenden Pseudo-Code der Methode FloodFillIterative:

// globals
int oldColor;
int newColor;
....

void FloodFillIterative (int x, int y)    // x,y: pixel coordinates
{
    localPointStack.Push (x, y);

    while (! localPointStack.IsEmpty)
    {
        Point p = localPointStack.Pop ();
        if (GetPixel(p.x, p.y) == oldColor)
        {
            SetPixel (p.x, p.y, newColor);

            localPointStack.Push (p.x, p.y + 1); // unten
            localPointStack.Push (p.x - 1, p.y); // links
            localPointStack.Push (p.x, p.y - 1); // oben
            localPointStack.Push (p.x + 1, p.y); // rechts
        }
    }
}

Implementieren Sie den Flood-Fill-Algorithmus in beiden Varianten. Welche maximale Stapelgröße benötigt die iterative Variante des Algorithmus? Können Sie eine Optimierung des Modells bzgl. seines Speicherplatzverbrauchs erkennen?

2. Lösung

Wir fangen erst einmal mit den einfachen Sachen an, wie zum Beispiel einem Datentyp Point oder auch Dimension. Derartige Datentypen sind in der .NET-Standardklassenbibliothek natürlich vorhanden, sogar – wenn ich mich nicht täusche – mehrere Male. Der Punkt ist nur: Das Modell in dieser Aufgabe war in meinen Überlegungen frei von Abhängigkeiten irgendwelcher .NET-Bibliotheken gedacht, die man speziell für eine graphische Programmierung benötigt. Ist vielleicht etwas akademisch gedacht, man kann dazu auch eine andere Meinung haben. Nichtsdestotrotz war es mir sympathischer, eine Modell-Realisierung ohne graphische .NET-Bibliotheken auf die Beine zu stellen. In diesem Fall muss man diese beiden Datentypen eben selbst bereitstellen. Beachten Sie dabei: Es genügen dafür leichtgewichtige C#-Strukturen:

public struct Point
{
    public int X { get; set; }
    public int Y { get; set; }

    public override String ToString()
    {
        return String.Format("[{0}, {1}]", this.X, this.Y);
    }
}

public struct Dimension
{
    public int Width { get; set; }
    public int Height { get; set; }
    
    public override String ToString()
    {
        return String.Format("Width={0}, Height={1}", this.Width, this.Height);
    }
}

Nachdem wir uns schon einem akademischen Touch unterworfen haben, belassen wir gleich dabei. Die folgenden Code-Fragmente steuern natürlich auf eine Realisierung des in Tabelle 1 spezifizierten Modells hin. Das hält uns aber nicht davon ab, die zentralen Charakteristika des Modells (also ohne Details bzw. Abhängigkeiten zu einer bestimmten Realisierung) in einer C#-Schnittstelle (interface) festzuhalten. Wir modellieren im Folgenden deshalb zunächst eine Schnittstelle IFloodFill:

public interface IFloodFill
{
    Dimension Size { set; }
    AlgorithmMode Mode { set; }

    event PixelChangedHandler PixelChanged;
    event StackSizeChangedHandler StackSizeChanged;

    void SetPolygon(List<Point> points);
    void SetStartPosition(Point p);
    void Start();
    void Stop();
    void Reset();
}

Die IFloodFill-Schnittstelle benötigt noch einige Deklarationen, die im Kontext einer C#-Schnittstelle nicht möglich sind (Delegate- und Aufzählungsdatentypen). Diese sind deshalb an einer zentralen Stelle zu definieren:

public enum PixelColor { Empty, Border, Filled, Start };
public enum AlgorithmMode { Recursive, Iterative };

public delegate void PixelChangedHandler(Point p, PixelColor c);
public delegate void StackSizeChangedHandler(int currentSize, int maximumSize);

In Listing 1 finden Sie nun eine Modell-Realisierung des Flood-Fill-Algorithmus vor:

001: public class FloodFillModelImpl : IFloodFill
002: {
003:     private const int SleepTime = 20;
004:     private const int StackSize = 1;
005: 
006:     private Dimension size;
007:     private Point start;
008:     private PixelColor[,] area;
009: 
010:     // stack size calculations
011:     private int currentStackSize;
012:     private int maximumStackSize;
013: 
014:     // threading utilities
015:     private Thread t;
016:     private bool isActive;
017:     private int pause;
018:     private AlgorithmMode mode;
019: 
020:     // polygon utilities
021:     private List<Point> polygon;
022: 
023:     public event PixelChangedHandler PixelChanged;
024:     public event StackSizeChangedHandler StackSizeChanged;
025: 
026:     public FloodFillModelImpl()
027:     {
028:         this.pause = SleepTime;
029:         this.area = new PixelColor[0, 0];
030:         this.polygon = new List<Point>();
031:     }
032: 
033:     // properties
034:     public Dimension Size
035:     {
036:         set
037:         {
038:             this.size = value;
039:             this.area = new PixelColor[value.Width, value.Height];
040:             this.EmptyArea();
041:         }
042:     }
043: 
044:     public AlgorithmMode Mode
045:     {
046:         set { this.mode = value; }
047:     }
048: 
049:     // public interface
050:     public void SetPolygon(List<Point> points)
051:     {
052:         for (int i = 0; i < points.Count; i++)
053:         {
054:             this.SetPixel(points[i], PixelColor.Border);
055:         }
056:     }
057: 
058:     public void SetStartPosition(Point p)
059:     {
060:         this.start = p;
061:         this.SetPixel(p, PixelColor.Start);
062:     }
063: 
064:     public void Start()
065:     {
066:         if (this.t != null)
067:             return;
068: 
069:         if (this.start.X < 0 || this.start.Y < 0)
070:             return;
071: 
072:         this.t = new Thread(new ThreadStart(this.FloodFill));
073:         this.isActive = true;
074:         this.t.Start();
075:     }
076: 
077:     public void Stop()
078:     {
079:         this.isActive = false;
080: 
081:         if (this.t != null)
082:             this.t = null;
083:     }
084: 
085:     public void Reset()
086:     {
087:         this.start = new Point() { X = -1, Y = -1 };
088:         this.EmptyArea();
089:         this.currentStackSize = 0;
090:     }
091: 
092:     // private helper methods
093:     private void FloodFill()
094:     {
095:         this.currentStackSize = 0;
096:         this.maximumStackSize = 0;
097: 
098:         if (this.mode == AlgorithmMode.Recursive)
099:             this.FloodFill_Recursive(this.start);
100:         else
101:             this.FloodFill_Iterative(this.start);
102: 
103:         // algorithm has finished
104:         this.isActive = false;
105:         this.t = null;
106:     }
107: 
108:     private void FloodFill_Recursive(Point point)
109:     {
110:         // increase stack
111:         this.currentStackSize += StackSize;
112:         if (this.currentStackSize > this.maximumStackSize)
113:             this.maximumStackSize = this.currentStackSize;
114: 
115:         if (this.StackSizeChanged != null)
116:             this.StackSizeChanged(this.currentStackSize, this.maximumStackSize);
117: 
118:         // premature end of algorithm
119:         if (!this.isActive)
120:         {
121:             // decrease stack
122:             this.currentStackSize -= StackSize;
123: 
124:             if (this.StackSizeChanged != null)
125:                 this.StackSizeChanged(this.currentStackSize, this.maximumStackSize);
126: 
127:             return;
128:         }
129: 
130:         if (this.area[point.X, point.Y] == PixelColor.Empty ||
131:             this.area[point.X, point.Y] == PixelColor.Start)
132:         {
133:             this.SetPixel(point, PixelColor.Filled);
134: 
135:             // animation delay
136:             Thread.Sleep(this.pause);
137: 
138:             this.FloodFill_Recursive (new Point() { X = point.X + 1, Y = point.Y });
139:             this.FloodFill_Recursive (new Point() { X = point.X - 1, Y = point.Y });
140:             this.FloodFill_Recursive (new Point() { X = point.X, Y = point.Y + 1 });
141:             this.FloodFill_Recursive (new Point() { X = point.X, Y = point.Y - 1 });
142:         }
143: 
144:         // animation delay
145:         Thread.Sleep(this.pause);
146: 
147:         // decrease stack
148:         this.currentStackSize -= StackSize;
149:         if (this.StackSizeChanged != null)
150:             this.StackSizeChanged(this.currentStackSize, this.maximumStackSize);
151:     }
152: 
153:     private void FloodFill_Iterative(Point point)
154:     {
155:         // increase stack
156:         this.currentStackSize += StackSize;
157:         if (this.currentStackSize > this.maximumStackSize)
158:             this.maximumStackSize = this.currentStackSize;
159: 
160:         if (this.StackSizeChanged != null)
161:             this.StackSizeChanged(this.currentStackSize, this.maximumStackSize);
162: 
163:         Stack<Point> stack = new Stack<Point>();
164:         stack.Push(point);
165: 
166:         while (stack.Count > 0)
167:         {
168:             // premature end of algorithm
169:             if (!this.isActive)
170:             {
171:                 // decrease stack
172:                 this.currentStackSize -= StackSize;
173: 
174:                 if (this.StackSizeChanged != null)
175:                     this.StackSizeChanged(this.currentStackSize, this.maximumStackSize);
176: 
177:                 return;
178:             }
179: 
180:             Point p = stack.Pop();
181: 
182:             if (this.area[p.X, p.Y] == PixelColor.Empty ||
183:                 this.area[p.X, p.Y] == PixelColor.Start)
184:             {
185:                 this.SetPixel(p, PixelColor.Filled);
186: 
187:                 // animation delay
188:                 Thread.Sleep(this.pause);
189: 
190:                 stack.Push(new Point() { X = p.X + 1, Y = p.Y });
191:                 stack.Push(new Point() { X = p.X - 1, Y = p.Y });
192:                 stack.Push(new Point() { X = p.X, Y = p.Y + 1 });
193:                 stack.Push(new Point() { X = p.X, Y = p.Y - 1 });
194:             }
195:         }
196: 
197:         // animation delay
198:         Thread.Sleep(this.pause);
199: 
200:         // decrease stack
201:         this.currentStackSize -= StackSize;
202:         if (this.StackSizeChanged != null)
203:             this.StackSizeChanged(this.currentStackSize, this.maximumStackSize);
204:     }
205: 
206:     private void SetPixel(Point p, PixelColor c)
207:     {
208:         if ((p.X < 0) || (p.X >= this.size.Width) ||
209:             (p.Y < 0) || (p.Y >= this.size.Height))
210:                 return;
211: 
212:         this.area[p.X, p.Y] = c;
213: 
214:         // fire event
215:         if (this.PixelChanged != null)
216:             this.PixelChanged(p, c);
217:     }
218: 
219:     private void EmptyArea()
220:     {
221:         for (int i = 0; i < this.size.Width; i++)
222:         {
223:             for (int j = 0; j < this.size.Height; j++)
224:             {
225:                 this.area[i, j] = PixelColor.Empty;
226:             }
227:         }
228:     }
229: }

Beispiel 1. Realisierung des Modells.


Die Anforderungen für eine rekursive als auch iterative Implementierung finden Sie beide in der Klasse FloodFillModelImpl aus Listing 1 umgesetzt vor. Mit Hilfe des Aufzählungstyps AlgorithmMode können Sie beim Aufruf der FloodFill-Methode einfach umschalten, die beiden Methoden FloodFill_Recursive (Zeilen 108 ff.) bzw. FloodFill_Iterative (Zeilen 153 ff.) führen dann die Arbeit durch. Auch haben wir bereits die Analyse des Speicherplatzverbrauchs mit integriert.

Weiter geht es mit der grafischen Visualisierung des Modells. Für das Malen vieler kleiner Rechtecke bietet sich am ehesten ein Canvas-Objekt an. Bei der öffentlichen Methode SetPixel muss man darauf achten, dass diese im Kontext eines beliebigen Threads aufrufbar sein sollte. Aus diesem Grund ist das Dispatcher-Objekt in die Realisierung mit einzubeziehen (Listing 2 und Listing 3):

01: <UserControl x:Class="FloodFillSimulation.FloodFillViewControl"
02:              xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
03:              xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
04:              xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006" 
05:              xmlns:d="http://schemas.microsoft.com/expression/blend/2008" 
06:              mc:Ignorable="d" 
07:              d:DesignHeight="300" d:DesignWidth="300">
08:     <GroupBox Header="View">
09:         <Canvas Name="BoundaryFillCanvas"
10:                 Background="White" x:FieldModifier="private"/>
11:     </GroupBox>
12: </UserControl>

Beispiel 2. Steuerelement FloodFillViewControl: Realisierung der Ansicht: XAML.


001: public partial class FloodFillViewControl : UserControl
002: {
003:     private Dimension size;
004:     private Point start;
005: 
006:     // c'tor
007:     public FloodFillViewControl()
008:     {
009:         this.InitializeComponent();
010: 
011:         this.start = new Point() { X = -1, Y = -1 };
012:         this.BoundaryFillCanvas.MouseDown +=
013:             new MouseButtonEventHandler(this.BoundaryFillCanvas_MouseDown);
014:     }
015: 
016:     // properties
017:     public Dimension Size
018:     {
019:         get
020:         {
021:             return this.size;
022:         }
023: 
024:         set
025:         {
026:             this.size = value;
027:         }
028:     }
029: 
030:     public Point Start
031:     {
032:         get
033:         {
034:             return this.start;
035:         }
036:     }
037: 
038:     // event handler
039:     private void BoundaryFillCanvas_MouseDown (Object sender, MouseButtonEventArgs e)
040:     {
041:         System.Windows.Point p = e.GetPosition(this.BoundaryFillCanvas);
042: 
043:         // clear old start point
044:         if (this.start.X != -1 && this.start.Y != -1)
045:             this.SetPixel(this.start, Colors.Red, Colors.White);
046: 
047:         // set and paint new start point
048:         this.start = new Point() { X = (int) ((p.X - 10) / 10), Y = (int) ((p.Y - 10) / 10) };
049:         this.SetPixel(this.start, Colors.Black, Colors.Black);
050:     }
051: 
052:     // public interface
053:     public void SetPixel(Point p, Color border, Color fill)
054:     {
055:         int index = (p.Y * this.size.Width) + p.X;
056: 
057:         if (this.BoundaryFillCanvas.Dispatcher.CheckAccess())
058:         {
059:             Rectangle rect = (Rectangle) this.BoundaryFillCanvas.Children[index];
060:             rect.Stroke = new SolidColorBrush(border);
061:             rect.Fill = new SolidColorBrush(fill);
062:         }
063:         else
064:         {
065:             this.BoundaryFillCanvas.Dispatcher.BeginInvoke((Action)(() =>
066:             {
067:                 Rectangle rect = (Rectangle) this.BoundaryFillCanvas.Children[index];
068:                 rect.Stroke = new SolidColorBrush(border);
069:                 rect.Fill = new SolidColorBrush(fill);
070:             }));
071:         }
072:     }
073: 
074:     public void PaintView()
075:     {
076:         this.BoundaryFillCanvas.Height = this.Size.Height * 10 + 20;
077:         this.BoundaryFillCanvas.Width = this.Size.Width * 10 + 20;
078: 
079:         // fill canvas row per row
080:         for (int row = 0; row < this.Size.Height; row++) 
081:         {
082:             for (int col = 0; col < this.Size.Width; col++)
083:             {
084:                 Rectangle rect = new Rectangle();
085:                 rect.Width = 9;
086:                 rect.Height = 9;
087:                 rect.Stroke = Brushes.Red;
088:                 rect.StrokeThickness = 1;
089: 
090:                 rect.SetValue(Canvas.LeftProperty, (double) (10 + col * 10));
091:                 rect.SetValue(Canvas.TopProperty, (double) (10 + row * 10));
092: 
093:                 this.BoundaryFillCanvas.Children.Add(rect);
094:             }
095:         }
096:     }
097: 
098:     public void ClearView()
099:     {
100:         this.start = new Point() { X = -1, Y = -1 };
101: 
102:         for (int i = 0; i < this.BoundaryFillCanvas.Children.Count; i++)
103:         {
104:             Rectangle rect = (Rectangle) this.BoundaryFillCanvas.Children[i];
105:             rect.Stroke = Brushes.Red;
106:             rect.Fill = Brushes.White;
107:         }
108:     }
109: }

Beispiel 3. Steuerelement FloodFillViewControl: Realisierung der Ansicht: Codebehind.


Bevor wir Modell und die Ansicht in einer Hauptanwendung integrieren können, fehlt uns noch das Toolbar-Steuerelement (Listing 4 und Listing 5):

01: <UserControl x:Class="FloodFillSimulation.FloodFillControllerControl"
02:              xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
03:              xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
04:              xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006" 
05:              xmlns:d="http://schemas.microsoft.com/expression/blend/2008" >
06:     <StackPanel Orientation="Vertical">
07: 
08:         <UniformGrid Rows="1" Columns="3">
09:             <Button
10:                 Name="ButtonStart" Margin="3"
11:                 Click="Button_Click" x:FieldModifier="private">Start</Button>
12:             <Button
13:                 Name="ButtonStop" Margin="3"
14:                 Click="Button_Click" x:FieldModifier="private">Stopp</Button>
15:             <Button
16:                 Name="ButtonReset"  Margin="3"
17:                 Click="Button_Click" x:FieldModifier="private">Reset</Button>
18:         </UniformGrid>
19: 
20:         <UniformGrid Rows="1" Columns="3">
21:             <Label Margin="3">Current Stack Size</Label>
22:             <TextBox Name="TextBoxCurrentStackSize"
23:                      Margin="3" x:FieldModifier="private"></TextBox>
24:             <RadioButton Name="RadioButtonRecursive"
25:                          Content="Recursive" Margin="6" GroupName="Modus"
26:                          x:FieldModifier="private"></RadioButton>
27:         </UniformGrid>
28: 
29:         <UniformGrid Rows="1" Columns="3">
30:             <Label Margin="3">Maximum Stack Size</Label>
31:             <TextBox Name="TextBoxMaximumStackSize"
32:                      Margin="3" x:FieldModifier="private"></TextBox>
33:             <RadioButton Name="RadioButtonIterative" Content="Iterative"
34:                          Margin="6" GroupName="Modus" IsChecked="True"
35:                          x:FieldModifier="private"></RadioButton>
36:         </UniformGrid>
37: 
38:     </StackPanel>
39: </UserControl>

Beispiel 4. Steuerelement FloodFillControllerControl: Realisierung des Toolbar-Steuerelements: XAML.


01: public enum ControllerAction { Start, Stop, Reset };
02: 
03: public delegate void ControllerActionsEventHandler(ControllerAction action);
04: 
05: public partial class FloodFillControllerControl : UserControl
06: {
07:     // events
08:     public event ControllerActionsEventHandler Action;
09: 
10:     // c'tor
11:     public FloodFillControllerControl()
12:     {
13:         this.InitializeComponent();
14:     }
15: 
16:     // event handler
17:     private void Button_Click(Object sender, RoutedEventArgs e)
18:     {
19:         if (sender == this.ButtonStart)
20:         {
21:             this.Action(ControllerAction.Start);
22:         }
23:         else if (sender == this.ButtonStop)
24:         {
25:             this.Action(ControllerAction.Stop);
26:         }
27:         else if (sender == this.ButtonReset)
28:         {
29:             this.TextBoxCurrentStackSize.Text = "";
30:             this.TextBoxMaximumStackSize.Text = "";
31:                 
32:             this.Action(ControllerAction.Reset);
33:         }
34:     }
35: 
36:     // public interface
37:     public bool IsRecursive
38:     {
39:         get
40:         {
41:             return this.RadioButtonRecursive.IsChecked == true;
42:         }
43:     }
44: 
45:     public void DisplayStacksize(int currentSize, int maximumSize)
46:     {
47:         if (this.TextBoxCurrentStackSize.Dispatcher.CheckAccess())
48:         {
49:             this.TextBoxCurrentStackSize.Text = currentSize.ToString();
50:             this.TextBoxMaximumStackSize.Text = maximumSize.ToString();
51:         }
52:         else
53:         {
54:             this.TextBoxCurrentStackSize.Dispatcher.BeginInvoke((Action)(() =>
55:             {
56:                 this.TextBoxCurrentStackSize.Text = currentSize.ToString();
57:                 this.TextBoxMaximumStackSize.Text = maximumSize.ToString();
58:             }));
59:         }
60:     }
61: }

Beispiel 5. Steuerelement FloodFillControllerControl: Realisierung des Toolbar-Steuerelements: Codebehind.


Damit kommen wir zum Abschluss der Musterlösung. Die Platzierung der beiden benutzerdefinierten Steuerelemente FloodFillViewControl und FloodFillControllerControl in XAML gestaltet sich mit dem XAML-Hilfsmitteln recht einfach:

01: <Window x:Class="FloodFillSimulation.MainWindow"
02:         xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
03:         xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
04:         xmlns:local="clr-namespace:FloodFillSimulation"
05:         Title="Flood-Fill Algorithmus" Height="500" Width="700">
06:     <DockPanel LastChildFill="True">
07:         <local:FloodFillControllerControl x:Name="controller"
08:             DockPanel.Dock="Top" x:FieldModifier="private">
09:         </local:FloodFillControllerControl>
10:         <local:FloodFillViewControl x:Name="view"
11:             x:FieldModifier="private" Background="LightGray">
12:         </local:FloodFillViewControl>
13:     </DockPanel>
14: </Window>

Beispiel 6. Das Hauptfenster der Anwendung: XAML.


Die Verschaltung der Ereignisse, die aus beiden Steuerelementen eintreffen könnnen, ist im Codebehind-Anteil zu leisten:

01: public partial class MainWindow : Window
02: {
03:     private IFloodFill model;
04: 
05:     public MainWindow()
06:     {
07:         this.InitializeComponent();
08:         this.Loaded += new RoutedEventHandler(MainWindow_Loaded);
09: 
10:         Dimension size = new Dimension() { Width = 50, Height = 40 };
11: 
12:         this.model = new FloodFillModelImpl();
13:         this.model.Mode = AlgorithmMode.Iterative;
14:         this.model.Size = size;
15:         this.model.PixelChanged += new PixelChangedHandler(this.OnModelPixelChanged);
16:         this.model.StackSizeChanged += new StackSizeChangedHandler(this.OnStackSizeChanged);
17: 
18:         this.view.Size = size;
19:         this.view.PaintView();
20: 
21:         this.controller.Action +=
22:             new ControllerActionsEventHandler(this.OnBoundaryFillControllerAction);
23:     }
24: 
25:     private void MainWindow_Loaded(Object sender, RoutedEventArgs e)
26:     {
27:         // defer painting of polygon after main window has been rendered
28:         this.model.SetPolygon(this.GetBoundaryList());
29:     }
30: 
31:     private void OnStackSizeChanged(int currentSize, int maximumSize)
32:     {
33:         this.controller.DisplayStacksize(currentSize, maximumSize);
34:     }
35: 
36:     private void OnModelPixelChanged(Point point, PixelColor pixelColor)
37:     {
38:         Color color = this.PixelColorToColor(pixelColor);
39:         this.view.SetPixel(point, Colors.Black, color);
40:     }
41: 
42:     private void OnBoundaryFillControllerAction(ControllerAction action)
43:     {
44:         if (action == ControllerAction.Start)
45:         {
46:             Point start = this.view.Start;
47: 
48:             this.model.Mode = (this.controller.IsRecursive) ?
49:                 AlgorithmMode.Recursive :
50:                 AlgorithmMode.Iterative;
51: 
52:             this.model.SetStartPosition(start);
53:             this.model.Start();
54:         }
55:         else if (action == ControllerAction.Stop)
56:         {
57:             this.model.Stop();
58:         }
59:         else if (action == ControllerAction.Reset)
60:         {
61:             this.model.Reset();
62:             this.view.ClearView();
63:             this.model.SetPolygon(this.GetBoundaryList());
64:         }
65:     }
66: 
67:     private Color PixelColorToColor(PixelColor pc)
68:     {
69:         Color color = Colors.Black;
70:         if (pc == PixelColor.Empty)
71:             color = Colors.Red;
72:         else if (pc == PixelColor.Border)
73:             color = Colors.Blue;
74:         else if (pc == PixelColor.Filled)
75:             color = Colors.Green;
76: 
77:         return color;
78:     }
79: 
80:     private List<Point> GetBoundaryList_Rectangle()
81:     {
82:         List<Point> points = new List<Point>();
83: 
84:         points.Add(new Point() { X = 24 - 10, Y = 4 });
85:         points.Add(new Point() { X = 23 - 10, Y = 5 });
86:         points.Add(new Point() { X = 22 - 10, Y = 6 });
87:         points.Add(new Point() { X = 21 - 10, Y = 7 });
88:         points.Add(new Point() { X = 20 - 10, Y = 8 });
89:         points.Add(new Point() { X = 19 - 10, Y = 9 });
90:         points.Add(new Point() { X = 18 - 10, Y = 10 });
91:         ...
92:         ...
93:         ...
94: 
95: 
96:         return points;
97:     }
98: }

Beispiel 7. Das Hauptfenster der Anwendung: Codebehind.