油漆应用中的填充操作是如何工作的？

Question

所有的绘画程序，无论它们是多么简单或复杂，都配备了填充工具。这基本上用另一种颜色替换封闭区域的颜色。我知道有不同的API来实现这个功能，但我对算法感兴趣。实现此工具的有效算法是什么？

我能够快速想到的几件事情是：

1. 将图像转换为二进制地图，其中要替换的颜色像素为1，所有其他颜色为0。 2. 找到围绕要更改的点的封闭区域，使得所有内部像素都为1，所有相邻像素都为0。 示例图像

- Szere Dyeri

---

@dbr：“neighbouring”？你们英国人说我们的语言有趣。:-) 不过标题确实更好！ - Adam Liss

Answer 1

许多实现都是使用递归分治算法完成的。如果您在Google上快速搜索“泛洪填充算法”，您将会发现很多资源，其中包括关于这个主题的优秀维基百科页面。

- kasperjj

---

哇，这些动画真是太棒了！我还记得在我的Amiga 500上用Deluxe Paint观看算法的时候。 - akuhn

@akuhn 或者在玩486上的炮击地球游戏时观看它。 - Cloud

Answer 2

洪水填充算法是最常用的算法。以下是我旧大学教材“使用OpenGL进行计算机图形学”（第三版）中的一个朴素版本：

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所述，维基百科有一篇关于这个的好文章。

- Cybis

---

因为提到了 Stack Overflow，所以被点赞了！ - Justin Bozonier

Answer 3

这些算法在计算机图形学原理与实践中有详细讨论。如果你想了解如何对线条进行光栅化、填充多边形、编写3D代码而不使用DirectX或OpenGL API，我强烈推荐这本书。当然，对于实际应用，你可能想使用现有的库，但如果你想了解这些库的工作原理，这是一本非常棒的读物。

- Mitch Haile

---

我引用的书籍《OpenGL计算机图形学》也是一本深入探讨2D和3D渲染背后理论的优秀书籍，写得非常好。它只使用OpenGL来展示一些算法和方程式的应用，但数学内容相当深奥。 - Cybis

Answer 4

一般想法被描述为泛洪填充算法，并且有各种修改。常见的是扫描线填充。参见相关问题如何使用基于扫描线的2D渲染引擎？

- mloskot

Answer 5

还可以阅读有关连通组件标记的内容。这是一种有效的方法，可以在仅访问每个像素两次的情况下找到连接的像素。

维基百科文章。

这样做的好处是像素值不必相同，或者描述像素连接的函数可以是其他东西，比如梯度。

- geometrikal

Answer 6

如果您想要一个时间效率高、不太关心内存效率的算法，可以按照以下方法实现：

1）保持一个布尔型的内存来记录哪些单元格已经被访问过：Vis[] 2）保持一个点的列表，这些点已经被访问过，但是尚未标记邻居：Busy[] 3）将它们都初始化为空

4）将起始点添加到Busy中

5）

while you have a point P in Busy:
{
    for each neighbour N of the point P for which Vis[N] is still false
    {
       if appropriate (not crossing the boundary of the fill region)
       {
           set Vis[N] to true
           update the colour of N in the bitmap
           add N to the end of Busy[]
       }
       remove P from Busy[]
    }
}

- Tim Lovell-Smith