Алгоритмы заполнения потока

Снова выходные, и это значит, что я могу играть с моим хобби-проектом .

Я устал от создания тестовых уровней вручную, поэтому решил отдохнуть от разработки движка и поработать над редактором уровней:

Редактор уровней http://gfilter.net/junk/Editor.JPG

Я хотел бы реализовать алгоритм заливки в редакторе, который работал бы так же, как в программе рисования. У кого-нибудь есть указания на то, что техника будет работать хорошо для меня здесь?

Уровень - это просто двумерный массив, поэтому его можно считать действительно растровым.

Спасибо!

15.12.2008 00:52:20
7 ОТВЕТОВ
обратите внимание, что теоретически нет разницы между «занятым» пикселем и «занятым» тайлом
Steven A. Lowe 15.12.2008 01:02:36

Wikpedia приведены некоторые примеры псевдокода различных методов заливки их заливка статьи. Какой метод вы выберете, зависит от приложения.

Помните, что заполнение потока может быть легко пронизано (подобно быстрой сортировке).

5
15.12.2008 00:54:36

Справедливости ради, это должно быть довольно просто. Так как у вас в любом случае есть базовая структура тайла, алгоритм будет довольно простым:

Select Tile To Fill:    
Fill Till    
Check neighbouring Tiles - If Empty Then Fill    
Repeat, for all filled tiles.

Отказ от ответственности: Выше приведено очень простое описание. В Интернете есть много ссылок, которые объясняют это намного лучше, чем я.

2
15.12.2008 00:57:46

Мы должны были запрограммировать это для школы:

1: stuff the start pixel into a queue, note its color. note it as added.
2: begin picking a pixel off the queue. If it's similar to the start pixel:
   2: put all its neighbours into the queue
      for each added pixel, note it's added. if already noted for a pixel, don't 
      add it anymore.
   3: color it with the destination color.
3: nonempty => jump back to 2
4: empty => we are finished

В зависимости от того, делаем ли мы 8-соседний или 4-соседний, мы проверяем все 8 соседних пикселей или только пиксели влево / вправо или выше / ниже определенного пикселя. Вот код (используя ImageJ. Я удалил некоторый код, не относящийся к делу). Надеюсь, это имеет смысл, это Java. Просто задайте вопросы:

public class Uebung1_2 implements PlugInFilter, MouseListener {
    private ImageProcessor ip;
    boolean[] state;
    int[] pixels;
    Queue<Integer> nextPixels;
    int threshould;

    /**
     * adds one pixel to the next-pixel queue only if it's not
     * already added.
     */
    void addNextPixel(int p) {
        if(!state[p]) {
            nextPixels.add(p);
            state[p] = true;
        }
    }

    boolean pixelsSimilar(int color1, int color2) {
        int dr = Math.abs(((color1 >> 16) & 0xff) -
                          ((color2 >> 16) & 0xff));
        int dg = Math.abs(((color1 >>  8) & 0xff) -
                          ((color2 >>  8) & 0xff));
        int db = Math.abs(((color1 >>  0) & 0xff) -
                          ((color2 >>  0) & 0xff));
        return ((double)(dr + dg + db) / 3.0) <= threshould;
    }

    /**
     * actually does the hard work :)
     * @param x the x position from which to start filling
     * @param y the y position from which to start filling
     */
    private void doFill(int x, int y, boolean connect8) {
        // first, add the start pixel
        int width = ip.getWidth(),
            height = ip.getHeight();
        /* for 8bit, we just gonna take the median of rgb */
        Color colorC = ij.gui.Toolbar.getForegroundColor();
        int color = colorC.getRGB();
        int firstPixel = ip.get(x, y);

        // go on with the mainloop
        addNextPixel(y * width + x);
        while(!nextPixels.isEmpty()) {
            int nextPixel = nextPixels.remove();
            int pixel = pixels[nextPixel];
            if(pixelsSimilar(pixel, firstPixel)) {
                // yay it matches. put the neighbours.
                int xN = nextPixel % width,
                    yN = nextPixel / width;
                /* the three pixels above */
                if(yN - 1 >= 0) {
                    if(connect8) {
                        if(xN + 1 < width) { 
                            addNextPixel(nextPixel - width + 1);
                        }
                        if(xN - 1 >= 0) {
                            addNextPixel(nextPixel - width - 1);
                        }
                    }
                    addNextPixel(nextPixel - width);
                }

                /* pixels left and right from the current one */
                if(xN > 0) {
                    addNextPixel(nextPixel - 1);
                }
                if(xN + 1 < width) {
                    addNextPixel(nextPixel + 1);
                }

                /* three pixels below */
                if(yN + 1 < height) {
                    if(connect8) {
                        if(xN + 1 < width) { 
                            addNextPixel(nextPixel + width + 1);
                        }
                        if(xN - 1 >= 0) {
                            addNextPixel(nextPixel + width - 1);
                        }
                    }
                    addNextPixel(nextPixel + width);
                }

                /* color it finally */
                pixels[nextPixel] = color;
            }
        }
    }

    @Override
    public void run(ImageProcessor ip) {
        ij.WindowManager.getCurrentImage().getCanvas().addMouseListener(this);
        this.ip = ip;
        this.pixels = (int[])ip.getPixels();
        this.state = new boolean[ip.getPixelCount()];
        this.nextPixels = new LinkedList<Integer>();
    }

    @Override
    public int setup(String arg0, ImagePlus arg1) {
        return DOES_RGB;
    }

    @Override
    public void mouseClicked(MouseEvent e) {
        ij.WindowManager.getCurrentWindow().getCanvas().removeMouseListener(this);
        ij.gui.GenericDialog g = new GenericDialog("Please enter parameters");
        g.addChoice("connection", new String[]{"4-connect", "8-connect"}, "8-connect");
        g.addNumericField("Threshould (0..255)", 0.0, 3);
        g.showDialog();

        boolean connect8 = g.getNextChoice().equals("8-connect");
        threshould = (int) g.getNextNumber();
        doFill(e.getX(), e.getY(), connect8);
        ij.WindowManager.getCurrentImage().draw();
    }
}
6
15.12.2008 01:41:35

Статья в Википедии довольно хорошая. Пока ваши сетки маленькие, все будет работать.

Ранее этой осенью я сделал несколько заливок на 10-мегапиксельных отсканированных изображениях. (Проблема заключалась в удалении черных краев со страниц книги, которые были отсканированы на фотокопировальном устройстве.) В этом случае есть только два цвета, поэтому я по существу отнесся к проблеме как к поиску в неориентированном графике, где каждый пиксель соединен со своими соседями вдоль четыре направления компаса. Я сохранил отдельное растровое изображение, чтобы отслеживать, какие пиксели были посещены .

Основные выводы были

  • Не пытайтесь выполнить рекурсивный поиск в глубину . Вы действительно хотите явную структуру данных.

  • Вспомогательная очередь использует намного меньше места, чем стек . Примерно в сорок раз меньше места . Другими словами, предпочитайте поиск в ширину поиску в глубину.

Опять же, эти выводы применимы только к сеткам с несколькими мегапикселями . На хорошей маленькой сетке, подобной той, которая показана в вашем вопросе, любой простой алгоритм должен работать.

8
15.12.2008 02:54:40

Простая функция без проверки допуска на цвет

С помощью:

var img = Image.FromFile("test.png");
img = img.FloodFill(new Point(0, 0), Color.Red);
img.Save("testcomplete.png", ImageFormat.Png);

Основная функция:

    public static Image FloodFill(this Image img, Point pt, Color color)
    {
        Stack<Point> pixels = new Stack<Point>();
        var targetColor = ((Bitmap)img).GetPixel(pt.X, pt.Y);
        pixels.Push(pt);

        while (pixels.Count > 0)
        {
            Point a = pixels.Pop();
            if (a.X < img.Width && a.X > -1 && a.Y < img.Height && a.Y > -1)
            {
                if (((Bitmap)img).GetPixel(a.X, a.Y) == targetColor)
                {
                    ((Bitmap)img).SetPixel(a.X, a.Y, color);
                    pixels.Push(new Point(a.X - 1, a.Y));
                    pixels.Push(new Point(a.X + 1, a.Y));
                    pixels.Push(new Point(a.X, a.Y - 1));
                    pixels.Push(new Point(a.X, a.Y + 1));
                }
            }
        }
        return img;
    }
1
8.07.2018 13:24:08

Вот пример использования подпрограмм GDI + в программе на C #.

( https://www.pinvoke.net/default.aspx/gdi32.extfloodfill )

using System.Runtime.InteropServices;
//insert by Zswang(wjhu111#21cn.com) at 2007-05-22
[DllImport("gdi32.dll")]
public static extern IntPtr SelectObject(IntPtr hdc, IntPtr hgdiobj);
[DllImport("gdi32.dll")]
public static extern IntPtr CreateSolidBrush(int crColor);
[DllImport("gdi32.dll")]
public static extern bool ExtFloodFill(IntPtr hdc, int nXStart, int nYStart, 
    int crColor, uint fuFillType);
[DllImport("gdi32.dll")]
public static extern bool DeleteObject(IntPtr hObject);
[DllImport("gdi32.dll")]
public static extern int GetPixel(IntPtr hdc, int x, int y);
public static uint FLOODFILLBORDER = 0;
public static uint FLOODFILLSURFACE = 1;

private void button1_Click(object sender, EventArgs e)
{
    Graphics vGraphics = Graphics.FromHwnd(Handle);
    vGraphics.DrawRectangle(Pens.Blue, new Rectangle(0, 0, 300, 300));
    vGraphics.DrawRectangle(Pens.Blue, new Rectangle(50, 70, 300, 300));
    IntPtr vDC = vGraphics.GetHdc();
    IntPtr vBrush = CreateSolidBrush(ColorTranslator.ToWin32(Color.Red));
    IntPtr vPreviouseBrush = SelectObject(vDC, vBrush);
    ExtFloodFill(vDC, 10, 10, GetPixel(vDC, 10, 10), FLOODFILLSURFACE);
    SelectObject(vDC, vPreviouseBrush);
    DeleteObject(vBrush);
    vGraphics.ReleaseHdc(vDC);
}

Вместо использования Graphics vGraphics = Graphics.FromHwnd(Handle);, если вы вызываете это в обработчике события OnPaint, вы можете использовать e.Graphics. У меня сработало довольно хорошо.

Иногда лучше не изобретать алгоритм и использовать существующие подпрограммы, хотя при переносе на Mono могут возникнуть некоторые проблемы с этим.

0
20.05.2019 11:34:46