View Full Version : zu Boundary Fill / Flood Span Algo.
Grüß euch
Bitte, bitte, brauch dringend eure Hilfe !!
Kann mir wer vielleicht erklären wie dieser Algorithmus genau funktioniert ? Ich kann mir beispielsweise nicht erklären, nach welchem Prinzip die Anfänge der "Spans" ausgewählt werden. (im Vorlesungsfolien-Beispiel mit "s1" usw. markiert)
Vielleicht hat ja wer schon ein ausgearbeitetes Prüfungsordner-Bsp.... ?
Danke, im Vorhinein
Chris
Hallo!
Ich stehe auch bei diesem Beispiel an (Angabe vom 02-06-21). Habs probiert im Kopf durchzugehen...doch ich habs nicht geschafft. Bin also auch für jede Hilfeleistung dankbar,
lG leadpen
Kuschelmaus
20-01-2003, 16:43
hab auch meine lösung amal im exel nachgestellt, hoff es stimmt so.
soweit is das verstanden hab, geht der algorithmus zuerst nach oben und füllt dort von links nach rechts alles auf. ist die obere zeile zwei- oder dreigeteilt, so entstehen zwei oder drei neue rekursionen, die von links nach rechts abgearbeitet werden.
gehts nach oben nimma weiter, geht er nach unten und macht dort das gleiche
mumpstar
20-01-2003, 18:02
@ kuschelmaus
hi,
ich habs zu erst auch so gehabt wie du..
ich hab mir dann nochmal das bsp auf den vorlesungsfolien angeschaut und bin dann zu einen etwas anderen ergebnis gekommen.
der algo. funktioniert ja so, nachdem du eine reihe gefüllt hast, du die benachbarten pixel-reihen (spans) oben und unten von dieser in den stack reinhaust (die untere pixel reihe zuerst in den stack). und dann füllt man die oberste pixel-reihe im stack wieder von links nach rechts... und dann gibt man wieder die benachbarten pixel-reihen in den stack, usw...
das geht halt so lang rekursiv weiter bis der stack wieder leer ist.
bei mir hats dann so augeschaut, dass der untere Teil a bisserl anders war. das letzte pixel (66) is unterm 4er. und darunter 65 und ganz unten 58 - 64
mfg... alex:)
Danke für deine Hilfe Kuschelmaus, ich glaub ich habs jetzt kapiert.
Kuschelmaus
21-01-2003, 19:20
@ mumpstar
danke für den hinweis, bins nochmal durchgangen, glaub jetzt stimmts ;)
vielleicht bin ich blind aber
wo sind denn die 49,50,51 hin?
Hätte die 1. Zeichnung eh nicht gestimmt?
Wieso gehört ab 41 nicht mehr in der "Mitte" sondern ist nach rechts gerutscht?
Geht ja von links nach recht oder?
Soda, hab das ganze mal gemacht und bin zu folgendem Ergebnis gekommen (ist sozusagen eine Mischung von beiden obigen Zeichnungen):
lG, leadpen
mumpstar
21-01-2003, 22:18
hi..
ja, ich habs auch so wie leadpen.
scheint zu stimmen :-)
ciao...
wieso geht 41-43 und 44-48 plötzlich von oben nach unten ???
Javanack
22-01-2003, 12:01
eine frage hätt ich da noch: bei dem beispiel von den folien (siehe anhang!) wurde zuerst s4 und dann s5 links davon gewählt. Im buch hingegen - seite 129 (c) - wurde zuerst s5 auf der linken seite in den stack gegeben und dann erst s6 auf der rechten seite, also genau umgekehrt wie in der vorlesung. wieso?
ich hoffe es ist halbwegs klar was ich meine.
In der Prüfungsangabe steht, wir sollen das Beispiel mit modifiziertem FloodFill machen, in der Vorlesung hatten wir den Span-FloodFill.... ist SpanFloodFill = BoundaryFill?
Als Überschrift des Beispiel steht ja BoundaryFill
@Kenny - das hängt mit dem Stack zusammen...
@12gauge: modifiziert heißt, das man gleich die ganze scan line füllt, und nicht nur die pixel rundum, glaub ich... ach, wem mach ich was vor, ich kann einfach nicht erklären! schau einfach mal auf seite 130 unten, da steht's
@all: seit ihr euch da sicher, das der flood fill von oben nach unten geht. ich glaube eher, das er von links nach rechts stacked, und nur wenn 2 stacks die selbe x-koordinate haben, spielt oben bzw. unten eine rolle.
an hand des bsp. wurde das heißen, dass ich bereits bei der 2ten linie nach unten gehen würde.
d.h. : 1234
5
6
789.....usw
hoffe jemand versteht was ich meine, ist zugegebener massen a wenig konfus.
alex
mumpstar
22-01-2003, 13:56
@ aleX
also, ich bin mir schon sicher, dass der algorithmus zuerst den oberen Teil füllt. es wird nur zuerst die untere reihe mit span s1 makiert, dass der als unterstes im stack liegt und somit als letztes bearbeitet wird..
also fangt man die spans in der anderen reihenfolge an zu makieren, in der man sie eigentlich dann füllt.. ich hoff das war jetzt klar ausgedrückt :-)
.
@all
ich glaub, der flood-fill algorithmus gehört einfach zur allgemeinen klasse der boundary-fill methoden und der modifizierte-flood-fill alg verwendet die spans und stacks.. anstatt nur normal rekursiv zu füllen
mfg...
O.K vergesst's des wos i oben g'sogt hob. die folien haben klarheit geschaffen!
haben sich die damen und herren auf eine lösung geeinigt? stimmt die vom leadpen?
ich hab das gleiche rausbekommen und wär an einer verifikation dieser lösung interessiert.
lg
Korrektur für die Lösung von Kuschelmaus:
In die Zeile 52-54 gehört 49-51
darunter dann 52-54, 55-57!
Sowohl die Lösungen von leadpen als auch von Kuschelmaus sind
dann richtig.
Der Unterschied: es kommt darauf an, welche Strategie man verfolgt.
leadpen *zeichnet* von links nach rechts, um das zu tun, muss
er die Werte am Stack von rechts nach links eintragen.
kuschelmaus trägt die *Werte* von links nach rechts ein, zeichnet damit
aber von rechts nach links.
Das ergibt den Unterschied von 46/41 bei kuschelmaus bzw. 41/44 bei leadpen.
Für die Prüfung ist beides ok, man muss nur in sich konsistent bleiben.
Liebe Grüße
-Markus
Javanack
24-01-2003, 14:20
was ist jetzt wirklich der unterschied zwischen 'span flood fill', wie er auf den folien beschrieben ist, und dem 'modifizierten flood fill algorithmus', den wir bei der prüfung anwenden mußten? seid ihr euch auch wirklich sicher, dass da ein unterschied ist?
Javanack
24-01-2003, 14:41
eine weitere frage noch (wurde glaub ich schon mal gestellt - blieb aber unbeantwortet): wieso wird 41-43 und 44-48 plötzlich von oben nach unten gefüllt? was habt ihr da im stack eingetragen?
Stell Dir vor, Du hast 41 gerade gefüllt. Jetzt stehst Du
dort, der Algorithmus will nach oben - geht aber nicht,
schon gefüllt. Also geht er nach unten!
Du kannst erst wieder was vom Stack nehmen, wenn Du
weder nach oben noch nach unten kannst.
Alles klar?
-Markus
Original geschrieben von Javanack
was ist jetzt wirklich der unterschied zwischen 'span flood fill', wie er auf den folien beschrieben ist, und dem 'modifizierten flood fill algorithmus', den wir bei der prüfung anwenden mußten? seid ihr euch auch wirklich sicher, dass da ein unterschied ist?
boundary fill algos sind alle algos, die von einem punkt aus eine fläche füllen, bis sie zu einer bestimmten grenze kommen (meist is das eine bestimmte farbe)
flood fill algos sind im prinzip das selbe, sie gehen auch von einem punkt aus und füllen so lange, bis sie an eine andere farbe stoßen (egal welche)
und der "modifizierte flood fill algorithmus", den wir machen sollen is der "span flood fill" aus den folien b.z.w. dem buch
am besten wird wohl sein, wenn wir dazuschreiben, wie unser stack gefüllt wird z.B. von unten nach oben und links nach rechts
@magic7
kuschelmaus schreibt zwar, wenn sie eine zeile nach unten geht, von links nach rechts in den stack... wenn sie eine zeile nach oben geht aber von rechts nach links... das kann nicht stimmen...
z.B. müsste 15 dann doch über 13 stehen, oder nicht?
vBulletin® v3.7.1, Copyright ©2000-2008, Jelsoft Enterprises Ltd.