在 Java 中填充形状的最佳方法（无递归）

Question

我有一个 BufferedImage，上面画了一些形状，我试图用随机颜色填充这些形状；我已经制作了一个递归方法来完成这项工作，它确实做到了，但是：

速度慢得令人痛苦
它需要大量堆栈内存（我不得不将其扩展到 1GB 以避免出现问题）

我听说总是可以避免递归，但我想不出更有效的方法，任何帮助将不胜感激

方法 returns 一个 int[] 的 ArrayList 代表我必须填充的所有像素（然后我逐个像素地为这些像素着色）它从一个尚未着色的随机点开始.

我希望得到类似于我们在 Microsoft Paint 上使用工具“填充”可以获得的结果

下面是查找一个部分中所有点的方法代码：

ArrayList<int[]> populatesSection(ArrayList<int[]> section, int[] is) {
  int[][] neighbors=new int[4][2];
  int i;

  neighbors[0][0]=is[0];
  neighbors[0][1]=is[1]+1;

  neighbors[1][0]=is[0]-1;
  neighbors[1][1]=is[1];

  neighbors[2][0]=is[0];
  neighbors[2][1]=is[1]-1;

  neighbors[3][0]=is[0]+1;
  neighbors[3][1]=is[1];


  toBeColored.remove(contains(toBeColored, is));
  section.add(is);
  

  for(i=0;i<neighbors.length;i++)
    if(isValid(neighbors[i]) && contains(toBeColored, neighbors[i])>=0 && contains(section, neighbors[i])<0)
      populatesSection(section, neighbors[i]);

  return section;
}

初始缓冲图像：

彩色缓冲图像：

Answer 1

这是我很久以前在网上找到的洪水填充方法：

import java.awt.*;
import java.awt.event.*;
import java.awt.image.*;
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import javax.imageio.ImageIO;
import javax.swing.*;

public class ImageUtil
{
    public static void floodFill(BufferedImage image, Point point, Color target, Color replacement)
    {
        int width = image.getWidth() - 1;
        int height = image.getHeight() - 1;
        int targetRGB = target.getRGB();
        int replacementRGB = replacement.getRGB();

        Queue<Point> queue = new LinkedList<Point>();
        queue.add( point );

        while (!queue.isEmpty())
        {
            Point p = queue.remove();
            int imageRGB = image.getRGB(p.x, p.y);
            Color imageColor = new Color(imageRGB);

            if (imageRGB != targetRGB) continue;

            //  Update the image and check surrounding pixels

            image.setRGB(p.x, p.y, replacementRGB);

            if (p.x > 0) queue.add( new Point(p.x - 1, p.y) );
            if (p.x < width) queue.add( new Point(p.x + 1, p.y) );
            if (p.y > 0) queue.add( new Point(p.x, p.y - 1) );
            if (p.y < height) queue.add( new Point(p.x, p.y + 1) );
        }
    }

    public static void main(String[] args)
        throws Exception
    {
        if (args.length != 1) {
            System.err.println("ERROR: Pass filename as argument.");
            return;
        }

        String fileName = args[0];

        BufferedImage image = ImageIO.read( new File( fileName ) );

        JLabel north = new JLabel( new ImageIcon( fileName ) );
        JLabel south = new JLabel( new ImageIcon( image ) );

        north.addMouseListener( new MouseAdapter()
        {
            @Override
            public void mousePressed(MouseEvent e)
            {
                try
                {
                    BufferedImage image = ImageIO.read( new File( fileName ) );
                    int rgb = image.getRGB(e.getX(), e.getY());
                    Color target = new Color( rgb );

                    floodFill(image, e.getPoint(), target, Color.ORANGE);

                    south.setIcon( new ImageIcon(image) );
                }
                catch (Exception e2) {}
            }
        });

        JLabel label = new JLabel("Click on above image for flood fill");

        JFrame frame = new JFrame();
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.add(north, BorderLayout.NORTH);
        frame.add(label);
        frame.add(south, BorderLayout.SOUTH);
        frame.pack();
        frame.setLocationRelativeTo( null );
        frame.setVisible( true );
    }
}

我会让你决定它是否更有效率。

Answer 2

您通常会使用 Queue 来实现泛光填充，每次在图像的光栅扫描期间检测到背景（在您的情况下为白色）像素时都会播种。

static int[] xd = {-1, 0, 1,  0};
static int[] yd = { 0, 1, 0, -1};

static BufferedImage colorImage(BufferedImage im, Color background, Color[] colors) throws Exception
{       
    im = ensureImageType(im, BufferedImage.TYPE_INT_ARGB);
    
    int width = im.getWidth();
    int height = im.getHeight();
    
    int[] pix = ((DataBufferInt)im.getRaster().getDataBuffer()).getData();
    
    Queue<Integer> q = new LinkedList<>();      
    for (int i = 0, r = 0; i < width * height; i++) 
    {
        if(pix[i] == background.getRGB())
        {
            q.add(i);
            pix[i] = colors[r++ % colors.length].getRGB();
            
            while(!q.isEmpty())
            {
                int pos = q.poll();
                int x = pos % width;
                int y = pos / width;
    
                for(int j = 0; j < 4; j++)
                {                       
                    int xn = x + xd[j];
                    if(xn >= 0 && xn < width)
                    {
                        int yn = y + yd[j];
                        if(yn >= 0 && yn < height)
                        {
                            int npos = yn * width + xn;
                            if(pix[npos] == background.getRGB())
                            {
                                q.add(npos);
                                pix[npos] = pix[i];
                            }
                        }
                    }
                }
            }
        }
    }

    return im;
}

有了帮手class：

static BufferedImage ensureImageType(BufferedImage im, int imageType)
{
    if (im.getType() != imageType)
    {
        BufferedImage nim = new BufferedImage(im.getWidth(), im.getHeight(), imageType);
        Graphics g = nim.getGraphics();
        g.drawImage(im, 0, 0, null);
        g.dispose();
        im = nim;
    }
    return im;
}

测试：

Color[] colors = {Color.BLUE, Color.RED, Color.GREEN, Color.ORANGE,                  
                  Color.PINK, Color.CYAN, Color.MAGENTA, Color.YELLOW};

BufferedImage im = ImageIO.read(new File("to4SE.png"));         
im = colorImage(im, Color.WHITE, colors);       
ImageIO.write(im, "png", new File("color.png"));

输出：

Answer 3

我借鉴了的flood方法，并将其增强为自动flood填充整个图像。
我还通过在 SwingWorker:

上执行它，从 EDT 中删除了与洪水相关的长计算

import java.awt.*;
import java.awt.image.BufferedImage;
import java.net.URL;
import java.util.*;
import javax.imageio.ImageIO;
import javax.swing.*;

public class FloodFill extends JPanel {

    private final BufferedImage image;
    private static final Color background = Color.WHITE;
    private final Random rnd = new Random();

    FloodFill(BufferedImage image) {
        this.image = image;
    }

    @Override
    public Dimension getPreferredSize() {
        return new Dimension(image.getWidth(), image.getHeight());
    }

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        g.drawImage(image, 0,0, this);
    }

    private void autoFloodFill(){
        //take long process off the EDT by delegating it to a worker
        new FloodFillWorker().execute();
    }

    private Optional<Point> findBackgrounPoint() {

        int backgroundRGB = background.getRGB();

        for (int x = 0; x < image.getWidth(); x++) {
            for (int y = 0; y < image.getHeight(); y++) {
                int imageRGB = image.getRGB(x, y);
                if(imageRGB == backgroundRGB)
                    return Optional.of(new Point(x, y));
            }
        }
        return Optional.empty();
    }

    private Color randomColor() {
        return new Color(rnd.nextInt(256), rnd.nextInt(256), rnd.nextInt(256));
    }

    class FloodFillWorker extends SwingWorker<Void, Void>{

        //todo set sleep to 0
        private final long SLEEP = 500; //used to slow sown for demo purposed.

        @Override
        protected Void doInBackground() throws Exception {

            Optional<Point> backgroundPoint = findBackgrounPoint();
            while(backgroundPoint.isPresent()){
                floodFill(backgroundPoint.get(), randomColor());
                SwingUtilities.invokeLater(()-> repaint());  //invoke repaint on EDT
                backgroundPoint = findBackgrounPoint(); //find next point
                Thread.sleep(SLEEP);
            }
            return null;
        }

        private void floodFill(Point point, Color replacement)  {

            int width = image.getWidth();
            int height = image.getHeight();
            int targetRGB = image.getRGB(point.x, point.y);
            int replacementRGB = replacement.getRGB();

            Queue<Point> queue = new LinkedList<>();
            queue.add( point );

            while (!queue.isEmpty()){

                Point p = queue.remove();

                int imageRGB = image.getRGB(p.x, p.y);
                if (imageRGB != targetRGB) { continue;  }

                //Update the image and check surrounding pixels
                image.setRGB(p.x, p.y, replacementRGB);

                if (p.x > 0) {
                    queue.add( new Point(p.x - 1, p.y) );
                }
                if (p.x +1 < width) {
                    queue.add( new Point(p.x + 1, p.y) );
                }
                if (p.y > 0) {
                    queue.add( new Point(p.x, p.y - 1) );
                }
                if (p.y +1 < height) {
                    queue.add( new Point(p.x, p.y + 1) );
                }
            }
        }
    }

    public static void main(String[] args)  throws Exception    {

        String imageAdress = "https://i.stack.imgur.com/to4SE.png";
        BufferedImage image = ImageIO.read(new URL(imageAdress));

        FloodFill ff = new FloodFill(image);

        JFrame frame = new JFrame();
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.add(ff);
        frame.pack();
        frame.setLocationRelativeTo( null );
        frame.setVisible( true );
        ff.autoFloodFill();
    }
}

一个放慢速度的演示：

运行这on line

在 Java 中填充形状的最佳方法（无递归）

Best way to fill shapes in Java (no recursion)

java

recursion

geometry

swing

fill