计算机图形学种子选填

### 计算机图形学中的种子填充算法

#### 定义与基本概念
所谓种子填充，是指以待填充区域内的一点作为起点（即种子），基于该点向四周进行扩展，对满足特定条件的像素点进行颜色绘制。这种技术广泛应用于图像处理和计算机绘图领域[^2]。

#### 类型区分
从不同角度可以将种子填充算法分类：

- **按表示方法分**
- 边界表示法：仅当周围存在不属于目标区域的颜色时才停止填充；
- 内部标记法：直到遇到预先设定好的边界颜色为止继续填充。

- **按连接模式分**
- 四连通：只考虑上下左右四个方向相邻的像素；
- 八连通：除了上述四向外还包括对角线位置上的邻居节点。

#### 主要算法介绍

##### (1) 递归种子填充算法
这是一种最直观的方法，通过不断调用自身来访问并着色符合条件的新像素直至整个封闭空间被填满。然而由于频繁函数调用可能导致栈溢出风险，在实际应用中有一定局限性[^1]。

void floodFill(int x, int y, Color oldColor, Color newColor){
    if(getPixel(x,y)!=oldColor || getPixel(x,y)==newColor)return;
    
    setPixel(x,y,newColor);
    
    // 对于四联通情况下的递归调用
    floodFill(x+1,y,oldColor,newColor); 
    floodFill(x-1,y,oldColor,newColor); 
    floodFill(x,y+1,oldColor,newColor); 
    floodFill(x,y-1,oldColor,newColor);
}

##### (2) 改进后的边界种子填充算法
为了克服传统递归版本可能带来的性能瓶颈问题，此变种采用队列结构存储待处理坐标，从而有效避免了深层数组嵌套造成的效率低下现象。它同样适用于复杂形状内部空洞较多的情形下快速完成大面积上色操作。

##### (3) 扫描线种子填充算法
这种方法利用水平扫描线条带状遍历屏幕缓冲区内的每一个象素单元格，一旦发现属于指定范围内的未染色部分则立即启动局部扩散过程。相比前两者而言更加高效稳定，尤其适合处理大规模数据集以及实时渲染场景需求。