플러드 필

플러드 필(영어: flood fill) 혹은 시드 필(영어: seed fill)은 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘이다. 이 알고리즘은 그림 프로그램에서 연결된 비슷한 색을 가지는 영역에 "채우기" 도구에 사용되며, 바둑이나 지뢰 찾기 같은 게임에서 어떤 비어 있는 칸을 표시 할 지를 결정할 때에도 사용된다.

알고리즘

플러드 필 알고리즘은 시작 칸, 목표 색, 대체 색의 세 개의 인자를 받는다. 이 알고리즘은 배열에 있는 시작 칸에서 목표 색으로 연결된 모든 칸을 방문해서 대체 색으로 바꾼다. 플러드 필 알고리즘을 구현하는 방법은 여러가지가 있지만, 대부분 큐나 스택과 같은 자료구조를 사용한다.
모서리가 맞닿은 칸이 연결되어 있는 지에 따라서 두 가지 변형이 있다: 각각 4방향과 8방향이다.

스택 기반 재귀 수행 (4 방향)

암시적 스택 기반 (재귀적) 플러드 필 수행(이차원 배열)은 다음과 같다:
Flood-fill (node, target-color, replacement-color):
 1. If target-color is equal to replacement-color, return.
 2. If the color of node is not equal to target-color, return.
 3. Set the color of node to replacement-color.
 4. Perform Flood-fill (one step to the south of node, target-color, replacement-color).
    Perform Flood-fill (one step to the north of node, target-color, replacement-color).
    Perform Flood-fill (one step to the west of node, target-color, replacement-color).
    Perform Flood-fill (one step to the east of node, target-color, replacement-color).
 5. Return.
위에서 사용되는 알고리즘의 수행은 이해하기 쉽지만, 스택공간이 매우 제한된 언어나 환경(예: 자바 애플릿)에서는 실용적이지 않다.

큐 기반 수행

명시적인 큐 기반 수행(종종 "산불 알고리즘"이라고도 불린다)은 아래에 의사 코드로 나타나 있다. 이 수행은 단순한 재귀 해법과 비슷하지만 재귀 호출을 하지 않고 칸을 큐에 넣는다:
Flood-fill (node, target-color, replacement-color):
  1. If target-color is equal to replacement-color, return.
  2. If color of node is not equal to target-color, return.
  3. Set Q to the empty queue.
  4. Set the color of node to replacement-color.
  5. Add node to the end of Q.
  6. While Q is not empty:
  7.     Set n equal to the first element of Q.
  8.     Remove first element from Q.
  9.     If the color of the node to the west of n is target-color,
             set the color of that node to replacement-color and add that node to the end of Q.
 10.     If the color of the node to the east of n is target-color,
             set the color of that node to replacement-color and add that node to the end of Q.
 11.     If the color of the node to the north of n is target-color,
             set the color of that node to replacement-color and add that node to the end of Q.
 12.     If the color of the node to the south of n is target-color,
             set the color of that node to replacement-color and add that node to the end of Q.
 13. Continue looping until Q is exhausted.
 14. Return.
대부분의 실용적인 수행은 스택이나 큐의 오버플로우를 막기 위해 가로 방향 루프를 사용해서 최척화한다:
Flood-fill (node, target-color, replacement-color):
 1. If target-color is equal to replacement-color, return.
 2. If color of node is not equal to target-color, return.
 3. Set Q to the empty queue.
 4. Add node to Q.
 5. For each element N of Q:
 6.     Set w and e equal to N.
 7.     Move w to the west until the color of the node to the west of w no longer matches target-color.
 8.     Move e to the east until the color of the node to the east of e no longer matches target-color.
 9.     For each node n between w and e:
10.         Set the color of n to replacement-color.
11.         If the color of the node to the north of n is target-color, add that node to Q.
12.         If the color of the node to the south of n is target-color, add that node to Q.
13. Continue looping until Q is exhausted.
14. Return.
이 알고리즘에서 영역의 모양을 저장하도록 추가로 배열을 사용하면 채워진 영역의 특정한 경계에서 칸이 다를 수 있는 "흐린" 플러드 필로 일반화 할 수 있다. 이 추가적인 배열을 알파 채널로 사용하면 채워진 영역의 경계에서 채워지지 않은 영역과 부드럽게 섞일 수 있다.

의사코드

다음은 최적의 고정 메모리 플러드 필 알고리즘의 의사코드 수행이다:
변수:
cur, mark, 그리고 mark2는 각각 픽셀의 좌표나 널 값을 가진다
    참고: mark가 널 값으로 설정 된다면, 이전 좌표 값을 지우면 안 된다.
        이 좌표들은 필요할 때마다 불러올 수 있게 해야 한다.
cur-dir, mark-dir, 그리고 mark2-dir는 각각 방향을 가진다 (왼쪽, 오른쪽, 위, 또는 아래)
backtrack과 findloop은 각각 논릿값을 가진다
count는 정수이다
알고리즘:
(참고: 모든 방향(front, back, left, right)은 cur-dir에 대해서 상대적이다)
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
    move forward
end while
﻿
jump to START
﻿
MAIN LOOP:
    move forward
    if right-pixel is empty
        if backtrack is true and findloop is false and either front-pixel or left-pixel is empty
            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
        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
                set findloop to true
            else if findloop is true
                if mark is null
                    restore mark
                end if
            else if front-left-pixel and back-left-pixel are both empty
                clear mark
                fill cur
                jump to PAINT
            end if
        end case
        case 2
            if back-pixel is filled
                if front-left-pixel is not filled
                    clear mark
                    fill cur
                    jump to PAINT
                end if
            else if mark is not set
                set mark to cur
                set mark-dir to cur-dir
                clear mark2
                set findloop and backtrack to false
            else
                if mark2 is not set
                    if cur is at mark
                        if cur-dir is the same as mark-dir
                            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
                        set mark2 to cur
                        set mark2-dir to cur-dir
                    end if
                else
                    if cur is at mark
                        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
                        set mark to cur
                        set cur-dir and mark-dir to mark2-dir
                        clear mark2
                    end
                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

주사선 채우기

이 알고리즘은 한 줄을 채움으로서 속도를 높일 수 있다. 가능한 픽셀 좌표를 각각 스택에 집어 넣는 것이 아니라, 다음에 채울 조각을 찾을 때 이웃한 줄(이전 줄과 다음 줄)을 넣는다. 선분의 좌표(시작과 끝)가 스택에 들어간다. 대부분의 경우, 주사선 알고리즘은 픽셀 단위 알고리즘보다 적어도 크기만큼 빠르다.
효율성: 각각의 픽셀은 한 번만 검사된다.

벡터 수행

잉크스케이프 버전 0.46은 채우기 도구가 있어서 일반적인 비트맵 연산과 비슷한 결과를 내며 실제로 사용한다: 캔버스가 렌더 되고, 플러드 필 연산을 선택된 영역에 수행한 후, 그 결과를 가지고 경로를 되돌아간다. 이는 경계 조건의 개념을 사용한다.