Java无递归填充图形最优方案 解决递归填充性能与栈内存过高问题

原有代码问题根因 #

• 递归实现的深度优先搜索(DFS)在填充大面积连续区域时，递归深度等于区域像素总数，普通JVM栈默认只有几百KB到几MB，自然会栈溢出，必须扩容才能运行
• contains方法是遍历ArrayList查询，时间复杂度为O(n)，每判断一个坐标都要遍历所有已存储的像素，区域越大运行速度越慢

优化实现思路 #

1. 把递归DFS改成基于队列的广度优先搜索(BFS)，完全避免栈内存溢出问题
2. 新增布尔类型二维标记数组，用来记录坐标是否已经被访问过，查询时间复杂度降到O(1)，大幅提升运行效率
3. 一次性读取BufferedImage的全量像素数组，比逐点调用getRGB效率更高

优化后示例代码 #

import java.awt.image.BufferedImage;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class FloodFill {
    private int targetColor;
    private int width, height;
    private boolean[][] visited;
    private int[] pixels;
    // 四个方向偏移量，和你原有逻辑一致
    private final int[][] dirs = {{0,1}, {-1,0}, {0,-1}, {1,0}};

    public ArrayList<int[]> populateSection(int startX, int startY, BufferedImage image) {
        width = image.getWidth();
        height = image.getHeight();
        targetColor = image.getRGB(startX, startY);
        visited = new boolean[width][height];
        // 一次性读取所有像素
        pixels = image.getRGB(0, 0, width, height, null, 0, width);
        
        ArrayList<int[]> section = new ArrayList<>();
        Queue<int[]> queue = new LinkedList<>();

        // 起始点入队
        queue.add(new int[]{startX, startY});
        visited[startX][startY] = true;

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int x = curr[0], y = curr[1];
            section.add(curr);
            // 如果需要维护原有toBeColored列表，在这里添加移除逻辑即可

            // 遍历四个方向
            for (int[] dir : dirs) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                // 判断坐标合法、颜色匹配、未访问过
                if (nx >= 0 && nx < width && ny >=0 && ny < height 
                    && !visited[nx][ny] 
                    && pixels[ny * width + nx] == targetColor) {
                    visited[nx][ny] = true;
                    queue.add(new int[]{nx, ny});
                }
            }
        }
        return section;
    }
}

效果说明 #

优化后不需要调整JVM栈内存参数，填充1920*1080分辨率的满屏区域耗时在毫秒级，返回的坐标列表和你原有后续着色逻辑完全兼容。

效果参考 #

初始图像：

着色完成图像：

内容的提问来源于stack exchange，提问作者mario colombini