扫描线填充算法将如何以优化的方式迭代以下图像上的像素位置？

Question

谁能解释一下扫描线填充算法如何将蓝色位置变成粉红色？我想知道当观察到障碍物时迭代将如何变化。以第三行为例，算法很容易将位置 40 到 46 视为同一组的一部分。但是算法将如何以及何时迭代位置 52 到 59？

如果可能，请从左到右而不是从上到下解释。还要提到一个优化的迭代方法。

Answer 1

这是来自维基百科的简单代码：

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

所以“s”是一个种子列表，基本上你放一些随机点（必须为空）来启动算法。

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

这是一个基本循环，我们正在消耗种子，当“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

这是跟踪当前扫描线，其中 lx 是最左边的空像素，(x-1) 是最右边的空像素（请注意，这可能会造成混淆，无论如何 x 都会至少递增一次因为所有种子点都保证在点内）。第一个循环向左步进，并在每次找到空像素时递减 lx。第二个循环向右移动并在每次找到空像素时递增 x。您可以按照说明逐个像素地设置，但取决于您的库（如果绘制线条比逐像素编辑便宜），您可以在通过这两个循环后绘制一条线，延长 (lx,y) 和 ( x-1,y).

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

这是“重新播种”步骤。基本上上面的步骤是消耗种子的，这是根据刚刚消耗的种子的结果产生新种子的步骤。 “y+1”和“y-1”是刚刚绘制的线上方和下方的单个像素偏移量，而“lx”和“x-1”描述了这一步刚刚计算的线。

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

这里发生的所有事情是扫描线上的任何空像素（记住这是根据参数检查的最后一行的上方和下方）被添加到种子数组以供稍后测试（这不是递增向前和向后但详尽地搜索沿线的每个点）。请记住，此处 s 必须是 byref 参数，因为您将对其进行编辑。

一个附加说明：当我说“空像素”时，我指的是两件事（尽管在这个 aglo 中它们通常被相同地处理）：1 像素不是边缘点，2 像素尚未被填充通过算法。

如下图所示，可以按任何顺序从种子列表中提取任何种子，并且算法仍然可以正常运行。

扫描线填充算法将如何以优化的方式迭代以下图像上的像素位置？

How would scanline fill algorithm iterate the pixel positions on the following image in an optimised way?

algorithm

math

graphics

image-processing

computer-vision