🌱 种子填充算法

💡 种子填充算法原理

算法类型：

1. 四连通（4-Connected）填充

从当前点扩散到4个相邻点：
    ↑
  ← ● →   只考虑上下左右
    ↓

邻居：(x, y-1), (x, y+1), (x-1, y), (x+1, y)
            

2. 八连通（8-Connected）填充

从当前点扩散到8个相邻点：
  ↖ ↑ ↗
  ← ● →   包含对角线方向
  ↙ ↓ ↘

邻居：上述4个 + (x-1,y-1), (x+1,y-1), (x-1,y+1), (x+1,y+1)
            

实现方法：

方法1：递归实现（简单但可能栈溢出）

function floodFill(x, y, targetColor, fillColor) {
    // 越界检查
    if (x < 0 || y < 0 || x >= width || y >= height) return;
    
    // 检查是否需要填充
    if (getPixel(x, y) != targetColor) return;
    if (getPixel(x, y) == fillColor) return;
    
    // 填充当前像素
    setPixel(x, y, fillColor);
    
    // 递归填充邻居（4-连通）
    floodFill(x+1, y, targetColor, fillColor);
    floodFill(x-1, y, targetColor, fillColor);
    floodFill(x, y+1, targetColor, fillColor);
    floodFill(x, y-1, targetColor, fillColor);
}
            

方法2：栈/队列实现（推荐，避免栈溢出）

function floodFill(seedX, seedY, targetColor, fillColor) {
    const stack = [{x: seedX, y: seedY}];
    
    while (stack.length > 0) {
        const {x, y} = stack.pop();  // 或 shift() 用于队列
        
        // 检查并填充
        if (x < 0 || y < 0 || x >= width || y >= height) continue;
        if (getPixel(x, y) != targetColor) continue;
        if (getPixel(x, y) == fillColor) continue;
        
        setPixel(x, y, fillColor);
        
        // 将邻居加入栈
        stack.push({x: x+1, y: y});
        stack.push({x: x-1, y: y});
        stack.push({x: x, y: y+1});
        stack.push({x: x, y: y-1});
    }
}
            

应用场景：

• 图像编辑：Paint工具的"油漆桶"功能
• 游戏开发：地图区域标记、路径寻找
• 图像处理：区域分割、连通域标记
• 扫雷游戏：点击空白区域自动展开

优化技巧：

• 扫描线种子填充：以行为单位填充，效率更高
• 边界填充：已知边界颜色，遇到边界停止
• 泛洪填充：已知原始颜色，替换所有相同颜色

🎓 使用说明

1. 绘制边界：选择"绘制边界"模式，点击并拖动鼠标画出封闭区域
2. 选择种子点：切换到"选择种子"模式，在封闭区域内点击一个点
3. 选择算法：选择4-连通或8-连通填充方式
4. 开始填充：点击"开始填充"按钮，观看动画演示
5. 调整速度：使用滑块控制动画速度