填充操作如何在涂料应用中起作用？

Question

所有绘画程序,无论它们多么简单或复杂,都带有填充工具.这基本上用另一种颜色替换封闭区域的颜色.我知道有不同的API可以做到这一点,但我对算法很感兴趣.实现此工具的有效算法是什么？

我能想到的一些事情很快就是:

1. 将图像转换为二进制图,其中要替换的颜色中的像素是1所有其他颜色0.
2. 在要更改的点周围找到一个闭合区域,使得内部的所有像素都为1,并且所有相邻像素都为0.

示例图像

Answer 1

许多实现都是作为递归征服和除法算法完成的.如果你快速谷歌"洪水填充算法",你会发现很多资源,包括关于该主题的优秀维基百科页面.

Answer 2

Flood Fill算法是最常用的算法.以下是我的旧大学教科书"Helen Baker的计算机图形学"第3版的直接版本:

void floodFill4 (int x, int y, int fillColor, int interiorColor)
{
  int color;

  /* Set current color to fillColor, then perform the following operations */
  getPixel(x, y, color);
  if (color == interiorColor) 
  {
    setPixel(x,y);  // Set color of pixel to fillColor.
    floodFill4(x + 1, y, fillColor, interiorColor);
    floodFill4(x - 1, y, fillColor, interiorColor);
    floodFill4(x, y + 1, fillColor, interiorColor);
    floodFill4(x, y - 1, fillColor, interiorColor);
  }
}

但是,对于大图像,由于每个像素的递归,上面可能会给出堆栈溢出错误.通常,此算法会被修改,以便在填充一行像素时使用迭代,然后递归填充上方和下方的行.正如@kasperjj所述,维基百科有一篇关于此的好文章.