How would scanline fill algorithm iterate the pixel positions on the following image in an optimised-CodePudding

Can anyone explain me how would scanline fill algorithm turn the blue positions into pink? I wanted to know how the iterations will change when an obstruction is observed. Take for example in the third row, the algorithm will easily consider positions 40 to 46 being part of the same group. But how and when will the algorithm iterate the positions 52 to 59?

If possible, please explain from left to right instead of top to bottom. Also mention an optimised method to iterate.

CodePudding user response：

Here is the simple code from wikipedia:

fn fill(x, y):
  if not Inside(x, y) then return
  let s = new empty stack or queue
  add (x, y) to s
  while s is not empty:
    Remove an (x, y) from s
    let lx = x
    while Inside(lx - 1, y):
      Set(lx - 1, y)
      lx = lx - 1
    while Inside(x, y):
      Set(x, y)
      x = x   1
    scan(lx, x - 1, y   1, s)
    scan(lx, x - 1, y - 1, s)

fn scan(lx, rx, y, s):
  let added = false
  for x in lx .. rx:
    if not Inside(x, y):
      added = false
    else if not added:
      Add (x, y) to s
      added = true

So "s" is a seed list, basically you put some random point (must be empty) to start off the algorithm.

while s is not empty:
    Remove an (x, y) from s

This is a basic loop where we are consuming seeds and when there are no seeds left in "s" then the algorithm is finished.

let lx = x
    while Inside(lx - 1, y):
      Set(lx - 1, y)
      lx = lx - 1
    while Inside(x, y):
      Set(x, y)
      x = x   1

This is keeping track of the current scan line where lx is the leftmost empty pixel and (x-1) is the rightmost empty pixel (note as this may be confusing, x will be incremented at least once no matter what since all seed points are assured to be inside points). The first loop steps to the left and decrements lx every time it finds an empty pixel. The second loop steps to the right and increments x every time it finds an empty pixel. You can set pixel by pixel as stated, but depending on your library (if drawing lines is cheaper than pixel by pixel editing) you can instead draw a line after passing both of these loops, extending the line between (lx,y) and (x-1,y).

scan(lx, x - 1, y   1, s)
    scan(lx, x - 1, y - 1, s)

This is the "re-seeding" step. Basically the above steps consume seeds, this is the step that produces new seeds based on the results of the seed that was just consumed. "y 1" and "y-1" are single pixel offsets above and below the line that was just drawn, while "lx" and "x-1" describe the line that was just computed this step.

fn scan(lx, rx, y, s):
  let added = false
  for x in lx .. rx:
    if not Inside(x, y):
      added = false
    else if not added:
      Add (x, y) to s
      added = true

All that is happening here is that any empty pixels on the scan line (remember this is above and below the last line checked based on arguments) is being added to the seed array to be later tested (this is not incrementing forward and backwards but exhaustively searching every point along the line). Keep in mind that s needs to be a byref argument here since you will be editing it.

One additional note: when I say "empty pixel" I mean two things (though they generally are handled the same in this aglo): 1 the pixel is not an edge point, 2 the pixel has not already be filled by the algo.

As can be seen in the graphic below, any seed can be pulled from the seed list in any order and the algo still functions properly.