光栅图形学(5)-Flood Fill 洪水填充算法

文章目录[x]
  1. 1:算法介绍
  2. 2:步骤
  3. 3:代码实现
  4. 4:缺点
  5. 5:参考

算法介绍


洪水填充算法属于区域填充算法的一种,与多边形扫描不同的是,洪水填充算法除了要知道多边形的边界以外,还需要多边形区域内的一点,即种子点,并且区域必须是连通的。其思想是先将种子点赋予指定的颜色,然后通过这个点扩散到整个区域。

洪水填充算法可以分为四连通和八连通

  • 四连通。每次往左,上,右,下四个方向扩散
  • 八连通,每次往左,左上,上,右上,右,右下,下,左下八个方向扩散

 

步骤


  1. 将种子点压入栈
  2. 如果栈非空
    1. 弹出栈顶像素
    2. 为此像素赋予颜色
    3. 如果该像素的左,上,右,下方向的像素颜色不等于未填色,则将其压入栈中

 

代码实现


此代码还可改进,仅为参考。

void FloodFill(int x, int y, Color& fillColor, Color& edgeColor)
{
    int offset1[] = { 1, -1, 0, 0 };
    int offset2[] = { 0, 0, 1, -1 };

    stack<Vector2>* pixelStack = new stack<Vector2>();
    pixelStack->push(Vector2(x, y));
    while (!pixelStack->empty())
    {
        Vector2 p = pixelStack->top();
        pixelStack->pop();
        RenderSystem::current->GetRasterizer()->DrawPixel(p.x, p.y, fillColor);
        for (int i = 0; i < 4; i++) 
        { 
            int px = p.x + offset1[i]; 
            int py = p.y + offset2[i]; 
            Color c = RenderSystem::current->GetRasterizer()->GetPixel(px, py);
            if (c != fillColor && c != edgeColor)
                pixelStack->push(Vector2(px, py));
        }
    }   
}

缺点

此算法需要出栈入栈,多次循环(递归),费时费内存,所以并不适用。可以考虑用扫描的方法将其改进。

参考


《计算机图形学基础教程(第二版)》孙家广、胡事民 2.3.2
区域填充算法和多边形填充的扫描线算法  -- 张建龙

点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像