Farbfüllalgorithmus

F34r0fTh3D4rk · Verfasst: Do 23.03.06 19:49

ich habe für meine facharbeit einen rekursiven füll algo geschrieben (backtracking:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

procedure TMainForm.afill(curcol, nextcol: Tcolor; px, py: integer);
begin
  if image1.canvas.pixels[px, py] = curcol then
  begin
    image1.canvas.pixels[px, py] := nextcol;
    afill(curcol, nextcol, px + 1, py);
    afill(curcol, nextcol, px - 1, py);
    afill(curcol, nextcol, px, py + 1);
    afill(curcol, nextcol, px, py - 1);
  end;
end;

weil dieser schnell zu stackoverflows führte habe ich ihn ein wenig optmiert:

markieren

Delphi-Quelltext

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

procedure TMainForm.afill(curcol, nextcol: Tcolor; px, py: integer; dir: tmydir);
begin
  if image1.canvas.pixels[px, py] = curcol then
  begin
    image1.canvas.pixels[px, py] := nextcol;
    if dir <> tmdleft then
      afill(curcol, nextcol, px + 1, py, tmdright);
    if dir <> tmdright then
      afill(curcol, nextcol, px - 1, py, tmdleft);
    if dir <> tmdup then
      afill(curcol, nextcol, px, py + 1, tmddown);
    if dir <> tmddown then
      afill(curcol, nextcol, px, py - 1, tmdup);
  end;
end;

jedoch kommt es bei etwas größeren flächen immernoch zu stack overflows, gibt es da eine technik oder einen trick, dies irgendwie zu umgehen (paint schafft riesige flächen) ?

Lossy eX · Beiträge: 1048 Erhaltene Danke: 4

Ja. Lass die Rekursion raus. Dsa Problem ist, dass du für jedes Pixel was zu deiner Fläche gehört jeweils einen Aufruf deiner Methode hast. Damit hast du bei größeren Flächen irgendwann 100000 Methoden auf dem Stack. Auf dem Stack liegen dann aber auch noch alle Daten die an diese Methode übergeben wurden. Das müssten in diesem Falle 20 Byte alleine an Parametern sein.

Abhelfen könntest du in dem du alles in ein Record packst und dieses als Const oder so übergibst. Damit würdest du die Stackgröße verkleinern. Aber das wäre nur eine Milderung der Sympthome. Bei noch größeren Flächen. Gleiches Problem.

Ich würde es mit einer WhileSchleife und einer Liste versuchen. Alle Pixel die du anpackst würde ich in die Liste werfen und im nächsten Durchgang von der Liste wieder entfernen. Also, dass du dir die Pixel nicht anhand der Rekursion merkst sondern in einer art Liste. Denke mal, dass es so etwas in der Art wie eine stackbasierte Liste sein müsste. Also das was sonst aufm Stack mit den Rekursionen gemacht hast machste dann selber.

PS: Das Pushen und Popen der Funktionsparameter vom und auf den Stack kann mitunter auch einiges an Zeit in Anspruch nehmen. Dadurch kann man mitunter durch das umstellen der Parameter schon knapp 10-15% an Zeit einsparen. Aber das macht sich nur bei sehr sehr vielen aufrufen bemerktbar und bei dir dürfte Pixels eh der Flaschenhals sein.

_________________
Nur die Menschheit ist arrogant genug, um zu glauben sie sei die einzige intelligente Lebensform im All. Wo nicht mal das nachhaltig bewiesen wurde.

Horst_H · Verfasst: Fr 24.03.06 11:40

Hallo,

es kann ja sein, dass Paint mit scanline arbeitet.
Das heisst es wird zeilenweise abgeklappert.
Einmalig durchzufuhren:
Du beginnst mit einem Punkt und gehst diese Zeile nach und rechts ab, um Start und Endpunkt zu finden und natuerlich die Farbe zuaendern.#
Rekursive Aufrufe:
Dann testest und aenderst Du die Zeile darueber und darunter, jeweils von Anfang bis Ende.
Zeile_darueber_testen:
Falls dort der Start Links vom vorherigen Start oder Ende rechts vom vorhergehendem Ende musst Du Zeile_darunter_testen in dem Bereich NeuStart..AltStart-1 und AltEnd+1..Neuend.
Fuer alle Abschnitte die entstehen eben Zeile_darueber_testen, mit den jeweiligen Start,EndPositionen.

Zeile_darunter testen ist analog dazu.

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:

AAAAAAAAAAAAAAAA
A.....A..A.....A
............A..A <- dieses sei die Startzeile z.B . durch X ersetzen 
..AAAAA....AA..A
..AA..A.....A..A
...A.......A...A
AAAAAAAAAAAAAAAA

Als Uebergabewerte sind also Zeile,StartPos,EndPos noetig.

Gruss Horst

F34r0fTh3D4rk · Verfasst: Fr 24.03.06 13:47

In einer Facharbeit zum Thema rekursive Algorithmik sollte das schon rekursiv gelöst werden, das Problem bei zeilenweise ist, dass eine zeile auch ziemlich lang sein kann.

Narses · Verfasst: Fr 24.03.06 14:02

Moin!

Schonmal gegoogled?

FLOODFILL ALGORITHM DELPHI

Abgesehen davon, wer schreibt hier eigentlich die Facharbeit, du oder wir... :gruebel:

cu
Narses

F34r0fTh3D4rk · Verfasst: Fr 24.03.06 14:03

klar hab ich gegooglet, aber nix gefunden, es ist eigentlich auch egal, dann lass ich das programm halt weg.

Kroko · Beiträge: 1284 W98 W2k WXP Turbo D

Wie wärs mit folgenden Verbesserungen:

markieren

Delphi-Quelltext

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

procedure TMainForm.afill(curcol, nextcol: Tcolor; px, py: integer; dir: tmydir);
  procedure _Fill (const Ax,Ay: Word; const ADir: TMyDir);
  begin
    if image1.canvas.pixels[Ax, Ay] = curcol then
    begin
      image1.canvas.pixels[Ax, Ay] := nextcol;
      if ADir <> tmdleft then
        _Fill(Ax + 1, Ay, tmdright);
      if ADir <> tmdright then
        _Fill(Ax - 1, Ay, tmdleft);
      if ADir <> tmdup then
        _Fill(Ax, Ay + 1, tmddown);
      if ADir <> tmddown then
        _Fill(Ax, Ay - 1, tmdup);
    end;
  end;
begin
  _Fill (Px,Py,Dir);
end;

sollte den Stack nur noch mit 3/5 belegen!

_________________
Die F1-Taste steht nicht unter Naturschutz und darf somit regelmäßig und oft benutzt werden! oder Wer lesen kann, ist klar im Vorteil!

Kroko · Beiträge: 1284 W98 W2k WXP Turbo D

Ich habe den Teil gerad emal geteset, Stacküberlauf tritt immer noch auf! Darauf hin habe ich die maximale STackgröße um ein Stelle vergrößert von $00100000 auf $01000000 und schon konnte ich eine ganze Form (1024x768) füllen!

_________________
Die F1-Taste steht nicht unter Naturschutz und darf somit regelmäßig und oft benutzt werden! oder Wer lesen kann, ist klar im Vorteil!

F34r0fTh3D4rk · Verfasst: Fr 24.03.06 15:43

wie hast du dir maximale stackgröße erhöht ?

bzw wäre es doch möglich das nacheinander in ne schlange zu reihen und diese dann abzuarbeiten, nur wie ?

Lossy eX · Beiträge: 1048 Erhaltene Danke: 4

F34r0fTh3D4rk hat folgendes geschrieben:

In einer Facharbeit zum Thema rekursive Algorithmik sollte das schon rekursiv gelöst werden, das Problem bei zeilenweise ist, dass eine zeile auch ziemlich lang sein kann.

Nenn mich kleinlich aber das wären wichtige Hintergrundinfos gewesen! Also, dass es unbedingt Rekursiv sein muss, weil es sich dabei um DEINE Facharbeit handelt.

Das mit der Stackgröße ist aber auch wieder nur eine Verschleierung des eigentlichen Problemes! Man hat nur lediglich den Platz etwas größer gemacht. Aber auch dieser könnte irgendwann zu Ende sein. Was bei solchen Größen zwar so schnell nicht passieren sollte. Ich persönlich finde die Lösung durch einen größeren Stack alles andere als Ptraktisch. Zu mindestens wenn es darum geht echte konzeptionelle Probleme zu lösen.

Wobei wir gerade beim Thema sind. Soll es unbedingt ein rekursiver Floodfill Algorithmuss sein? Ich denke mal nicht. Für mich persönlich ist diese Aufgabe unter gar keinen Umständen ein Fall für eine Rekursion und würde ich so etwas bekommen würde es von mir Punkte Abzug geben.

Verstehe das bitte nicht falsch aber ich denke du solltest dein Beispiel noch mal überarbeiten. Sifern du es selbst wählen kannst. Aber bei einer Facharbeit gehe ich mal davon aus. Wie wäre es denn klasschicherweise mit einem Baum etc. Das sind ideale Anwendungsgebiete für eine Rekursion.

PS: Kann auch mehr als nur motzen. Bei der Stacklösung würde es so aussehen, dass du das Startpixel auf den Stack (Liste mit Pointern auf Records die X, Y etc enthalten) packst und dann in einer Whileschleife so lange die Liste abarbeitest bis kein Element mehr vorhanden ist. Dabei nimmst du zu Begin der Schleife ein Element vom Stack und überprüfst es. Sollte es die Farbe sein packst du die umliegenden Pixel auf den Stack und färbst es ein. Sollte es das nicht sein verschwindet es vom Stack und im nächsten Durchlauf nimmst du dir das nächste Element.

_________________
Nur die Menschheit ist arrogant genug, um zu glauben sie sei die einzige intelligente Lebensform im All. Wo nicht mal das nachhaltig bewiesen wurde.

delfiphan · Beiträge: 2684 Erhaltene Danke: 32

Meine Variante (ist zwar nur Pseudo-Rekursiv):
Demo: TyFloodFill.exe
Sources: TyFloodFill_Sources.zip

Die Stacksize ist zwar bloss 1024 aber wenn du damit nen Stack-Overflow hinkriegst gibt's nen Preis ;D

F34r0fTh3D4rk · Verfasst: Fr 24.03.06 18:26

es ging bei dem beispiel um ein mögliches anwendungsbeispiel für backtracking, was theoretisch ja auch einwandfrei funktioniert, eben nur bei dem stack scheitert, weitere rekursive beispiele aus meiner facharbeit sind:

datei-suchalgorithmus (neuer aufruf bei ordner)
labyrinthsuche
hanoi
pythagoras baum
...

delfiphan · Beiträge: 2684 Erhaltene Danke: 32

Wenn es um Backtracking geht würde ich Prolog und Regular Expressions erwähnen. Prolog ist *die* Programmiersprache wo Backtracking zur Verwendung kommt; dort sieht man die Stärken von Backtracking sehr schön. Man kann beispielsweise formale Logikbeweise völlig automatisch erstellen lassen. Oder Rätzel lösen im Stil von "A sagt B und C lügen. B sagt A lügt, ... -- wer lügt nun wirklich?".

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme