FloodFill算法实现异常问题：基于《Graphics Gems 1》伪代码的JavaScript实现故障排查

首先，你的代码基于Graphics Gems的扫描线填充思路是对的，但几个细节逻辑错误导致了挂起或部分填充的问题，下面逐一拆解：

1. 图像边界越界判断错误 #

在向右扫描的循环里，你用了x <= that.w，但图像的x坐标范围是0 <= x < that.w（因为宽度是that.w，索引从0开始）。当x等于that.w时，访问img.data[4*(x + y*that.w)]会越界，这不仅可能导致颜色判断错误，还可能引发死循环或浏览器挂起。

2. Skip逻辑的判断条件颠倒 #

在向左扫描后，你判断if (x >= x1)就设置skip = true，这和原算法逻辑完全相反：

• 向左扫描结束后，x是第一个不满足inside条件的位置，如果x + 1 > x1，说明从x1开始向左没有可填充的区域，才需要跳过后续处理；而你当前的条件会在有可填充区域时错误触发skip，导致部分区域被跳过填充。

3. Do-While循环的终止条件错误 #

你的do { ... } while (x < x2);会漏掉x == x2的情况，导致右侧部分区域没有被检查和处理，最终出现填充不完整的问题，应该改为while (x <= x2)。

4. 栈元素压入时的参数错误 #

在处理中间间隔区域时，压入栈的[y, x2 + 1, x - 1, -dy]应该使用dy而不是-dy，原算法中这个栈元素是用来标记下一行需要检查的区域，方向应该保持一致。

修复后的完整代码 #

function inside(x, y) { 
  const q = 4 * (x + y * that.w); 
  const color = [img.data[q], img.data[q + 1], img.data[q + 2], img.data[q + 3]]; 
  return color[0] === toolColor[0] && color[1] === toolColor[1] && color[2] === toolColor[2]; 
}

function set(x, y) { 
  const q = 4 * (x + y * that.w); 
  img.data[q] = that.color.r; 
  img.data[q + 1] = that.color.g; 
  img.data[q + 2] = that.color.b; 
  img.data[q + 3] = that.color.a; 
}

function doFloodFill(x, y) { 
  let skip = false;
  let x1, x2, dy, start; 
  const s = []; 
  // 初始化栈：原位置的上下两行，方向分别为+1和-1
  s.push([y, x, x, 1]); 
  s.push([y + 1, x, x, -1]); 

  while (s.length > 0) { 
    const n = s.pop(); 
    y = n[0] + n[3]; // 修正：基准y加上方向dy得到当前处理行
    x1 = n[1]; 
    x2 = n[2]; 
    dy = n[3]; 

    x = x1; 
    // 向左扫描，直到边界或非目标颜色
    while (x >= 0 && inside(x, y)) { 
      set(x, y); 
      x--; 
    } 

    // 判断是否需要跳过：如果start > x1，说明当前行x1左侧没有可填充区域
    start = x + 1;
    skip = start > x1; 

    if (!skip) { 
      // 如果左侧有未处理的间隔，压入栈待处理
      if (start < x1) { 
        s.push([y, start, x1 - 1, -dy]); 
      } 
      x = x1 + 1; 
    } 

    do { 
      if (!skip) { 
        // 向右扫描，注意边界是x < that.w，避免越界
        while (x < that.w && inside(x, y)) { 
          set(x, y); 
          x++; 
        } 
        // 压入当前扫描到的有效区域，用于处理下一行
        s.push([y, start, x - 1, dy]); 
        // 如果当前扫描范围超过了x2，说明中间有间隔，压入间隔区域待处理
        if (x > x2 + 1) { 
          s.push([y, x2 + 1, x - 1, dy]); 
        } 
      } 

      x++; 
      // 跳过非目标颜色的区域
      while (x <= x2 && !inside(x, y)) { 
        x++; 
      } 

      skip = false; 
      start = x; 
    } while (x <= x2); // 修正：包含x=x2的情况
  } 
}

额外注意点 #

• 确保that.w是图像的实际宽度（像素数），如果是canvas元素，应该用canvas.width而不是CSS样式的宽度。
• 填充完成后，记得调用ctx.putImageData(img, 0, 0)将修改后的data绘制到画布上，否则看不到填充效果。

内容的提问来源于stack exchange，提问作者Krzysztof Papciak