Universelle Füllverfahren stützen sich auf die Nachbarschaft eines Pixels. Abbildung 4.1 zeigt zwei Varianten.
 im 4-way-stepping
|
im 8-way-stepping
|
Obacht:
Gebiete, die nur durch 8-way-stepping erreicht werden können, werden beim Füllen mit 4-way-stepping ``vergessen'', wird hingegen die Nachbarschaft über 8-way-stepping definiert, so ``läuft die Farbe aus''.
Bild 4.1 zeigt beide Effekte.
|
|
boolean get_pixel ( // liefert true, wenn Pixel p
Point p) // die Vordergrundfarbe hat
und
boolean range_ok ( // liefert false, wenn Pixel p
Point p) // ausserhalb des Bildbereichs
Der Nachteil der sehr ineffizienten Methode boundary_fill liegt darin, daß für jedes Pixel innerhalb der Begrenzungskurve(n) (mit Ausnahme der Randpixel des inneren Gebiets) der Algorithmus viermal aufgerufen wird. Dadurch werden die Pixel mehrfach auf dem Stapel abgelegt.
Eine Beschleunigung des Verfahrens läßt sich dadurch erreichen, daß auf dem Stapel jeweils Repräsentanten für noch zu füllende Zeilen abgelegt werden, d.h. nach dem Einfärben einer kompletten horizontalen Linie werden von den unmittelbar angrenzenden Zeilen solche Punkte auf den Stapel gelegt, die noch nicht gefüllt worden sind und die unmittelbar links von einer Begrenzung liegen.
/*************************************************************************************/
/* */
/* Fuellen einer durch Vordergrundfarbe umrandeten Flaeche */
/* */
/*************************************************************************************/
private void boundary_fill( // setzt alle Nicht-Vordergrund-Pixel
Point p) // beginnend bei Position p auf Vordergrund
{
if ( range_ok(p) && !get_pixel(p) ) { // falls p keine Vordergrundfarbe hat
set_pixel(p); // setze Vordergrundfarbe
boundary_fill( new Point(p.x+1, p.y )); // 4-way stepping
boundary_fill( new Point(p.x, p.y+1 ));
boundary_fill( new Point(p.x-1, p.y ));
boundary_fill( new Point(p.x, p.y-1 ));
}
}
/*************************************************************************************/
/* */
/* Leeren einer durch Vordergrundfarbe definierten Flaeche */
/* */
/*************************************************************************************/
private void boundary_empty( // setzt alle Vordergrund-Pixel beginnend
Point p) // bei Position p auf Hintergrundfarbe
{
if ( range_ok(p) && get_pixel(p) ) { // falls p Vordergrundfarbe hat
del_pixel(p); // setze Hintergrundfarbe
boundary_empty( new Point( p.x+1, p.y )); // 8-way-stepping
boundary_empty( new Point( p.x+1, p.y+1 ));
boundary_empty( new Point( p.x, p.y+1 ));
boundary_empty( new Point( p.x-1, p.y+1 ));
boundary_empty( new Point( p.x-1, p.y ));
boundary_empty( new Point( p.x-1, p.y-1 ));
boundary_empty( new Point( p.x, p.y-1 ));
boundary_empty( new Point( p.x+1, p.y-1 ));
}
}
|
/*****************************************************************************/
/* */
/* linienweises Fuellen einer durch Vordergrundfarbe umrandeten Flaeche */
/* */
/*****************************************************************************/
private void fillRowByRow(int x, int y, Graphics g) {
int lg; // nicht gesetzte Pixel ganz
int rg; // links/rechts in dieser Z.
Punkt hilf; // Hilfpunkt
int px = x; // lokale Kopie
while(!isPixelSet(x, y)) { // Solange Pixel ungesetzt
setPixelInBuf(x, y); // Pixel merken und setzen
hilf = new Punkt(x, y);
hilf.paint(g);
x--; // naechstes Pixel links
}
lg = x+1; // 1 zu weit gelaufen
x = px + 1; // da (px,y) schon gesetzt
while(!isPixelSet(x, y)) { // Solange Pixel ungesetzt
setPixelInBuf(x, y); // Pixel merken und setzen
hilf = new Punkt(x, y);
hilf.paint(g);
x++; // naechstes Pixel rechts
}
rg = x-1; // 1 zu weit gelaufen
for(int pos = rg; pos >= lg; pos--) { // von rechts nach links
if(!isPixelSet(pos, y - 1)) { // falls Pixel in Reihe ueber
// dieser nicht gesetzt:
fillRowByRow(pos,y-1, g); // Repraesentant! neuer Aufruf
}
if(!isPixelSet(pos, y + 1)) { // falls Pixel in Reihe unter
// dieser nicht gesetzt:
fillRowByRow(pos,y+1, g); // Repraesentant! neuer Aufruf
}
}
return;
}
|