Заливка

Наступний псевдокод показує реалізацію, засновану на застосуванні черги в явному вигляді. Це схоже на рекурсивне рішення, за винятком того, що замість рекурсивних викликів, він штовхає вузли в стек:

 Заливка (вузол, замінюваний колір, колір заливки):
 1. Якщо замінюваний колір дорівнює кольору заливки, то повернутись.
 2. Присвоїти  Q  порожню чергу.
 3. Додати вузол у кінець Q.
 4. До тих пір, поки  Q  не порожній:
 5.    Присвоїти  n  перший елемент  Q 
 6.    Видалити перший елемент  Q .
 7.    Якщо колір  n  дорівнює  замінюваному кольору :
 8.       Встановити колір n до кольору заливки і відмітити "n" як елемент,що обробляється.
 9.       Додати західний вузол до кінця  Q , якщо західний елемент ще не був оброблений.
10.       Додати східний вузол до кінця  Q , якщо східний  елемент ще не був оброблений.
11.       Додати північний вузол до кінця  Q , якщо північний елемент ще не був оброблений.
12.       Додати південний вузол до кінця  Q , якщо південний елемент ще не був оброблений.
13.Повернутися.

Для того, щоб використовувати прапор "оброблено", усі пікселі доведеться ініціалізувати як необроблені перед запитом цього алгоритму. Найбільш практичні методики оптимізують використання стека або черги, вводячи цикл за «західним» і «східним» напрямками:

 Заливка (вузол, замінюваний колір, колір заливки):
 1. Присвоїти  Q  порожню чергу.
 2. Якщо колір  вузла не дорівнює замінюваному кольору, повернутись.
 3. Додати  вузол  у  Q .
 4. Для кожного елемента від  N  до  Q :
 5.   Присвоїти  w  і  e  дорівнюють  N .
 6.   Переміщайте  w  на захід, поки колір вузла на захід від  w  більше не відповідає  замінюваному кольору .
 7.   Переміщайте  е  на схід, поки колір вузла на схід від  е  більше не відповідає  замінюваному кольору .
 8.   Для кожного вузла  n  між  w  і  e :
 9.    Встановіть колір  n  як  колір заливки         
10.    Якщо колір вузла на північ від  n  є  замінюваним кольором , додати цей вузол у  Q .
11.    Якщо колір вузла на південь від  n  є  замінюваним кольором , додати цей вузол у  Q .
12. Продовжувати цикл доки  Q  не закінчиться.
13. Повернутись. 

Якщо прописати в алгоритмі використання окремого масиву для зберігання форми області, це дозволить узагальнити його на випадок «нечіткого» заповнення, коли елементи можуть дещо відрізнятися від початково заданих. Використання цього додаткового масиву як альфа-каналу дозволяє створити плавний перехід на кордонах між залитою і не залитою областями.

Є метод, що практично не використовує додаткової пам'яті для зв'язуючих по 4 напрямках (див. Околиця фон Неймана) областей. Цим же методом можна шукати вихід з лабіринту. Уявіть собі маляра, який фарбує область так, щоб не опинитися затиснутим в кутку. Початкові кордони — це чотири пікселя, які маляр розглядає, щоб вибрати одну з можливих дій. Основні можливі стани:

1. Всі 4 граничних пікселя пофарбовані.
2. Три граничних пікселя пофарбовані.
3. Два граничних пікселя пофарбовані.
4. Один граничний піксель зафарбований.
5. Жоден з граничних пікселів не зафарбований.

При продовженні кордону використовується метод правої руки. Маляр обходить область, тримаючи праву руку на «стіні» (кордоні області) і просувається, не відриваючи руки.

У випадку № 1 маляр фарбує піксель, на якому стояв, і закінчує (алгоритм завершений).

У випадку № 2 існує шлях з області назовні. Маляр фарбує піксель, на якому стояв, і рухається цим шляхом.

У випадку № 3 два граничних пікселя створюють смугу, яка, якщо ми пофарбуємо поточний піксель, може відрізати нас від усього, що знаходиться по її іншу сторону. Потрібно закріпити «стрілку», що вказує, де ми зараз і куди дивимося, щоб, якщо ми колись повернемося на цей піксель, ми могли її побачити. Якщо така стрілка вже намальована, ми її зберігаємо і рухаємося далі за правилом правої руки.

Стрілка на першому двохпіксельному кордоні фіксує, де маляр почав роботу і куди звідти пішов. Якщо маляр зустрічає ту ж мітку, рухаючись в тому ж напрямку, то він розуміє, що фарбувати цей квадрат, рухаючись у цьому напрямку, безпечно: пікселі на іншій стороні по якомусь поки не відомому шляху будуть доступні для фарбування в майбутньому. Мітка знімається, і її можна поставити десь ще.

Якщо ж маляр зустрічає стрілку, що вказує не туди, куди він йде, значить, він пройшов якимось шляхом, що повернув його до мітки. Цю петлю треба виключити. Мітка забирається, а маляр рухається у вказаному нею напрямі, керуючись правилом лівої руки. Так він йде, поки не потрапить на перетин (з не менш ніж трьома пікселями відкритого кордону). Не відриваючи лівої руки, маляр шукає простий прохід (що складається з двох граничних пікселів). Знайшовши його, він фарбує цей піксель, петля розривається, і можна продовжувати алгоритм.

У випадку № 4 ми повинні перевірити протилежні зв'язані по 8 напрямам кути — пофарбовані вони чи ні. Якщо хоча б один з цих двох кутів пофарбований, виходить перетин багатьох шляхів, які ми зафарбувати не зможемо. Якщо обидва порожні, можемо пофарбувати поточний піксель і слідувати далі за правилом правої руки.

Алгоритм дає виграш в пам'яті за рахунок програшу за часом. Для областей простої форми він дуже ефективний, але в більш складних випадках багато часу витрачається на те, щоб відстежити межі області і переконатися, що все можна зафарбувати.

Перша комерційна реалізація цього алгоритму з'явилася в 1981 році на системі Vicom Image Processing, випущеної Vicom Systems, Inc. Також в цій системі був присутній і класичний рекурсивний алгоритм.

Це реалізація псевдокоду, який виконує алгоритм заливки, з фіксованим використанням пам'яті.

Змінні :

    cur, mark, and mark2 each hold either pixel coordinates or a null value
         NOTE: when mark is set to null, do not erase its previous coordinate value.
               Keep those coordinates available to be recalled if necessary.
    cur-dir, mark-dir, and mark2-dir each hold a direction (left, right, up, or down)
    backtrack and findloop each hold boolean values
    count is an integer

(Примітка: усі напрямки (front, back, left, right) рахуються відносно поточного напрямку)

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