플러드 필

플러드 필() 혹은 시드 필()은 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘이다. 이 알고리즘은 그림 프로그램에서 연결된 비슷한 색을 가지는 영역에 "채우기" 도구에 사용되며, 바둑이나 지뢰 찾기 같은 게임에서 어떤 비어 있는 칸을 표시 할 지를 결정할 때에도 사용된다.
알고리즘.
플러드 필 알고리즘은 시작 칸, 목표 색, 대체 색의 세 개의 인자를 받는다. 이 알고리즘은 배열에 있는 시작 칸에서 목표 색으로 연결된 모든 칸을 방문해서 대체 색으로 바꾼다. 플러드 필 알고리즘을 구현하는 방법은 여러가지가 있지만, 대부분 큐나 스택과 같은 자료구조를 사용한다.
모서리가 맞닿은 칸이 연결되어 있는 지에 따라서 두 가지 변형이 있다: 각각 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.
이 알고리즘에서 영역의 모양을 저장하도록 추가로 배열을 사용하면 채워진 영역의 특정한 경계에서 칸이 다를 수 있는 "흐린" 플러드 필로 일반화 할 수 있다. 이 추가적인 배열을 알파 채널로 사용하면 채워진 영역의 경계에서 채워지지 않은 영역과 부드럽게 섞일 수 있다.
고정 메모리 방법(오른손 채우기 방법).
알고리즘이 화가가 되어서 자신이 있는 칸을 색칠하는 것을 미뤄두고 주변의 4방향 연결된 영역을 색칠하기 위한 메모리가 본질적으로 없을 때 사용되는 방법이 있다. 이는 또한 미로를 푸는 방법이기도 한다. 일차적인 경계를 형성하는 네 픽셀은 어떤 행동을 취할지를 알기 위해서 확인한다. 화가는 다음 중 한 가지 상태에 있을 수 있다:
경로나 경계를 따라가기 위해서 오른손의 법칙을 사용한다. 화가는 오른손을 벽에(영역의 경계) 짚고 손을 떼지 않으면서 영역의 경계를 따라 칠한다.
1번 경우, 화가는 자신이 있는 픽셀을 칠하고 알고리즘을 끝낸다.
2번 경우, 그 영역을 나가는 경로가 있다. 자신이 있는 픽셀을 칠하고 열린 경로로 이동한다.
3번 경우, 현재 픽셀을 칠하면 반대편 경로로 가는 것이 불가능 할 수 있기 때문에 두 경계 픽셀이 경로를 결정한다. 따라서 만약 이 픽셀로 되돌아왔을 때 보기 위해 이 픽셀의 위치와 어느 방향으로 향하는 지를 "표시"해야 한다. 만약 이미 그런 "표시"가 있다면, 이전의 표시를 그대로 두고는 오른손 법칙을 따라서 다음 픽셀로 간다.
표시는 처음 찾은 2 픽셀 경계에서 통로가 어디서 시작했으며 화가가 어느 방향으로 움직였는지를 기억하기 위해서 사용한다. 만약 이 표시를 다시 찾았고, 화가가 같은 방향으로 가고 있다면, 표시가 있는 칸을 칠해도 괜찮기 때문에 칠하고 같은 방향으로 이동한다. 왜냐하면 나중에 (어떤 경로로든)표시와 반대쪽에 있는 픽셀에 도달해 칠할 수 있기 때문이다. 이 표시는 나중에 쓰기 위해 지운다.
만약 화가가 표시를 다시 찾았으나 다른 방향으로 가고 있었다면, 화가가 표시로 되돌아 오게 만든 어떤 루프가 있는 것이다. 이 루프는 없애야만 한다. 표시를 주워서 표시에 쓰여 있던 방향으로 다시 가되, 이번에는 왼손 법칙(오른손 법칙과 비슷하지만 왼손을 이용한다)을 이용해서 교차로(경계 픽셀이 셋 이상 열린 곳)를 찾을 때까지 계속 작업한다. 계속 왼손 법칙을 사용하지만 이번에는 단순한 통로(경계 픽셀 두 개로 이루어진 곳)을 찾는다. 이 두 픽셀 경계를 가지는 통로를 찾으면, 그 픽셀을 색칠한다. 이는 루프를 끝내고 알고리즘이 계속될 수 있게 한다.
4번 경우, 반대쪽 8방향 연결된 모서리가 채워졌는지를 검사해야 한다. 만약 둘 중 하나라도 채워져 있다면, 이 칸은 다경로 교차로를 만들기 때문에 칠해서는 안된다. 만약 둘 다 비었을 경우에는, 현재 픽셀을 칠하고 화가는 오른손 법칙을 따라서 이동한다.
이 알고리즘은 시간을 메모리로 바꾼다. 단순한 도형에 대해서는 매우 효율적이지만, 모양이 복잡하고 특징이 많으면, 모든 영역이 칠해졌다는 것을 확실히 하기 위해서 영역의 경계에서 매우 많은 시간을 소요한다.
이 알고리즘은 1981년에 처음으로 Vicom Systems, Inc에서 제작한 Vicom Image Processing 시스템에서 상업적으로 이용 가능해졌다. 이 시스템에서는 평범한 재귀 플러드 필 알고리즘도 사용 가능하다.
의사코드.
다음은 최적의 고정 메모리 플러드 필 알고리즘의 의사코드 수행이다:
변수:
 cur, mark, 그리고 mark2는 각각 픽셀의 좌표나 널 값을 가진다
 참고: mark가 널 값으로 설정 된다면, 이전 좌표 값을 지우면 안 된다.
 이 좌표들은 필요할 때마다 불러올 수 있게 해야 한다.
 cur-dir, mark-dir, 그리고 mark2-dir는 각각 방향을 가진다 (왼쪽, 오른쪽, 위, 또는 아래)
 backtrack과 findloop은 각각 논릿값을 가진다
 count는 정수이다
알고리즘:
 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은 채우기 도구가 있어서 일반적인 비트맵 연산과 비슷한 결과를 내며 실제로 사용한다: 캔버스가 렌더 되고, 플러드 필 연산을 선택된 영역에 수행한 후, 그 결과를 가지고 경로를 되돌아간다. 이는 경계 조건의 개념을 사용한다.
큰 규모에서 양상.
플러드 필을 조작할 때 주로 사용되는 기술은 데이터 중심과 처리 중심이 있다. 데이터 중심 접근은 확인 할 시드 픽셀을 쫓아가기 위해서 스택이나 큐를 사용할 수 있다. 처리 중심 알고리즘은 반드시 스택을 사용해야 한다.
인접 기술과 시드 픽셀 저장으로 큐를 사용하는 4방향 플러드 필 알고리즘은 확장하는 마름모꼴의 형태로 채운다.
효율성: 각각의 픽셀이 채워질 때 4픽셀이 검사된다 (8방향에서는 8픽셀).
인접 기술과 시드 픽셀 저장으로 스택을 사용하는 4방향 플러드 필 알고리즘은 "틈은 나중에 메우는" 양상을 띄며 선형적으로 채운다. 이 접근은 특히 "Graphic Adventure Creator"에서 만든 게임 같은 오래된 8비트 게임에서 나타난다.
효율성: 각각의 픽셀이 채워질 때 4픽셀이 검사된다 (8방향에서는 8픽셀).