Stack Überlauf verhindern?

barana · Beiträge: 39

Hallo Leute,

ich habe eine rekursive Procedur geschriben, welche etwas ähnliches macht, wie das Farbfüllwerkzeug von Paint.
Naja im Grunde macht sie genau das Selbe, zählt aber zusätzlich noch die gefüllten Pixel.
Hier der Code.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

procedure realfill(x,y:integer;image:TCanvas) ;
begin
  Inc(PC) ; // PC = PixelCounter
  image.Pixels[x,y] := FF ; // FF = Füllfarbe

  if image.Pixels[x+1,y]=GF then // GF = Grundfarbe (Suchfarbe) 
    realfill(x+1,y,image);

  if image.Pixels[x,y+1]=GF then
    realfill(x,y+1,image);

  if image.Pixels[x-1,y]=GF then
    realfill(x-1,y,image);

  if image.Pixels[x,y-1]=GF then
    realfill(x,y-1,image);
end;

Funktioniert auch, aber wenn ich mal ein etwas größeres Bild nehme, oder mehrere Bereiche fülle, dann kommt es oft zum Stack Überlauf.

Ist es irgendiwe möglich, dass die Rekursionen nicht auf den Stapelspeicher gehen oder den Stapelspeicher sogar zu erhöhen?

Danke im Voraus

PS: Bitte keine Antworten wie "benutz die FloodFoll Funktion" oder ähnliches.

BenBE · Verfasst: Mo 02.04.07 21:51

Der Algorithmus an sich ist korrekt, jedoch bietet sich bei Dingen, wo die Rekursionstiefe sehr groß werden kann die Implementation einer Queue an. D.h. Du speicherst in einer Liste einfach alle Pixel, die Du noch abarbeiten musst und gehst diese Liste einfach der Reihe nach durch.

D.h. anstatt die Daten über noh zu füllende Pixel in zahllosen Prozeduraufrufen auf den Stack zu legen, kümmerst Du dich auf dem Heap (im Speicher deiner Anwendung) um deren Verwaltung.

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

barana · Beiträge: 39

BenBE hat folgendes geschrieben:

Der Algorithmus an sich ist korrekt, jedoch bietet sich bei Dingen, wo die Rekursionstiefe sehr groß werden kann die Implementation einer Queue an. D.h. Du speicherst in einer Liste einfach alle Pixel, die Du noch abarbeiten musst und gehst diese Liste einfach der Reihe nach durch.

Aber um herauszufinden welche Pixel zu bearbeiten sind, muss ich doch durch die Rekursion, oder nicht?
Oder habe ich dich falsch verstanden?

Vielleicht einen Quellcode als Beispiel, wenn es nicht allzu aufwendig ist?

Danke im Voraus

BenBE · Verfasst: Di 03.04.07 16:17

Als Beispiel nehmen wir einfach deinen Quelltext ;-)

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

procedure realfill(x,y:integer;image:TCanvas) ;
begin
  Inc(PC) ; // PC = PixelCounter
  image.Pixels[x,y] := FF ; // FF = Füllfarbe

  if image.Pixels[x+1,y]=GF then // GF = Grundfarbe (Suchfarbe) 
    realfill(x+1,y,image);

  if image.Pixels[x,y+1]=GF then
    realfill(x,y+1,image);

  if image.Pixels[x-1,y]=GF then
    realfill(x-1,y,image);

  if image.Pixels[x,y-1]=GF then
    realfill(x,y-1,image);
end;

Jedesmal wenn Du in die Rekursion gehst, tust Du das doch, um einen Pixel zu übergeben, der behandelt werden muss???

Also ... Merken wir uns doch einfach die Parameter, mit denen die Rekursion aufgerufen werden würde???

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:

procedure realfill(x,y:integer;image:TCanvas) ;
var
    Queue: TPointQueue;
    P: TPoint;
begin
  Queue := TPointQueue.Create;
  Queue.Add(Point(X,Y));

  While not Queue.Empty do 
  Begin
    P := Queue.GetAndRemove;

    Inc(PC) ; // PC = PixelCounter
    image.Pixels[P.x,P.y] := FF ; // FF = Füllfarbe

    if image.Pixels[P.x+1,P.y]=GF then // GF = Grundfarbe (Suchfarbe) 
      Queue.Add(Point(P.x+1,P.y,image));

    if image.Pixels[P.x,P.y+1]=GF then
      Queue.Add(Point(P.x,P.y+1,image));

    if image.Pixels[P.x-1,P.y]=GF then
      Queue.Add(Point(P.x-1,P.y,image));

    if image.Pixels[P.x,P.y-1]=GF then
      Queue.Add(Point(P.x,P.y-1,image));
  end;
end;

Siehe da??? Keine Rekursion mehr ;-)

Und die Lösung sieht FAST wie dein Original aus *g*

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

ub60 · Beiträge: 765 Erhaltene Danke: 130

Zitat:

Ist es irgendiwe möglich, ... den Stapelspeicher sogar zu erhöhen?

Findet man unter Projekt, Optionen, Linker

Bye!
ub60

BenBE · Verfasst: Di 03.04.07 22:32

ub60 hat folgendes geschrieben:

Zitat:

Ist es irgendiwe möglich, ... den Stapelspeicher sogar zu erhöhen?

Findet man unter Projekt, Optionen, Linker

Bye!
ub60

Beheb bitte die Ursache, nicht die Symptome ... Du ersparst Dir damit viel Ärger ...

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

ub60 · Beiträge: 765 Erhaltene Danke: 130

@BenBE:

<schmoll>Ich hab nur den zweiten Teil seiner Frage beantwortet. </schmoll>
Manchmal ist ein rekursiver Algorithmus so genial einfach, dass ich mit einer Vergrößerung des Stacks schon einen Überlauf verhindere.
Ansonsten gebe ich Dir natürlich uneingeschränkt ;-)

Recht.

Bye!
ub60

Horst_H · Verfasst: Mi 04.04.07 11:36

Hallo,

was mich dabei immer stört, das man eine Rekursionstiefe nahe der Anzahl der zu zeichnenden Punkte bekommmt.
Das aendert sich prinzipiell durch den Einsatz von Queue, auch wenn natürlich viel weniger Daten zwischengespeichert werden (Minimum ist ja zusätzlich die Rücksprungadresse, wenn man innerhalb von Realfill eine rekursive Procedure definiert, die image nicht mehr übergeben muss).

Gruß Horst

Einloggen, um Attachments anzusehen!

barana · Beiträge: 39

Danke für eure Antworten.

Mit der Queue klappt es sehr gut, obwohl ich es noch nicht ganz verstehe.
Hab sowas noch nie angewendet, aber ich arbeite mich da mal rein.
Ansonsten frag ich einfach wieder.

spider-b · Hält's aus hier Beiträge: 1

sorry wenn ich in diesem alten thema noch was poste aber ich habe mich gefragt, wo TPointQueue deklariert ist also welche unit ich zu uses hinzufügen muss, damit es klappt. delphi erkennt TPointQueue bei mir nicht...
mfg spider-b

BenBE · Verfasst: Di 28.10.08 16:51

TPointQueue in meinem Beispiel war eine Pseudo-Klasse, die "Punkte" speichert und sich wie eine Queue verhält ;-)

Siehe den Anhang realfill.zip, dort ist eine Implementation, die das von mir oben vorgestellte Prinzip umsetzt.

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme