Какой лучший алгоритм заполнения ковша? - PullRequest
Новая
       24

Какой лучший алгоритм заполнения ковша?

0 голосов
/ 13 апреля 2020

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

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

1 Ответ

1 голос
/ 13 апреля 2020

Если вы имеете в виду алгоритм заполнения, существует фиксированная реализация памяти. 

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.

Реализация алгоритма быстрого заполнения Scanline, быстрого заполнения, доступна здесь. Это может быть особенно полезно в вашем случае.

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

...