In der Computergra\ufb01k sind Objekte, die durch Linien und Punkte abgegrenzt sind selten. Vielmehr bekommen die Fl\u00e4chen eine Farbe oder ein \u00dcberzug von einer Textur. Ein ausgef\u00fclltes Objekt kann durch zwei Techniken entstehen. Zun\u00e4chst einmal kann es sofort so konstruiert werden, dass es gef\u00fcllt erscheint, beispielsweise ergeben viele gleichf\u00f6rmige Linien ein Rechteck. Aber Objekte k\u00f6nnen nachtr\u00e4glich gef\u00fcllt werden. Dazu sind Begrenzungen n\u00f6tig. Ein einfacher Algorithmus, der sich auf die Informationen des Bildschirmspeichers verl\u00e4sst ist Seed-Fill. Die Idee von Seed-Fill ist einfach: Wir starten bei einem bekannten Punkt \u2014 dem Seed (zu deutsch Korn) \u2014 und geben dem Nachbarpixel die gleiche F\u00fcllfarbe, wenn dieser nicht die Begrenzungsfarbe besitzt. Der Algorithmus ist schnell rekursiv definiert. Wenn wir auf den Bildschirmspeicher zugreifen, so umschreiben wir dies mit einem Zugriff auf das Feld pixelArray. Und boundaryValue bezeichnet die begrenzende Farbe und fillValue die zu f\u00fcllende Farbe:<\/p>\n
void seedFill( int x, int y )\r\n{\r\n if ( ( pixelArray[x,y] != boundaryValue ) && ( pixelArray[x,y] != fillValue ) ) {\r\n setPixel( x, y, fillValue );\r\n seedFill( x+1, y );\r\n seedFill( x-1, y);\r\n seedFill( x+1, y+1 );\r\n seedFill( x-1, y-1 );\r\n }\r\n}<\/pre>\nDie rekursive Implementierung krankt an dem Problem, dass der interne Stack sehr schnell ansteigt. Auch besitzt diese Implementierung den Nachteil, dass f\u00fcr jeden zu setzenden Punkt immer der Bildschirmspeicher ausgelesen wird und mehrere gleiche Punkte auf den Stack kommen und zur\u00fcckgewiesen werden.<\/p>\n
Eine m\u00f6gliche Verbesserung erhalten wir dadurch, dass wir die direkten Rekursion eliminieren. Dadurch wird dieser Algorithmus aber nicht schneller, da das setzen eines Pixels vier Stack-Operationen nach sich zieht. Au\u00dferdem ist eine Implementierung wie die folgende schon deswegen nicht schneller, da bei der Stack-Implementierung der Objekt-Overhead mit sich gezogen wird. Daher dient folgender Algorithmus lediglich zur Anschauung, wie Flood-Fill mit einem Stack umgesetzt werden kann.<\/p>\n
void seedFill( int xSeed, int ySeed )\r\n{\r\n Stack s = new Stack();\r\n floodValue = pixelArray[xSeed, ySeed];\r\n s.push( xSeed );\r\n s.push( ySeed );\r\n while ( s.notEmpty() )\r\n {\r\n y = s.pop();\r\n x = s.pop();\r\n setPixel( x, y );\r\n if ( pixelArray[x+1, y] == floodValue ) {\r\n s.push( x+1 ); s.push( y );\r\n }\r\n if ( pixelArray[x-1, y] == floodValue ) {\r\n s.push( x-1 ); s.push( y );\r\n }\r\n if ( pixelArray[x, y+1] == floodValue ) {\r\n s.push( x ); s.push( y+1 );\r\n }\r\n if ( pixelArray[x, y-1] == floodValue ) {\r\n s.push( x ); s.push( y-1 );\r\n }\r\n}<\/pre>\n\u00dcberlegen wir, wodurch diese Implementierung ineffizient wird. Ein Grund haben wir schon erschlossen: jeder gesetzte Punkt wird mehrmals \u00fcberpr\u00fcft. Nehmen wir einen Punkt (x,y) heraus. Dann wird (x+1,y) auf den Stapel gesetzt aber mit diesen Koordinaten wird wiederum (x+1-1,y) \u00fcberpr\u00fcft. Eine verbesserte Variante vom Seed-Fill m\u00fcsste sich daher einfach die Richtung merken und daraufhin die R\u00fcckrichtung nicht mehr gehen. Anstelle der Methode seedFill(\u2026) treten nun vier Implementierungen an, f\u00fcr jede Richtung eine Funktion. Zur Demonstration sei seedFillLeft(\u2026) aufgef\u00fchrt.<\/p>\n
seedFillLeft( int x, int y )\r\n{\r\n if ( pixelArray[x, y] != boundaryValue ) {\r\n setPixel( x, y, fillValue );\r\n seedFillLeft( x+1, y );\r\n seedFillUp( x-1, y);\r\n seedFillDown( x+1, y+1 );\r\n}<\/pre>\nWollen wir noch schnellere F\u00fcllalgorithmen benutzen, so kommen wir mit diesem Ansatz nicht weiter. Mit einer modifizierten Version des Scan-Line-Algorithmus ist dies aber zu schaffen.<\/p>\n","protected":false},"excerpt":{"rendered":"
In der Computergra\ufb01k sind Objekte, die durch Linien und Punkte abgegrenzt sind selten. Vielmehr bekommen die Fl\u00e4chen eine Farbe oder ein \u00dcberzug von einer Textur. Ein ausgef\u00fclltes Objekt kann durch zwei Techniken entstehen. Zun\u00e4chst einmal kann es sofort so konstruiert werden, dass es gef\u00fcllt erscheint, beispielsweise ergeben viele gleichf\u00f6rmige Linien ein Rechteck. Aber Objekte k\u00f6nnen […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":"","_links_to":"","_links_to_target":""},"categories":[1],"tags":[],"class_list":["post-2426","post","type-post","status-publish","format-standard","hentry","category-allgemein"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/posts\/2426","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/comments?post=2426"}],"version-history":[{"count":3,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/posts\/2426\/revisions"}],"predecessor-version":[{"id":3101,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/posts\/2426\/revisions\/3101"}],"wp:attachment":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/media?parent=2426"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/categories?post=2426"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/tags?post=2426"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}