java实现扫描线种子填充算法

扫描线种子填充算法是一种图形学算法，用于将一个封闭图形的内部区域填充为指定的颜色。下面是一份 Java 代码实现。

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Point;
import java.util.LinkedList;
import java.util.Queue;

import javax.swing.JFrame;
import javax.swing.JPanel;

public class ScanlineSeedFill extends JPanel {

    private static final long serialVersionUID = 1L;
    private static final int WIDTH = 500;
    private static final int HEIGHT = 500;
    private static final int SEED_X = 250;
    private static final int SEED_Y = 250;

    private int[][] pixels = new int[WIDTH][HEIGHT];
    private Queue<Point> queue = new LinkedList<>();

    public ScanlineSeedFill() {
        JFrame frame = new JFrame();
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setSize(WIDTH, HEIGHT);
        frame.add(this);
        frame.setVisible(true);

        // 初始化像素数组，将所有像素设为白色
        for (int i = 0; i < WIDTH; i++) {
            for (int j = 0; j < HEIGHT; j++) {
                pixels[i][j] = Color.WHITE.getRGB();
            }
        }

        // 将种子点入队，并设置为黑色
        queue.add(new Point(SEED_X, SEED_Y));
        pixels[SEED_X][SEED_Y] = Color.BLACK.getRGB();

        // 扫描线种子填充算法
        while (!queue.isEmpty()) {
            Point p = queue.remove();
            int x = p.x;
            int y = p.y;

            // 向上填充
            int i = x;
            int j = y - 1;
            while (j >= 0 && pixels[i][j] != Color.BLACK.getRGB()) {
                pixels[i][j] = Color.BLACK.getRGB();
                if (i > 0 && pixels[i - 1][j] != Color.BLACK.getRGB()) {
                    queue.add(new Point(i - 1, j));
                }
                if (i < WIDTH - 1 && pixels[i + 1][j] != Color.BLACK.getRGB()) {
                    queue.add(new Point(i + 1, j));
                }
                j--;
            }

            // 向下填充
            i = x;
            j = y + 1;
            while (j < HEIGHT && pixels[i][j] != Color.BLACK.getRGB()) {
                pixels[i][j] = Color.BLACK.getRGB();
                if (i > 0 && pixels[i - 1][j] != Color.BLACK.getRGB()) {
                    queue.add(new Point(i - 1, j));
                }
                if (i < WIDTH - 1 && pixels[i + 1][j] != Color.BLACK.getRGB()) {
                    queue.add(new Point(i + 1, j));
                }
                j++;
            }

            // 向左填充
            i = x - 1;
            j = y;
            while (i >= 0 && pixels[i][j] != Color.BLACK.getRGB()) {
                pixels[i][j] = Color.BLACK.getRGB();
                if (j > 0 && pixels[i][j - 1] != Color.BLACK.getRGB()) {
                    queue.add(new Point(i, j - 1));
                }
                if (j < HEIGHT - 1 && pixels[i][j + 1] != Color.BLACK.getRGB()) {
                    queue.add(new Point(i, j + 1));
                }
                i--;
            }

            // 向右填充
            i = x + 1;
            j = y;
            while (i < WIDTH && pixels[i][j] != Color.BLACK.getRGB()) {
                pixels[i][j] = Color.BLACK.getRGB();
                if (j > 0 && pixels[i][j - 1] != Color.BLACK.getRGB()) {
                    queue.add(new Point(i, j - 1));
                }
                if (j < HEIGHT - 1 && pixels[i][j + 1] != Color.BLACK.getRGB()) {
                    queue.add(new Point(i, j + 1));
                }
                i++;
            }

            // 刷新画面
            repaint();
        }
    }

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        for (int i = 0; i < WIDTH; i++) {
            for (int j = 0; j < HEIGHT; j++) {
                g.setColor(new Color(pixels[i][j]));
                g.drawLine(i, j, i, j);
            }
        }
    }

    public static void main(String[] args) {
        new ScanlineSeedFill();
    }
}

上述代码中，像素数组 `pixels` 表示所有像素的颜色，种子点 `(SEED_X, SEED_Y)` 表示填充的起点。将种子点入队后，不断执行以下操作：

1. 取出队首点 `(x, y)`；
2. 向上、下、左、右四个方向填充，直至遇到边界或已填充的像素；
3. 将新的像素点入队；
4. 重复执行步骤 1。

最终，所有与种子点相连的区域都将被填充为黑色。在每次填充后都刷新画面，可以看到填充的过程。