6

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

我能很快想到的几件事是：

  1. 将图像转换为二进制图，其中要替换的颜色中的像素为1，所有其他颜色为0。
  2. 在要更改的点周围找到一个封闭区域，使里面的所有像素都为 1，所有相邻的像素都为 0。

示例图像

4

6 回答 6

10

许多实现是作为递归征服和划分算法完成的。如果您对“洪水填充算法”进行快速 google，您会发现大量资源，包括关于该主题的优秀 wikipedia 页面。

于 2008-11-08T02:15:04.570 回答
7

洪水填充算法是最常用的。以下是直接来自我的旧大学教科书“使用 OpenGL 的计算机图形学”的一个幼稚版本，作者是 Hearn 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 所说，维基百科对此有一篇很好的文章。

于 2008-11-08T04:15:46.807 回答
3

这些算法在计算机图形学：原理与实践中有详细讨论。如果你有兴趣了解如何在不使用 DirectX 或 OpenGL API 的情况下光栅化线条、填充多边形、编写 3d 代码，我强烈推荐这本书。当然，对于现实世界的应用程序，您可能希望使用现有的库，但如果您对这些库的工作方式感到好奇，那么这是一本很棒的读物。

于 2008-11-08T04:20:07.797 回答
1

如果您想要一个不太关心内存效率的高效算法，您可以通过以下方式实现：

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[]
    }
}
于 2008-11-08T02:18:20.630 回答
1

另请阅读有关连接组件标签的信息。这是一种查找连接像素的有效方法，同时只访问每个像素两次。

维基百科文章。

这样做的好处是像素值不一定必须相同，或者将像素描述为连接的函数可能不是原始值 - 也许是梯度。

于 2008-11-11T13:50:29.903 回答
1

一般思想被描述为洪水填充算法，并且对其进行了各种修改。一种常见的方法是扫描线填充。请参阅相关问题基于扫描线的 2d 渲染引擎如何工作？

于 2010-01-23T23:30:07.220 回答