title: Efficient 8-Connected Flood Fill
body: <p>I've been using Paul Heckbert's excellent seed fill algorithm (available <a href="ftp://ftp-graphics.stanford.edu/pub/Graphics/GraphicsGems/Gems/GGems.tar.Z" rel="nofollow">here</a> and in the book <a href="http://www.graphicsgems.org" rel="nofollow">Graphic Gems (1990)</a>).</p>
  
  <p>Convoluted as the algorithm may appear. It's well-conceived and it's fast! Unfortunately, it's only for 4-connected spaces.</p>
  
  <p>I am looking for a well-designed, fast algorithm for 8-connected spaces (leaks along the diagonal). Any ideas?</p>
  
  <p>Recursively visiting or repeatedly throwing every cell onto a stack will not be considered well-designed for the purposes of this question. Algorithms available in pseudocode are most appreciated (Heckbert's is available in both code and pseudocode).</p>
  
  <p>Thanks!</p>
  
  <p>Heckbert's algorithm is copied here for completeness:</p>
  
  <pre><code>/*
   * A Seed Fill Algorithm
   * by Paul Heckbert
   * from "Graphics Gems", Academic Press, 1990
   *
   * user provides pixelread() and pixelwrite() routines
   */
  
  /*
   * fill.c : simple seed fill program
   * Calls pixelread() to read pixels, pixelwrite() to write pixels.
   *
   * Paul Heckbert    13 Sept 1982, 28 Jan 1987
   */
  
  typedef struct {        /* window: a discrete 2-D rectangle */
      int x0, y0;         /* xmin and ymin */
      int x1, y1;         /* xmax and ymax (inclusive) */
  } Window;
  
  typedef int Pixel;      /* 1-channel frame buffer assumed */
  
  Pixel pixelread();
  
  typedef struct {short y, xl, xr, dy;} Segment;
  /*
   * Filled horizontal segment of scanline y for xl&lt;=x&lt;=xr.
   * Parent segment was on line y-dy.  dy=1 or -1
   */
  
  #define MAX 10000       /* max depth of stack */
  
  #define PUSH(Y, XL, XR, DY) /* push new segment on stack */ \
      if (sp&lt;stack+MAX &amp;&amp; Y+(DY)&gt;=win-&gt;y0 &amp;&amp; Y+(DY)&lt;=win-&gt;y1) \
      {sp-&gt;y = Y; sp-&gt;xl = XL; sp-&gt;xr = XR; sp-&gt;dy = DY; sp++;}
  
  #define POP(Y, XL, XR, DY)  /* pop segment off stack */ \
      {sp--; Y = sp-&gt;y+(DY = sp-&gt;dy); XL = sp-&gt;xl; XR = sp-&gt;xr;}
  
  /*
   * fill: set the pixel at (x,y) and all of its 4-connected neighbors
   * with the same pixel value to the new pixel value nv.
   * A 4-connected neighbor is a pixel above, below, left, or right of a pixel.
   */
  
  fill(x, y, win, nv)
  int x, y;   /* seed point */
  Window *win;    /* screen window */
  Pixel nv;   /* new pixel value */
  {
      int l, x1, x2, dy;
      Pixel ov;   /* old pixel value */
      Segment stack[MAX], *sp = stack;    /* stack of filled segments */
  
      ov = pixelread(x, y);       /* read pv at seed point */
      if (ov==nv || x&lt;win-&gt;x0 || x&gt;win-&gt;x1 || y&lt;win-&gt;y0 || y&gt;win-&gt;y1) return;
      PUSH(y, x, x, 1);           /* needed in some cases */
      PUSH(y+1, x, x, -1);        /* seed segment (popped 1st) */
  
      while (sp&gt;stack) {
      /* pop segment off stack and fill a neighboring scan line */
      POP(y, x1, x2, dy);
      /*
       * segment of scan line y-dy for x1&lt;=x&lt;=x2 was previously filled,
       * now explore adjacent pixels in scan line y
       */
      for (x=x1; x&gt;=win-&gt;x0 &amp;&amp; pixelread(x, y)==ov; x--)
          pixelwrite(x, y, nv);
      if (x&gt;=x1) goto skip;
      l = x+1;
      if (l&lt;x1) PUSH(y, l, x1-1, -dy);        /* leak on left? */
      x = x1+1;
      do {
          for (; x&lt;=win-&gt;x1 &amp;&amp; pixelread(x, y)==ov; x++)
          pixelwrite(x, y, nv);
          PUSH(y, l, x-1, dy);
          if (x&gt;x2+1) PUSH(y, x2+1, x-1, -dy);    /* leak on right? */
  skip:       for (x++; x&lt;=x2 &amp;&amp; pixelread(x, y)!=ov; x++);
          l = x;
      } while (x&lt;=x2);
      }
  }
  </code></pre>