위키백과

플러드 필: 두 판 사이의 차이

입체적으로 역사 찾아보기
← 이전 편집다음 편집 →
내용 삭제됨 내용 추가됨
시각위키텍스트
88번째 줄:
표시는 처음 찾은 2 픽셀 경계에서 통로가 어디서 시작했으며 화가가 어느 방향으로 움직였는지를 기억하기 위해서 사용한다. 만약 이 표시를 다시 찾았고, 화가가 같은 방향으로 가고 있다면, 표시가 있는 칸을 칠해도 괜찮기 때문에 칠하고 같은 방향으로 이동한다. 왜냐하면 나중에 (어떤 경로로든)표시와 반대쪽에 있는 픽셀에 도달해 칠할 수 있기 때문이다. 이 표시는 나중에 쓰기 위해 지운다.
 
만약 화가가 표시를 다시 찾았으나 다른 방향으로 가고 있었다면, 화가가 표시로 되돌아 오게 만든 어떤 루프가 있는 것이다. 이 루프는 없애야만 한다. 표시를 주워서 표시에 쓰여 있던 방향으로 다시 가되, 이번에는 왼손 법칙(오른손 법칙과 비슷하지만 왼손을 이용한다)을 이용해서 교차로(경계 픽셀이 세셋 개이상 이상인열린 곳)를 찾을 때까지 계속 작업한다. 계속 왼손 법칙을 사용하지만 이번에는 단순한 통로(경계 픽셀 두 개로 이루어진 곳)을 찾는다. 이 두 픽셀 경계를 가지는 통로를 찾으면, 그 픽셀을 색칠한다. 이는 루프를 끝내고 알고리즘이 계속될 수 있게 한다.
 
4번 경우, 반대쪽 8방향 연결된 모서리가 채워졌는지를 검사해야 한다. 만약 둘 중 하나라도 채워져 있다면, 이 칸은 다경로 교차로를 만들기 때문에 칠해서는 안된다. 만약 둘 다 비었을 경우에는, 현재 픽셀을 칠하고 화가는 오른손 법칙을 따라서 이동한다.
100번째 줄:
 
'''변수:'''
cur, mark, 그리고 mark2는 각각 픽셀의 좌표나 널 값을 가진다
참고: mark가 널 값으로 설정 된다면, 이전 좌표 값을 지우면 안 된다.
이 좌표들은 필요할 때마다 불러올 수 있게 해야 한다.
cur-dir, mark-dir, 그리고 mark2-dir는 각각 방향을 가진다 (왼쪽, 오른쪽, 위, 또는 아래)
backtrack과 findloop은 각각 논릿값을 가진다
count는 정수이다
 
'''알고리즘:'''
117번째 줄:
while front-pixel is empty
move forward
end while
123번째 줄:
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 ifswitch count
end case 1
if backtrack is true
case 3
set findloop to true
clear mark
else if findloop is true
fill cur
if mark is null
jump to PAINT
restore mark
end case
end if
case 4
else if front-left-pixel and back-left-pixel are both empty
fill cur
clear mark
done
fill cur
end case
jump to PAINT
end switch
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
 
원본 주소 "https://ko.wikipedia.org/wiki/플러드_필"