Алгоритм Floodfill занимает несколько секунд

Question

Я программирую очень основное приложение для рисования.

У моего приложения есть изображение, и когда я прикасаюсь в любом месте, это место заполняется цветом.

Я использую алгоритм заполнения заливки (http://en.wikipedia.org/wiki/Flood_fill), в частности второй подход Alternative implementations.

Я использую pixmap для обновления текстуры.

Это прекрасно работает на моем компьютере, проблема заключается в том, чтобы выполнить приложение на моем Android-телефоне (Motorola Moto G с разрешением 720p, Android 4.4), алгоритм занимает несколько секунд, и мне это не нравится, я хочу, чтобы это этот процесс занимает меньше времени. Таким образом, проблема заключается в том, что с высоким разрешением (или с большой порцией для заполнения) алгоритм занимает несколько секунд.

Одна вещь, которую я сделал, это проверить каждые 5 пикселей вместо 1 пикселя, но я хочу знать, есть ли другая оптимизация.

Я знаю, что есть приложение, которое делает это (например, https://play.google.com/store/apps/details?id=com.coloring.toddlers&hl=en). Кто-нибудь может сказать мне какие-нибудь советы?

Спасибо.

Редактировать: обновить вопрос с помощью некоторого кода (я удалил пустой метод из интерфейсов). Вероятно, есть неиспользуемые переменные. Это версия, которая проверяет каждый пиксель.

Мой алгоритм заливка

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); 
    } 

} 

Answer 1

Распространенная ошибка при выполнении таких вещей является то, что вы пытаетесь обновить экран растрового изображения, который замедляет процесс вниз много, потому что приложение пытается обновить экран. Решение этой проблемы - копирование экрана в растровое изображение, выполнение алгоритма заполнения на этом растровом изображении и копирование результата обратно на экран по завершении. Если вы предоставите некоторый код, мы можем проверить ваш подход.