Floodfill в ActionScript 3

Question

Я пытаюсь написать свою собственную функцию заливки в ActionScript3, потому что предоставленная Adobe недостаточно гибкая (вы можете задать только один целевой цвет, я бы хотел задать диапазон целевых цветов.)

Итак, ужасный код, который я придумал, таков:

private function beginAlgortime(xx:int,yy:int):void
{
    if (bmp.bitmapData.getPixel(xx, yy) != 0x333333) {

        bmp.bitmapData.setPixel(xx, yy, 0x333333);

        beginAlgortime(xx + 1, yy);
        beginAlgortime(xx + 1, yy+1);
        beginAlgortime(xx + 1, yy - 1);

        beginAlgortime(xx , yy+1);
        beginAlgortime(xx , yy - 1);

        beginAlgortime(xx - 1, yy);
        beginAlgortime(xx - 1, yy+1);
        beginAlgortime(xx - 1, yy-1);
    }
}

довольно базовая рекурсивная функция. Но очевидно, что при использовании этого метода флеш-плейер обрушивается на меня :) У кого-нибудь есть решение для этого? ура!

Answer 1

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

что именно вы подразумеваете под заливкой? а что вы подразумеваете под "ассортиментом цветов"?

предоставленная вами подпрограмма заполнит все растровое изображение 0x333333. и оно не прекратится, поскольку вы никогда не проверяете, выходите ли вы за границы растровых изображений.

Answer 2

Вот что я использовал:

private function floodFill(bitmapData: BitmapData, x: int, y: int, backColor: uint, fillColor: uint): void
{
    var data: Vector. = bitmapData.getVector(bitmapData.rect);

    var queueX:Vector. = new Vector.();
    var queueY:Vector. = new Vector.();

    queueX.push(x);
    queueY.push(y);

    while (queueX.length > 0) {
        x = queueX.shift();
        y = queueY.shift();

        if (x = width || y = height)
            return;

        if (data[y*width + x] == backColor) {
            data[y*width + x] = fillColor;

            queueX.push(x+1);
            queueY.push(y);

            queueX.push(x-1);
            queueY.push(y);

            queueX.push(x);
            queueY.push(y+1);

            queueX.push(x);
            queueY.push(y-1);
        }
    }

    bitmapData.setVector(bitmapData.rect, data);
}

Answer 3

Вы можете попробовать преобразовать его из рекурсивной функции в итеративную функцию, которая использует массив вместо программного стека.

Вот итеративная реализация FloodFill, как описано в , в статье Аллана упоминается :

function floodFill(bmpData:BitmapData, startX:int, startY:int, fill:uint, old:uint):void
{
    var queue:Array = new Array();

    queue.push(new Point(startX, startY));

    var iterations:uint = 0;
    var bmpWidth:int = bmpData.width;
    var bmpHeight:int = bmpData.height;

    var searchBmp:BitmapData = new BitmapData(bmpData.width, bmpData.height);
    var currPoint:Point, newPoint:Point;
    while (queue.length > 0)
    {
        currPoint = queue.shift();
        ++iterations;

        if (currPoint.x < 0 || currPoint.x >= bmpWidth) continue;
        if (currPoint.y < 0 || currPoint.y >= bmpHeight) continue;

        searchBmp.setPixel(currPoint.x, currPoint.y, 0x00);

        if (bmpData.getPixel(currPoint.x, currPoint.y) == old)
        {
            bmpData.setPixel(currPoint.x, currPoint.y, fill);

            if (searchBmp.getPixel(currPoint.x + 1, currPoint.y) == 0xFFFFFF)
            {
                queue.push(new Point(currPoint.x + 1, currPoint.y));
            }
            if (searchBmp.getPixel(currPoint.x, currPoint.y + 1) == 0xFFFFFF)
            {
                queue.push(new Point(currPoint.x, currPoint.y + 1));
            }
            if (searchBmp.getPixel(currPoint.x - 1, currPoint.y) == 0xFFFFFF)
            {
                queue.push(new Point(currPoint.x - 1, currPoint.y));
            }
            if (searchBmp.getPixel(currPoint.x, currPoint.y - 1) == 0xFFFFFF)
            {
                queue.push(new Point(currPoint.x, currPoint.y - 1));
            }
        }

    }       
    trace("iterations: " + iterations);
}

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

Этот код заполняет растровое изображение 2000x1400 за ~ 14 секунд на моем компьютере. Для лучшего взаимодействия с пользователем вам следует разбить обработку заливки на несколько кадров, чтобы пользователю не приходилось смотреть на значок ожидания.

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

Редактировать, чтобы добавить: В статье Flood fill в Википедии есть несколько предложений алгоритмов.