What's the best bucket filling algorithm?

Question

I am looking for an algorithm that fills a given region of connected particular nodes in minimum time. I have tried using flood flow algorithm but it's too slow and inefficient for large array, it checks each pixel more than once which when using large array turns out to be too expensive . Is there any algorithm that is more efficient than flood flow algorithm. If there isn't, are there any variants to the algorithm, I have tried using iterative approach to prevent memory overhead of recursion.

If that helps, i want to implement this algorithm for a paint filling app.

Answer 1

If you're referring to the flood-fill algorithm, there is a fixed memory implementation.

set cur to starting pixel
set cur-dir to default direction
clear mark and mark2 (set values to null)
set backtrack and findloop to false

while front-pixel is empty do
    move forward
end while

jump to START

MAIN LOOP:
    move forward
    if right-pixel is empty then
        if backtrack is true and findloop is false and either front-pixel or left-pixel is empty then
            set findloop to true
        end if
        turn right
PAINT:
        move forward
    end if
START:
    set count to number of non-diagonally adjacent pixels filled (front/back/left/right ONLY)
    if count is not 4 then
        do
            turn right
        while front-pixel is empty
        do
            turn left
        while front-pixel is filled
    end if
    switch count
        case 1
            if backtrack is true then
                set findloop to true
            else if findloop is true then
                if mark is null then
                    restore mark
                end if
            else if front-left-pixel and back-left-pixel are both empty then
                clear mark
                fill cur
                jump to PAINT
            end if
        end case
        case 2
            if back-pixel is filled then
                if front-left-pixel is not filled then
                    clear mark
                    fill cur
                    jump to PAINT
                end if
            else if mark is not set then
                set mark to cur
                set mark-dir to cur-dir
                clear mark2
                set findloop and backtrack to false
            else
                if mark2 is not set then
                    if cur is at mark then
                        if cur-dir is the same as mark-dir then
                            clear mark
                            turn around
                            fill cur
                            jump to PAINT
                        else
                            set backtrack to true
                            set findloop to false
                            set cur-dir to mark-dir
                        end if
                    else if findloop is true then
                        set mark2 to cur
                        set mark2-dir to cur-dir
                    end if
                else
                    if cur is at mark then
                        set cur to mark2
                        set cur-dir to mark2-dir
                        clear mark and mark2
                        set backtrack to false
                        turn around
                        fill cur
                        jump to PAINT
                    else if cur at mark2 then
                        set mark to cur
                        set cur-dir and mark-dir to mark2-dir
                        clear mark2
                    end if
                end if
            end if
        end case
        case 3
            clear mark
            fill cur
            jump to PAINT
        end case
        case 4
            fill cur
            done
        end case
    end switch
end MAIN LOOP

Source Wikipedia: https://en.wikipedia.org/wiki/Flood_fill

There is another optimized implementation called the Scanline method.

The C++ implementation of the scanline, quick-fill algorithms is available here. This can be particularly helpful in your case.

https://www.codeproject.com/Articles/6017/QuickFill-An-efficient-flood-fill-algorithm