当前位置: 首页 > 知识库问答 >
问题:

洪水填充算法需要几秒钟

苗运珧
2023-03-14

我正在编写一个非常基本的油漆应用程序。

我的应用程序有一个图像,当我触摸任何地方时,这个地方会填充一种颜色。

我使用洪水填充算法(http://en.wikipedia.org/wiki/Flood_fill),特别是第二种替代实现方法。

我使用像素图来更新纹理。

这在我的电脑上运行得很好,问题是在我的android(分辨率为720p的摩托罗拉moto G,android 4.4)上执行应用程序时,算法需要几秒钟,我不喜欢这样,我希望这个过程花费更少的时间。因此,问题是,对于高分辨率(或要填充的部分很大)的算法需要几秒钟。

我做的一件事是每5个像素检查一次,而不是每1个像素检查一次,但我想知道是否还有其他优化。

我知道有这样做的应用程序(如https://play.google.com/store/apps/details?id=com.coloring.toddlers

谢谢。

编辑:用一些代码更新问题(我已经从接口中删除了空方法)。可能存在未使用的变量。这是检查每个像素的版本。

我的洪水填充算法

import com.badlogic.gdx.*;
import com.badlogic.gdx.assets.AssetManager;
import com.badlogic.gdx.graphics.Color;
import com.badlogic.gdx.graphics.GL20;
import com.badlogic.gdx.graphics.Pixmap;
import com.badlogic.gdx.graphics.Texture;
import com.badlogic.gdx.input.GestureDetector;
import com.badlogic.gdx.math.Vector2;
import com.badlogic.gdx.scenes.scene2d.Stage;
import es.angelluis..Actors.BackgroundActor;
import es.angelluis..Actors.ImageActor;
import es.angelluis..util.Pixel;

import java.util.ArrayList;

public class Images implements Screen, InputProcessor {

    private Stage stage;
    private ImageActor img = new ImageActor();
    private AssetManager manager;
    private Texture texture = null;

    public Images(){
        manager = new AssetManager();
        stage = new Stage();
        manager.load("dibujo1.png",Texture.class);
        stage.addActor(img);
        InputMultiplexer im = new InputMultiplexer();
        im.addProcessor(this);
        im.addProcessor(stage);
        Gdx.input.setInputProcessor(im);


    }

    @Override
    public void render(float delta) {
        Gdx.gl.glClear(GL20.GL_COLOR_BUFFER_BIT);
        if (manager.update()){
            if (!img.loaded){
                texture = manager.get("dibujo1.png", Texture.class);
                int x = (Gdx.graphics.getWidth()-texture.getWidth())/2;
                int y = (Gdx.graphics.getHeight()-texture.getHeight())/2;
                img.load(texture, x,y, texture.getWidth(), texture.getHeight());
                texture.getTextureData().prepare();
                pix = texture.getTextureData().consumePixmap();
            }
            stage.draw();
        }
    }

    @Override
    public boolean touchDown(int screenX, int screenY, int pointer, int button) {
        int colorSelected = Color.rgba8888(Color.RED);

        if (screenX < img.getX() || screenX > img.getX() + img.getWidth() || screenY < img.getY() || screenY > img.getY() + img.getHeight()){
            return false;
        }

        //Get Texture to update.
        Pixmap source = img.getPixmap();
        // Obtenemos las coordenadas locales a la textura.
        screenX = screenX - (int)img.getX();
        screenY = screenY - (int)img.getY();
        // Get Color.
        int colorInicial = source.getPixel(screenX, screenY);



        // If color is the same we will exit.
        if (colorInicial == colorSelected){
            return false;
        }

        ArrayList<Pixel> pixels = new ArrayList<Pixel>();
        int colorPixel = source.getPixel(screenX, screenY);

        if (colorPixel == colorInicial){
            // Store the initial pixel in pixels linked list.
            pixels.add(new Pixel(screenX, screenY));
            while(!pixels.isEmpty()){
                Pixel p = pixels.get(0);
                source.setColor(Color.RED);
                source.drawPixel(p.getX(), p.getY());
                pixels.remove(0);
                // Now get all pixel that I should be update in this y coords. So get west and east.
                ArrayList<Pixel> line = new ArrayList<Pixel>();
                int w = p.getX()-1;
                colorPixel = source.getPixel(w, p.getY());
                while (colorPixel == colorInicial && w != 0){
                    line.add(new Pixel(w, p.getY()));
                    w--;
                    colorPixel = source.getPixel(w, p.getY());
                }
                int e = p.getX() + 1;
                colorPixel = source.getPixel(e, p.getY());
                while (colorPixel == colorInicial && e != img.getWidth()){
                    line.add(new Pixel(e, p.getY()));
                    e++;
                    colorPixel = source.getPixel(e, p.getY());
                }

                // Draw the line that I store before.
                while (!line.isEmpty()){
                    Pixel linePixel = line.get(0);
                    line.remove(0);
                    source.setColor(Color.RED);
                    source.drawPixel(linePixel.getX(), linePixel.getY());

                    // I check  the north pixel and store it if they should be updated
                    colorPixel = source.getPixel(linePixel.getX(), linePixel.getY()+1);
                    if (colorPixel == colorInicial){

                        pixels.add(new Pixel(linePixel.getX(), linePixel.getY()+1));
                    }
                    // I check the south pixel and store it if they should be updated
                    colorPixel = source.getPixel(linePixel.getX(), linePixel.getY()-1);
                    if (colorPixel == colorInicial){
                        //System.out.println("Entramos en sur");

                        pixels.add(new Pixel(linePixel.getX(), linePixel.getY()-1));
                    }
                }
            }
        }
        img.setTexture(new Texture(source));
        return false;
    }
}

ImageActor

package es.angelluis..Actors;

import com.badlogic.gdx.Gdx;
import com.badlogic.gdx.graphics.Pixmap;
import com.badlogic.gdx.graphics.Texture;
import com.badlogic.gdx.graphics.g2d.Batch;
import com.badlogic.gdx.scenes.scene2d.Actor;

public class ImageActor extends Actor{

    private Texture img;
    public boolean loaded = false;
    private int x,y,width,height;

    public void load(Texture img, int x, int y, int width, int height){
        this.img = img;
        loaded = true;
        this.x = x;
        this.y = y;
        this.width = width;
        this.height = height;
    }

    public void setTexture(Texture img){
        this.img = img;
    }

    public Pixmap getPixmap(){
        if (!img.getTextureData().isPrepared()){
            img.getTextureData().prepare();
        }
        return img.getTextureData().consumePixmap();
    }

    public float getX() {
        return x;
    }

    public void setX(int x) {
        this.x = x;
    }

    public float getY() {
        return y;
    }

    public void setY(int y) {
        this.y = y;
    }

    public float getWidth() {
        return width;
    }

    public void setWidth(int width) {
        this.width = width;
    }

    public float getHeight() {
        return height;
    }

    public void setHeight(int height) {
        this.height = height;
    }

    @Override
    public void draw(Batch batch, float alpha){
        batch.draw(img, x, y, width, height);
    }

}

共有1个答案

邓卓
2023-03-14

执行此类操作时的一个常见错误是,您正在尝试更新屏幕位图,这会大大降低处理速度,因为应用程序正在尝试同时更新屏幕。此问题的解决方案是将屏幕复制到位图中,在该位图上执行填充算法,并在完成后将结果复制回屏幕。如果您提供一些代码,我们可以检查您的方法。

 类似资料:
  • 我正试图制作一个可以在C#中填充int数组的算法。基本上,作为MS Paint中的填充工具,我有一个颜色,如果我在数组中选择(x,y)坐标,它会用新的颜色替换所有初始颜色相同的邻居。 例如: 如果我把3放入(0,0),数组就变成: 所以我在递归中尝试了它,它确实有效,但不是一直有效。实际上,我有时会遇到“堆栈溢出”错误(似乎合适)。这是我的代码,如果你能告诉我哪里出了问题,那就太好了:) 谢了!

  • 本文向大家介绍洪水填充和边界填充算法之间的区别,包括了洪水填充和边界填充算法之间的区别的使用技巧和注意事项,需要的朋友参考一下 在这篇文章中,我们将了解洪水填充算法和边界填充算法之间的区别。它们是区域填充算法,可以根据随机像素是否具有该区域的原始颜色来区分它们。 洪水填充算法 它也被称为种子填充算法。 它针对多维数组计算连接到给定节点的面积。 它通过填充或重新着色内部包含特定颜色的特定区域并因此给

  • 我正在用Java开发一个小的绘图应用程序。我试图通过实现洪水填充算法来创建一个“bucket-fill”工具。 (不必是特定于Java的)。 谢谢。

  • 我试图构建一个函数floodfill(矩阵,x,y),到目前为止,我已经得到了这个: 你有办法引导我继续下去吗?试着在这里看洪水填充的例子,但他们似乎不适合我的情况。至少我无法将这些示例应用到我的代码中。洪水填充似乎不是这里受欢迎的主题...但是,再次,帮助将非常感谢!

  • 我正在编程一个简单的绘画应用程序使用Java。我试图使用洪水填充算法的递归实现作为我的“桶填充”工具。 我想知道是否有一种方法仍然使用递归与这个算法,而不得到这个错误。 如果没有,这个算法有哪些可能的非递归实现,我可以在我的程序中使用?

  • 做作业的时候,算法的实现洪流填满了。我正在为这个指南编写一个程序:http://en.wikipedia.org/wiki/flood_fill。我有一些问题: 指定函数中的参数替换任何字符的颜色是否正常,我不知道这些坐标最初是什么颜色? 算法正确吗?例如,我在维基百科中编写了它,但我的程序的结果如下: 我的代码: