SZ 博客

忠于理想 忠于技术

0%

泛洪算法 Flood Fill

发表于 分类于 阅读次数：

泛洪算法 Flood Fill

简介

泛洪算法——Flood Fill，（也称为种子填充——Seed Fill）是一种算法，用于确定连接到多维数组中给定节点的区域。 它被用在油漆程序的“桶”填充工具中，用于填充具有不同颜色的连接的，颜色相似的区域，并且在诸如围棋（Go）和扫雷（Minesweeper）之类的游戏中用于确定哪些块被清除。泛洪算法的基本原理就是从一个像素点出发，以此向周边相同或相似的像素点扩充着色，直到周边无相同颜色的区块或到图像边界为止。

泛洪填充算法采用三个参数：起始节点（start node），目标颜色（target color）和替换颜色（replacement color）。 该算法查找阵列中通过目标颜色的路径连接到起始节点的所有节点，并将它们更改为替换颜色。 可以通过多种方式构建泛洪填充算法，但它们都明确地或隐式地使用队列或堆栈数据结构。

四邻域泛洪

四邻域泛洪即向种子点上下左右四个方向传播。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void floodFill4Stack(int x, int y, int newColor, int oldColor)
{
  if(newColor == oldColor) return; //avoid infinite loop
  emptyStack();
 
  // 定义四个方向 下上左右
  static const int dx[4] = {0, 1, 0, -1}; 
  static const int dy[4] = {-1, 0, 1, 0}; 
 
  if(!push(x, y)) return;
  while(pop(x, y))
  {
    screenBuffer[y][x] = newColor;
    for(int i = 0; i < 4; i++) {
      int nx = x + dx[i];
      int ny = y + dy[i];
      if(nx > 0 && nx < w && ny > 0 && ny < h && screenBuffer[ny][nx] == oldColor) {
        if(!push(nx, ny)) return;
      }
    }
  }
}

八邻域泛洪

八邻域算法是将一个像素点的上下左右，左上，左下，右上，右下都进行着色。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void floodFill8Stack(int x, int y, int newColor, int oldColor)
{
  if(newColor == oldColor) return; //avoid infinite loop
  emptyStack();
   // 定义了八个方向
  static const int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  static const int dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; 
 
  if(!push(x, y)) return;
  while(pop(x, y))
  {
    screenBuffer[y][x] = newColor;
    for(int i = 0; i < 8; i++) {
      int nx = x + dx[i];
      int ny = y + dy[i];
      if(nx > 0 && nx < w && ny > 0 && ny < h && screenBuffer[ny][nx] == oldColor) {
        if(!push(nx, ny)) return;
      }
    }
  }
}

描绘线算法(Scanline Fill)

利用填充线来加速算法， 它不是在堆栈上推动每个潜在的未来像素坐标，而是检查相邻线（前一个和下一个）以找到可能在未来通过中填充的相邻段， 线段的坐标（开始或结束）被推到堆栈上。 在大多数情况下，该扫描线算法至少比每像素算法快一个数量级(减少了大量的出栈入栈操作)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void floodFillScanline(int x, int y, int newColor, int oldColor){
if(newColor==oldColor) return;
if(screen[x][y]!=oldColor) return;
emptyStack();
int x1;
bool spanAbove, spanBelow;
if(!push(x,y)) return;
while(pop(x,y)){
    x1=x;
        //从上向下扫描 找到第一行
    while(x1>0&&screen[x1][y]==oldColor) x1--;
    x1++;
    spanAbove = spanBelow = 0;
    while(x1<w&&screen[x1][y]==oldColor){
        screen[x1][y]=newColor;
        if(!spanAbove&&y>0&&screen[x1][y-1]==oldColor){
            // 线段左侧元素入栈
                if(!push(x1,y-1)) return;
            spanAbove=1;
        }
        else if(spanAbove&&y>0&&screen[x1][y-1]!=oldColor){
                // 本行元素直接修改 减少了出战入站操作
            spanAbove=1;
        }
        if(!spanBelow&&y<h-1&&screen[x1][y+1]==oldColor){
            if(!push(x1,y+1)) return;
            spanBelow=1;
        }
        else if(spanBelow&&y<h-1&&screen[x1][y+1]!=oldColor){
            spanBelow=1;
        }
        x1++;
    }
}
}

案例

leet-code 733. 图像渲染这个题目描述有些抽象，不过本质是一个Flood Fill算法，leet-code 463. 岛屿的周长这个题不偷懒的话，需要一个标准的图像分割算法去解，发现多个种子点，种子点按边界生长。这里暂不过多介绍相见【TODO】

参考 & 引用

https://www.pianshen.com/article/172962944/