Füll-Werkzeug für Pixelprogramm

[Medium]

Da es hier ja um einen Bildeditor geht, nicht um Animationen bei denen jedes Frame etwas neu gefüllt werden muss, wird der triviale Ansatz locker reichen. Man sollte nur überlegen, ob man nicht lieber mit Scanline statt Pixels[] da dran geht (vorausgesetzt man arbeitet mit einem TBitmap, was hier glaube ich nichtmals der Fall ist).
Ohne die Zeilen-Optimierung muss man ggf. nur aufpassen, dass man ab gewissen Bildgrößen keinen Stacküberlauf bekommt. Da ginge im Zweifel als Lösung auch noch die iterative Variante mit selbst verwaltetem Stapel.

[Sir Rufo]

Wie wäre es denn mit dieser Funktion?

Delphi-Quellcode:

procedure FloodFill( Canvas : TCanvas; x, y : Integer; NewColor : TColor );
var
  LCurrentColor : TColor;
begin
  Canvas.Brush.Color := NewColor;
  Canvas.Brush.Style := bsSolid;
  LCurrentColor := Canvas.Pixels[x, y];
  Canvas.FloodFill( x, y, LCurrentColor, fsSurface );
end;

...
FloodFill( MyBitmap.Canvas, 23, 54, clRed );
...

TCanvas.FloodFill

[Bjoerk]

Die Rekursion kann man vergessen (bringt regelmäßig Stackoverflow).

BTW, wie würde denn ein Algorithmus für fsBorder aussehen?

fsSurface ist ja dieser:

Delphi-Quellcode:

procedure TFloodFill.FloodFill4(X, Y: integer);
var
  P: TPoint;
  Stack: TPointStack;
begin
  Stack := TPointStack.Create;
  try
    Stack.Push(Point(X, Y));
    while not Stack.Empty do
    begin
      P := Stack.Pop;
      if IsCurrentColor(P.X, P.Y) then // OldColor;
      begin
        FPixels[P.X, P.Y] := FBrushColor; // NewColor;
        Stack.Push(Point(P.X, P.Y + 1));
        Stack.Push(Point(P.X, P.Y - 1));
        Stack.Push(Point(P.X + 1, P.Y));
        Stack.Push(Point(P.X - 1, P.Y));
      end;
    end;
  finally
    Stack.Free;
  end;
end;

[Blup]

Gibt viele nette Sachen im Internet zu dem Thema mit Quellcode und Erklärung:
QuickFill-An-efficient-flood-fill-algorithm

[Medium]

Zitat von Bjoerk:

Die Rekursion kann man vergessen (bringt regelmäßig Stackoverflow).

So pauschal stimmt das einfach nicht. Fläche klein genug oder Stack groß genug, und schon ist alles gut. (Ja, mit einem eigenen Stack ist man fast immer besser beraten, aber dennoch ist die Aussage faktisch falsch.)

Zitat:

BTW, wie würde denn ein Algorithmus für fsBorder aussehen?

Ich vermute du meinst die Unterscheidung zwischen "fülle diese einfarbige Fläche" und "fülle alles was von einem Rand mit Farbe X umgeben ist". Dann wäre "fsBorder":

Delphi-Quellcode:

procedure TFloodFill.FloodFill4(X, Y: integer);
var
  P: TPoint;
  Stack: TPointStack;
begin
  Stack := TPointStack.Create;
  try
    Stack.Push(Point(X, Y));
    while not Stack.Empty do
    begin
      P := Stack.Pop;
      if not IsBorderColor(P.X, P.Y) then
      begin
        FPixels[P.X, P.Y] := FBrushColor;
        Stack.Push(Point(P.X, P.Y + 1));
        Stack.Push(Point(P.X, P.Y - 1));
        Stack.Push(Point(P.X + 1, P.Y));
        Stack.Push(Point(P.X - 1, P.Y));
      end;
    end;
  finally
    Stack.Free;
  end;
end;

[Popov]

Ich hab gestern meinen alten Labyrinth Code ausgepackt und die Entstehung visualisiert, da ich selbst sehen wollte was da vor sich geht. Es ist ja nicht das Fill Problem, aber ich denke es ist im Grunde ein ähnliches Problem, da sich auch bei Fill die Wege oft trennen. Dabei habe ich auch den Stack visualisiert (rote Punkte), und war letztendlich selbst überrascht, wie viele Werte es dann doch sind. Ist aber auch richtig, denn bei dem Drang nach vorne wird immer dann eine Position auf Stack gelegt, wenn es zu dem Zeitpunkt mehr als eine Möglichkeit gab. Einiges erledigt sich im Laufe der weiteren Berechnung, aber jede Punkt wird noch mal besucht und kontrolliert.

Das Beispiel zeigt eine verzögerte Berechnung eines Labyrinths und wo überall und wie viele Werte auf Stack gelegt wurde. Interessant zu sehen, falls man den Stack bei der Arbeit zusehen möchte.

[Bjoerk]

Ok. Logo. Thanx @ Medium. Bin allerdings schon der Auffassung, daß das hier der Klassiker für einen Stack ist? Hatte gestern Tests mit 200 x 200 Pixel Fläche durchgeführt. Kam bei jedem 3. Durchlauf ein Stackoverflow? Den Stack hochstellen hab ich noch nie gemacht?

[Furtbichler]

Zitat von Bjoerk:

Ok. Logo. Thanx @ Medium. Bin allerdings schon der Auffassung, daß das hier der Klassiker für einen Stack ist? Hatte gestern Tests mit 200 x 200 Pixel Fläche durchgeführt. Kam bei jedem 3. Durchlauf ein Stackoverflow? Den Stack hochstellen hab ich noch nie gemacht?

Dieses Schwachsinnsfüllen macht man ja auch nicht mit 200x200 pixeln, sondern mit so 10x10 und in der Schule/Uni um mal was über Stacks und Rekursion zu lernen.