最好的存储桶填充算法是什么？

Question

我正在寻找一种算法，可以在最短的时间内填充连接的特定节点的给定区域。我已经尝试过使用洪流算法，但是对于大型阵列而言，它太慢且效率低下，它不止一次检查每个像素，而当使用大型阵列时，结果却过于昂贵。有没有比洪流算法更有效的算法。如果没有，算法是否有任何变体，我尝试使用迭代方法来防止递归的内存开销。

如果有帮助，我想为油漆填充应用程序实现此算法。

Answer 1

如果您使用的是泛洪填充算法，则有固定的内存实现。

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

来源维基百科：https://en.wikipedia.org/wiki/Flood_fill

还有另一种优化的实现，称为Scanline方法。

扫描线的C ++实现，快速填充算法可在此处获得。这对您的情况特别有用。

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