Floodfill 함수 (영역 채우기) - Seed Fill

<출처> http://ko.wikipedia.org/wiki/%ED%8C%8C%EC%9D%BC:Recursive_Flood_Fill_8_(aka).gif

 

 

플러드 필(Flood fill), 시드 필(seed fill)을 구현하는 재귀 함수 알고리듬

 

이 함수는 재귀호출을 이용한 영역 채움 기능을 제공한다.

닫혀진 영역에서 칠하려는 색과 다르 부분을 지정된 색으로 칠해가는 함수이다.

그림판에서 영역 채우는 기능이 그런 알고리듬을 사용한 예다.

 

*펄 언어로 구현한 플러드필 함수

sub FloodFill8
{
    my ($x, $y) = @_;

    if ($im->getPixel ($x, $y) == $colfill)
    {
       $im->setPixel ($x, $y, $colpen);
       WriteImage ();

       FloodFill8 ($x, $y+1);
       FloodFill8 ($x, $y-1);
       FloodFill8 ($x+1, $y);
       FloodFill8 ($x-1, $y);
       FloodFill8 ($x+1, $y+1);
       FloodFill8 ($x+1, $y-1);
       FloodFill8 ($x-1, $y+1);
       FloodFill8 ($x-1, $y-1);
    }
}
 

데모: http://upload.wikimedia.org/wikipedia/commons/8/89/Recursive_Flood_Fill_8_%28aka%29.gif

 

 

다음은 신위양님이 루아(Lua)로 게임을 만들 때 활용한 플러드필 함수이다.

<출처> http://blog.naver.com/PostList.nhn?blogId=sinwee&from=postList&categoryNo=26

 

여기서 t는 2차원 배열로 x(가로) 7, y(세로) 9 크기이다.

flood_fill을 하여 서로 붙어있는 블럭들은 -1로 마킹이 되고.

나중에 마킹된 블럭의 갯수를 세어 3개가 넘어서면 블럭을 삭제한다.  

이를 2중 중첩 for문을 돌려서 배열의 모든 부분에 반복한다

 

function flood_fill(x,y,t,color)

if x < 0 or x > 7 or y < 0 or y > 9 then --excess range -> exit

return

elseif t[y][x] ~= color then --if diffrent Color -> exit

return

else

t[y][x] = -1 --Marking(-1)

flood_fill(x+1, y   , t, color) --Right

flood_fill(x-1, y   , t, color) --Left

flood_fill(x,   y+1 , t, color) --Up

flood_fill(x,   y+1 , t, color) --Down

end

end