Füllwerkzeug

LeGaN

Hallo,

also ich hab ein kleines Programm á la MS Paint programmiert. Doch bei dem Füllwerkzeug hab ich das Problem, da dass ich einen StackOverflowError erhalte. Liegt wohl daran, dass ich das mit einer Rekursion gelöst habe. Wenn die Fläche, die füllbar ist, klein genug ist, funktioniert das wunderbar.

Nun fällt mir nichts ein, wie ich dies in eine nicht-rekursieve Methode packe, so dass es keinen StackOverflowError gibt.

Hat jemand vielleicht eine Idee?

Ach ja, das läuft in einem Applet.

Hier die Methode:

class Fill
{
  public static final int LEFT   =500;
  public static final int RIGHT  =400;
  public static final int TOP    =300;
  public static final int BOTTOM =200;
  public static final int NOWHERE=100;

/* ... */

  private void paintAndProgress(int x, int y, int from)
  {
    // Wenn die Koordinaten außerhalb des Bildes liegen, gleich abbrechen
    if(x<0 || y<0 || x>=this.image.getWidth() || y>=this.image.getHeight())
      return;

    switch(from)
    {
      /* wird nur ein einzigesmal aufgerufen.
         von diesem Punkt aus, wird das Füllen begonnen */
      case NOWHERE:
        // die Farbe, des ausgewählten Pixels wird gespeichert
        this.refIntColor=this.image.getRGB(x, y);

        // die malfarbe wird gesetzt
        this.graphics.setColor(this.color);

        // Der Pixel wird gemalt
        this.graphics.fillRect(x, y, 1, 1);

        // Rekursiever methodenaufruf mit der Angabe, woher man kommt, ob von Links, Rechts usw.
        this.paintAndProgress(x-1, y, RIGHT);
        this.paintAndProgress(x, y-1, BOTTOM);
        this.paintAndProgress(x+1, y, LEFT);
        this.paintAndProgress(x, y+1, TOP);
        break;

      default:
        // Falls der Pixel die gleiche Farbe hat, wird...
        if(this.refIntColor==this.image.getRGB(x, y))
        {
          // ...der Pixel angemalt, und...
          this.graphics.fillRect(x, y, 1, 1);

          /* ..in alle Richtungen, außer in die, von der der Methodenaufruf kommt (links, rechts, oben || unten), wird
             die Methode wieder aufgerufen */

          if(from!=LEFT)
            this.paintAndProgress(x-1, y, RIGHT);

          if(from!=TOP)
            this.paintAndProgress(x, y-1, BOTTOM);

          if(from!=RIGHT)
            this.paintAndProgress(x+1, y, LEFT);

          if(from!=BOTTOM)
            this.paintAndProgress(x, y+1, TOP);
        }
    }
  }

/* ... */

}

Beste Grüße
Jan

Leg dir am Anfang doch einen Stack an und dann PseudoCode:

Stack stack = new Stack();
stack.push( ersterPixel );

while( !stack.empty() ) {
  if( ! pixel-im-bild( stack.top() ) ) { stack.pop(); continue; }

  füllePixel( stack.top() );
  stack.push( pixel-links );
  stack.push( pixel-rechts );
  stack.push( pixel-oben );
  stack.push( pixel-unten );

  stack.pop();
}

müsste ja funktionieren

LeGaN

Hi,

danke für deine Antwort. Ich habs ausprobiert und funktionieren tut das auch...solange die zu füllende Fläche nicht zu groß ist
Denn wenns zu viel ist, kommt das dabei raus: java.lang.OutOfMemoryError: Java heap space

Und die Größe des Bildes, bei dem ich das teste, liegt bei 50x50 pixeln.

Beste Grüße
Jan

Gregor

Hi.

Überleg Dir mal anhand einer kleinen Fläche, wie oft der Pixel unterhalb des Ausgangspixels durchlaufen wird. (Wie oft landet dieser Pixel auf dem Stack?) ...dann erkennst Du, dass der Algorithmus insgesamt nicht wirklich so funktioniert, wie Du Dir das vorstellst.

Google danach dann mal nach:

Connected Components labeling

Vielleicht kommst Du darüber eher an Dein Ziel.

LeGaN

Hallo Gregor,

danke für deinen Tipp, ich habe mal gegoogeld, aber das was ich gefunden habe, habe ich nicht verstanden

Ich habe mir das nochmal mim Stack angeschaut und hab jetzt mal ausgeschlossen, dass ein Pixel mehr als einmal auf dem Stack landet. Das Funktioniert auch wunderbar. Allerdings ist wohl das problem, wesegen der Heap voll läuft, ein anderes: Ich habe mir mal ausgeben lassen, die Stackgröße und den Pixel, den er bei jedem durchlauf bearbeitet. Manchmal, nciht immer, hängt der sich sozusagen auf, und wechelst immer zwischen zwei Pixeln hin und her und der Stack wird deshalb halt nie leer. Ich habe bis jetzt noch nicht den Bug gefunden, vielleicht sieht ihn ja jemand auf den "ersten Blick". hier der Code:

public class Fill
{
  /*...*/
  private boolean istImStack(Pixel p, Stack s)
  {
    for(int i=0; i<s.size(); ++i)
    {
      if(((Pixel)s.get(i)).equals(p))
        return true;
    }

    return false;
  }

  private boolean istImBild(Pixel p)
  {
    return !(p.getX()<0 || p.getY()<0 || p.getX()>=this.image.getWidth() || p.getY()>=this.image.getHeight());
  }

  private void paintAndProgress(Pixel first)
  {
    int x, y;
    Pixel p, t;

    this.refIntColor=this.image.getRGB(first.getX(), first.getY());
    this.graphics.setColor(this.color);

    this.stack=new Stack();
    this.stack.push(first);

    while(!this.stack.empty())
    {
      x=((Pixel)this.stack.peek()).getX();
      y=((Pixel)this.stack.peek()).getY();

      this.graphics.fillRect(x, y, 1, 1);

      t=(Pixel)this.stack.pop();

      /* Ein neuer Pixel wird nur dann darauf gelegt, wenn sich dieser
         weder im Stack befindet, der gleiche Pixel ist, wie der ursprüngliche,
         noch außerhalb des Bildes befindet und eben die entsprechende Farbe
         besitzt.
      */

      // Links
      p=new Pixel(x-1, y);
      if(!t.equals(p) && !this.istImStack(p, stack) && this.istImBild(p) && this.refIntColor==this.image.getRGB(p.getX(), p.getY()))
        this.stack.push(p);

      // Oben
      p=new Pixel(x, y-1);
      if(!t.equals(p) && !this.istImStack(p, stack) && this.istImBild(p) && this.refIntColor==this.image.getRGB(p.getX(), p.getY()))
        this.stack.push(p);

      // Rechts
      p=new Pixel(x+1, y);
      if(!t.equals(p) && !this.istImStack(p, stack) && this.istImBild(p) && this.refIntColor==this.image.getRGB(p.getX(), p.getY()))
        this.stack.push(p);

      // Unten
      p=new Pixel(x, y+1);
      if(!t.equals(p) && !this.istImStack(p, stack) && this.istImBild(p) && this.refIntColor==this.image.getRGB(p.getX(), p.getY()))
        this.stack.push(p);
    }
  }

  /*...*/
}

Kann jemand helfen?

Beste Grüße
Jan