Stack overflow bei Floodfill

Salim

Hi,
ich benutze den Borland C++ Builder 6. Ich programmiere gerade meinen eigenen "FloodFill". Klappt auch alles ganz gut. Nur wenn die zu füllende Fläche zu groß wird, kommt folgender Fehler: "Stack overflow".
Den Algorithmus kann sich jeder denken, ist halt rekursiv.

So ungefähr sieht der Code ganz grob aus:

FloodFill(X,Y)
{
  if(Pixel[X][Y] == OldColor)
    Pixel[X][Y] = NewColor;
  else if(Pixel[X][Y] == NewColor) return;

  FloodFill(X+1, Y);
  FloodFill(X-1, Y);
  FloodFill(X, Y+1);
  FloodFill(X, Y-1);
}

Wie kann ich den FloodFill Algorithmus ohne dieses Problem programmieren? Vielleicht geht das iterativ? Ich bin auf jeden fall bis jetzt nur auf diese rekursive form gekommen.

dankbar für jede Hilfe

Salim

akari

Hallo

ich denke, du solltest noch Abruchbedingungen für die Ränder des Bitmaps einfügen.

bis bald
akari

Ponto

Wenn du das so pixelweise rekursiv machst, kommt es sehr schnell zu einem Stacküberlauf. Ein nichtrekursiver Algorithmus sollte das Problem nicht haben.

Salim

@akari: ist schon klar, ich hab hier nur das wichtige reingeschrieben, um mein algorithmus ungefähr deutlich zu machen.

@Ponto: Das ist ja das Problem. Nur wie sieht so ein "nichtrekursiver Algorithmus" aus?

Ponto

Salim schrieb:

@akari: ist schon klar, ich hab hier nur das wichtige reingeschrieben, um mein algorithmus ungefähr deutlich zu machen.

@Ponto: Das ist ja das Problem. Nur wie sieht so ein "nichtrekursiver Algorithmus" aus?

Ich hab sowas noch nie gemacht. Aber eine Möglichkeit bestünde darin, die Punkte in eine Stackdatenstruktur zu stecken. Wenn dein Algorithmus einen Stack simuliert kann dieser viel größer werden, als der vorgegebene Wert.

Dann würde ich nicht pixelweise arbeiten. Ich würde mindestens eine ganze Linie auf einmal einfärben.

Salim

Ich hab sowas noch nie gemacht. Aber eine Möglichkeit bestünde darin, die Punkte in eine Stackdatenstruktur zu stecken. Wenn dein Algorithmus einen Stack simuliert kann dieser viel größer werden, als der vorgegebene Wert.
Dann würde ich nicht pixelweise arbeiten. Ich würde mindestens eine ganze Linie auf einmal einfärben.

Tut mir leid. Ich such schon jetzt die ganze Zeit in Google, finde aber leider nichts.
Wie kann ich das machen?

Salim

Ich hab endlich was gefunden:
http://www.student.kuleuven.ac.be/~m0216922/CG/floodfill.html
Ich habs noch nicht direkt ausprobiert, aber ich tus sobald ich dann wieder Zeit hab.
Wie groß sollte ich mein Stack bei FloodFillScanlineStack wählen?