FloodFill Rekursiv

[Neutral General]

Hi,

Ich benötige für mein Vorhaben eine FloodFill Procedure. Dazu hab ich erst mal eine "normale" programmiert.
Aber irgendwie bekomm ich dauernd nen Stack-Overflow... Wodran liegt denn das? Ich hab bei Wikipedia geguckt ob die das anders machen aber Wikipedia machts exakt genauso!

Delphi-Quellcode:

procedure FloodFill(ACanvas: TCanvas; x,y: Integer; AColor: TColor; Border: TColor);
begin
  if (ACanvas.Pixels[x,y] <> Border) then
  begin
    ACanvas.Pixels[x,y] := AColor;
    FloodFill(ACanvas,x+1,y,AColor,Border);
    FloodFill(ACanvas,x-1,y,AColor,Border);
    FloodFill(ACanvas,x,y+1,AColor,Border);
    FloodFill(ACanvas,x,y-1,AColor,Border);
  end;
end;

Gruß
Neutral General

[nachti1505]

Nur ne Vermutung, aber du hast nicht wirklich ne vernünftige Endbedingung, ausser wenn ALLES eingefärbt ist.

Will sagen, checke wenigstens mal ob 0<X<maxX und 0<Y<maxY.....

[Neutral General]

Ja das hatte ich mir auch schon gedacht aber ich hab die Fläche jetzt so eingegrenzt das sie nicht am Ende des Canvas ist sondern in der Mitte. Also ist die Abbruchbedingung auf jeden Fall erfüllt.. Wenn ich nur eine Richtung Rekursiv ausführe dann gehts.. Bei mehreren gibts nen Stack overflow.

[Tormentor32]

Delphi-Quellcode:

procedure FloodFill(ACanvas: TCanvas; x,y: Integer; AColor: TColor; Border: TColor);
begin
  if (ACanvas.Pixels[x,y] <> Border) then
  begin
    ACanvas.Pixels[x,y] := AColor;
    // Überprüfe vorm Aufruf erst, ob der Pixel die Bordercolor hat! Dann ruft er FloodFill nur auf, wenn nötig!
    FloodFill(ACanvas,x+1,y,AColor,Border);
    FloodFill(ACanvas,x-1,y,AColor,Border);
    FloodFill(ACanvas,x,y+1,AColor,Border);
    FloodFill(ACanvas,x,y-1,AColor,Border);
  end;
end;

[nachti1505]

So ganz macht deinen Code auch kein Sinn --->

bspw. wird Pixel 10,10 bearbeitet --> ist ungleich Border und wird auf Color gesetzt --> rek. Aufruf auf alle umliegenden Pixel --> der umliegende Pixel ruft ja wieder das Feld 10,10 auf.... der Vergleich ergibt true, da Border und AColor bestimmt unterschiedlich sind --> endlosschleife

[Neutral General]

Ok thx. Also ich habs jetzt so abgeändert:

Delphi-Quellcode:

procedure FloodFill(ABmp: TBitmap; x,y: Integer; AColor: TColor; Border: TColor);
begin
  if    (ABmp.Canvas.Pixels[x,y] <> Border) and (ABmp.Canvas.Pixels[x,y] <> AColor)
    and (x <= ABmp.Width) and (x >= 0) and (y <= ABmp.Height) and (y >= 0)
  then
  begin
    ABmp.Canvas.Pixels[x,y] := AColor;
    FloodFill(ABmp,x,y+1,AColor,Border);
    FloodFill(ABmp,x,y-1,AColor,Border);
    FloodFill(ABmp,x+1,y,AColor,Border);
    FloodFill(ABmp,x-1,y,AColor,Border);
  end;
end;

Das klappt auch bei manchen flächen.. Aber bei Flächen die viel Bitmap-Rand enthalten gibts wieder en Stack-Overflow... -.-

Gruß
Neutral General

[dizzy]

Zitat:

Zitat von Neutral General

Delphi-Quellcode:

(x <= ABmp.Width) and (y <= ABmp.Height)

Ein Bitmap geht von x: 0..Width-1; y: 0..Height-1. Könnte evtl. die Ursache sein. Typisches off-by-one ;)

[Hawkeye219]

Hallo,

eine Frage: was spricht gegen die Verwendung von TCanvas.FloodFill?

Gruß Hawkeye

[Neutral General]

Zitat:

Zitat von dizzy

Zitat:

Zitat von Neutral General

Delphi-Quellcode:

(x <= ABmp.Width) and (y <= ABmp.Height)

Ein Bitmap geht von x: 0..Width-1; y: 0..Height-1. Könnte evtl. die Ursache sein. Typisches off-by-one ;)

Wie war das mit dem Wald den man vor lauter Bäumen nicht mehr sieht ? :mrgreen: :wall:

Danke :)

Gruß
Neutral General

[gammatester]

Zitat:

Zitat von dizzy

Zitat:

Zitat von Neutral General

Delphi-Quellcode:

(x <= ABmp.Width) and (y <= ABmp.Height)

Ein Bitmap geht von x: 0..Width-1; y: 0..Height-1. Könnte evtl. die Ursache sein. Typisches off-by-one ;)

Außerdem zuerst die Bereiche testen und dann die Farben, sonst könnte es, wenn's dumm läuft, statt des Stackfehlers einen Zugriffsfehler geben.

Gammatester

[Neutral General]

Hi,

Hätte nochmal ne Frage:
Ich fülle jetzt die Fläche mehrfarbig.. Also mit verschiedenen Helligkeiten der angegebenen Farbe. Und da funktioniert ja folgende Abbruchbedingung nicht mehr:

Delphi-Quellcode:

(ABmp.Canvas.Pixels[x,y] <> AColor)

Wie mach ich das denn?

Gruß
Neutral General

[Tormentor32]

Dann musst du dir die Pixel merken, an denen du schon warst!

[Neutral General]

grml das hatte ich mir fast gedacht das es nicht einfacher geht... Geht das ganze FloodFillen eigentlich auch schneller? Hab das Gefühl das das FloodFill von Windows um einiges schneller ist...

Gruß
Neutral General

[dizzy]

Wenn der Hintergrund einfarbig ist, und diese Farbe nicht in deinem Füllmuster vorkommt, prüfe auf Gleichheit mit der Referenzfarbe (Startpixel, der ja üblich auf dem Hintergrund liegt).
Wenn du nicht sicherstellen kannst, dass die Farbe nicht in der Füllung vor kommt, bleibt als ultimative Lösung noch, ein 2D Array aus Bools, mit den selben Ausmaßen wie dein Bitmap. Setze dort alles auf false wo der korespondierende Pixel im Bitmap deine Randfarbe ist, den Rest auf true. Dann setzte immer false, wenn du einen Punkt füllst. Dann kannst du in diesem Array nachsehen, ob du einen Pixel bereits bearbeitet hast, oder ob du am Rand bist.

\\Edith vermisst den roten Kasten, und ist zudem der Meinung, dass Canvas.Pixels[] der langsamst mögliche Zugriff auf Pixeldaten ist. Canvas.Scanline geht da schon ganz anders ab, und das dürfte den ärgsten Flaschenhals ausmachen bei dir.
Eine weitere Optimierung wäre noch möglich, indem du den 4 Folgeaufrufen mitteilst, welchen der 4 weiteren nicht mehr zu betrachten sind, da du ja daher kommst. Wenn man das einfach mit 0..3 durchnummeriert, kannst du mit einer einfachen case-Anweisung ein paar Vergleiche sparen. Aber Pixels ist ganz sicher der weiiiit größere Hammer.

[Neutral General]

Ja ich muss es schon mit einem Array machen... Der Hintergrund ist nämlich mehrfarbig. Aber wie siehts mit meiner zweiten Frage aus: Warum ist mein Floodfill langsamer als das von Canvas (auch einfarbig!) ? Kann ich meins irgendwie schneller machen?

[Neutral General]

...muss euch nochmal um Hilfe bitten bei der Sache:
Das ganze sieht jetzt so aus:

Delphi-Quellcode:

procedure FloodFill(ABmp: TBitmap; x,y: Integer; AColor: TColor; Border: TColor; var Map: TBoolmap);
var l,i: Integer;
    r,g,b: Byte;
    c: TColor;
begin
  if Length(Map) = 0 then
  begin
    SetLength(Map,Abmp.Height);
    for i:= 0 to ABmp.Height-1 do
      SetLength(Map[i],ABmp.Width);
  end;

  if Map[y,x] then
    exit;

  if    (ABmp.Canvas.Pixels[x,y] <> Border) and (x >= 0) and (x <= ABmp.Width-1)
    and (y <= ABmp.Height-1) and (y >= 0)
  then
  begin
    l := GetRValue(ABmp.Canvas.Pixels[x,y]);
    r:= cut(GetRValue(AColor)-(255-l));
    g:= cut(GetGValue(AColor)-(255-l));
    b:= cut(GetBValue(AColor)-(255-l));
    c := RGB(r,g,b);

    ABmp.Canvas.Pixels[x,y] := c;
    Map[y,x] := true;

    FloodFill(ABmp,x,y+1,AColor,Border,Map);
    FloodFill(ABmp,x,y-1,AColor,Border,Map);
    FloodFill(ABmp,x+1,y,AColor,Border,Map);
    FloodFill(ABmp,x-1,y,AColor,Border,Map);
  end;
end;

Seitdem ich das mehrfarbige Floodfill hab gibts en Stackoverflow. Dann hab ich halt das BooleanArray hinzugefügt aber es kommt immernoch ein Stack Overflow -.-

Wodran liegt das denn jetzt bitte ? -.-

Gruß
Neutral General

[dizzy]

Zuerst ein paar Anmerkungen zum Code, wo Dinge auftauchen, die ich für umständlich bzw. komisch gelöst halte:

1) In diesem Fall würde ich eine Nested-Function verwenden, um u.a. das mehrmalige Übergeben der Map zu umgehen. Das verhindert auch, dass die Map von aussen mitgegeben werden muss, was ja garkeinen Sinn ergibt, da sie rein interne Angelegenheit des Floodfills ist. Strukturell in etwa so:

Delphi-Quellcode:

procedure FloodFill(ABmp: TBitmap; x, y: Integer; AColor: TColor; Border: TColor);
var
  Map: TBoolmap;
  ix, iy: Integer;

  procedure DoPixel(ax, ay: Integer);
  begin
    if ({ax und ay im gültigen Bereich}) and not Map[ax, ay] then
    begin
      ABmp.Canvas.Pixels[ax, ay] := Zielfarbe;
      Map[ax, ay] := true;
      DoPixel(ax+1, ay  );
      DoPixel(ax  , ay+1);
      DoPixel(ax-1, ay  );
      DoPixel(ax  , ay-1);
    end;
  end;

begin
  // Bei SetLength gehen so viele Argumente wie dein Array Dimensionen hat ;)
  // Zudem ist es so "richtig herum", erst x dann y Koordinate. Bei dir ists vertauscht
  // und damit anders herum als bei Pixels. Unschön und fehlerträchtig.
  SetLength(Map, ABmp.Width, ABmp.Height);

  // Map initialisieren, und dabei gleich die Border abtragen. Erspart die zusätzliche
  // Abfrage auf diese für jedes Pixel nachher.
  for iy := 0 to ABmp.Heigt-1 do
    for ix := 0 to ABmp.Width-1 do
      if ABmp.Canvas.Pixels[ix, iy] = Border then
        Map[ix, iy] := true
      else
        Map[ix, iy] := false;

  // Eigentichen Fill starten
  DoPixel(x, y);
end;

So in etwa würd ich das vermutlich machen =)


2)

Delphi-Quellcode:

(x <= ABmp.Width-1) and (y <= ABmp.Height-1)

Naja, ich hab zwar geschrieben, dass es bis Width/Height-1 geht, aber performanter und lesbarer wäre es gewesen statt obigem folgendes zu machen:

Delphi-Quellcode:

(x < ABmp.Width) and (y < ABmp.Height)

Selber Effekt, ohne noch zusätzliche Arithmetik. Und wenn ich nicht irre, ist ein Vergleich auf echt kleiner oder größer sogar noch ne Picosekunde schneller als auf kleiner/größer-gleich :freak:


3) Dein Stack overflow ist im übrigen interessant! Ich hätte eher eine Bereichsverletzung, oder mindestens ne AV erwartet. Bei:

Delphi-Quellcode:

  if Map[y,x] then
    exit;

Greifst du auf Elemente zu, die evtl. garnicht mehr im Bereich sind. Ob x und y zwischen 0 und Width/Height sind, prüfst du erst später.



Gruss,
Fabian

[dizzy]

Nochmal zum Overflow:

Wie groß ist dein Bild, bzw. der zu füllende Bereich ca.? Diese Methode zum Füllen tendiert nämlich dazu, seeeehr tief in die Rekursion zu gehen. Die Erste "Füll-Ameise" läuft ja durch, bis sie in einer Sackgasse landet. Das kann im Optimalfall schon der gesamte Füllbereich sein! Je nach Größe, Form und Startpunkt wandern dann mehrere tausend Aufrufe aufm Stack.

Wenn das der Fall ist, und andere Quellen für den Overflow auszuschließen sind, gäbe es zwei Auswege:

1. Umsetzung in iteratives Vorgehen. Es wird angenommen, dass jede Rekursion in eine Iteration überführbar ist. Für den Umgekehrten Fall ist es bereits allgemein bewiesen, ob so rum mittlerweile auch weiss ich grad nicht.
   Da jeder Rekursionsschritt gleich 4 neue auslöst wird das allerdings vermute ich etwas aufwändiger was das Rahmenwerk an Zählern und Bedingungen angeht.
   
2. Festlegen einer maximalen Rekursionstiefe. DoPixel() würde einen Parameter mehr bekommen, einen Zähler der für jeden neuen Aufruf um je eins erhöht wird. In der Prozedur dann ab einer gewissen Tiefe nicht mehr weiter machen.
   Im Ergebnis können zwei Dinge passieren:
   1) Die Tiefe reicht aus, deine Form und Startpunkt waren glücklich gewählt, so dass die Fläche trotdem ganz erfasst wird.
   2) Die Füllung erhält Lücken.
   Im Fall 2 könntest du dann her gehen, und in der Map verbleibende Flecken suchen, und dort einen neuen Floodfill ansetzen, und das ganze so lange wiederholen, bis sich keine Flecken mehr finden. Dieses Verfahren wird jedoch auch etwas Aufwendiger, und sicherlich nicht weniger anspruchsvoll wie die Umsetzung in eine Iteration.

Es gibt noch einen 3. Ausweg, der aber extrem unschön ist, und nur Symptome bekämpft: In den Projektoptionen den Stack vergrößern. Auf den ersten Blick eine tolle Idee, weil einfach und super schnell gemacht, aber sehr unfeiner Stil und wenn jemand ein noch etwas größeres Bild nimmt, schon wieder im Eimer.


Zunächst gilt es aber alle anderen Fehlerquellen als "zu groß" auszuschließen. (Zumal das dann wirklich schon nen ganz schön großer Bereich sein müsste. So Fullscreen-Fill oder sowas :D)


Anmerkung: Witziger weise ist es was die Rekursionstiefe angeht besser für den Algo, wenn die zu füllende Form möglichst komplex ist, mit schön zerklüfteten Rändern. Ein ausgefranstes Tribal-Tatoo z.B. wäre prima :mrgreen:. Während ein einfaches Viereck z.B. schlimmstenfalls in einer einzigen Spirale gefüllt würde, was einer Rekursionstiefe von Breite*Höhe des Vierecks in Pixeln entspräche. (Je nach Wahl der Reihenfolge der zu untersuchenden Nachbarpixel, und dem Startpixel. Es kann auch etwas günstiger ausfallen.)

Alles in allem ist Floodfill recht interessant, und weit weniger trivial, als man zunächst annehmen möchte finde ich =). Man kann viel optimieren, verallgemeinern, rumdoktorn - herrlich!