Entwickler-Ecke
Multimedia / Grafik - Farbfüllalgorithmus
F34r0fTh3D4rk - Do 23.03.06 19:49
Titel: Farbfüllalgorithmus
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:
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 - Fr 24.03.06 10:55
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.
Horst_H - 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.
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 - 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 - Fr 24.03.06 14:02
Moin!
Schonmal gegoogled? ;)
FLOODFILL ALGORITHM DELPHI
Abgesehen davon, wer schreibt hier eigentlich die Facharbeit, du oder wir... :gruebel: :D
cu
Narses
F34r0fTh3D4rk - 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 - Fr 24.03.06 15:26
Wie wärs mit folgenden Verbesserungen:
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!
Kroko - Fr 24.03.06 15:41
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!
F34r0fTh3D4rk - 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 - Fr 24.03.06 17:35
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.
F34r0fTh3D4rk - 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 - Fr 24.03.06 23:40
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?".
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!