Заливка (від англ. flood fill чи англ. seed fill) — це алгоритм, що визначає область, «поєднану» з певним елементом у багатомірному масиві (як правило, це двовимірний масив точок растрового зображення). Алгоритм застосовується у програмах для редагування графіки для визначення області, яку треба заповнити певним кольором.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTg0THpnNUwxSmxZM1Z5YzJsMlpWOUdiRzl2WkY5R2FXeHNYemhmSlRJNFlXdGhKVEk1TG1kcFpnPT0uZ2lm.gif)
Заливка зображень — часто потрібна на практиці функція, суть якої — заповнити деяку область зображення, обмежену контуром, що заданий певним кольором.
Алгоритм
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTgzTHpkbEwxSmxZM1Z5YzJsMlpWOUdiRzl2WkY5R2FXeHNYelJmSlRJNFlXdGhKVEk1TG1kcFpnPT0uZ2lm.gif)
Алгоритм має три параметри на вхід: стартовий елемент (вузол), замінюваний колір і колір заливки. Відшукуються всі елементи масиву, що зв'язані з початковим шляхом змінюємого кольору, і перефарбовуються у колір заливки. Варіантів реалізації достатньо багато, але всі вони так чи інакше використовують чергу або стек. Ось псевдокод простого рекурсивного алгоритму, в якому зв'язність у двовимірному масиві визначається у 4 напрямах:
Заливка (вузол, замінюваний колір, колір заливки): 1. Якщо замінюваний колір дорівнює кольору заливки, то повернутись. 2. Якщо колір вузла не дорівнює замінюваному кольору, то повернутись. 3. Встановити колір вузла у колір заливки. 4. Виконати Заливку (крок на захід від вузла, замінюваний колір, колір заливки). Виконати Заливку (крок на схід від вузла, замінюваний колір, колір заливки). Виконати Заливку (крок на північ від вузла, замінюваний колір, колір заливки). Виконати Заливку (крок на південь від вузла, замінюваний колір, колір заливки). 5. Повернутися.
Хоча цей алгоритм і простий для розуміння, але він практично не застосовується у випадках обмеженості рекурсії (наприклад, у аплетах Java)
Інші способи реалізації
Наступний псевдокод показує реалізацію, засновану на застосуванні черги в явному вигляді. Це схоже на рекурсивне рішення, за винятком того, що замість рекурсивних викликів, він штовхає вузли в стек:
Заливка (вузол, замінюваний колір, колір заливки): 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. Повернутись.
Якщо прописати в алгоритмі використання окремого масиву для зберігання форми області, це дозволить узагальнити його на випадок «нечіткого» заповнення, коли елементи можуть дещо відрізнятися від початково заданих. Використання цього додаткового масиву як альфа-каналу дозволяє створити плавний перехід на кордонах між залитою і не залитою областями.
Метод заливки для фіксованого об'єму пам'яті
Метод заливки, що реалізується в обмеженому об'ємі пам'яті (англ. Fixed memory method), або, як його ще називають, — «метод правої руки».
Опис методу
Є метод, що практично не використовує додаткової пам'яті для [en] (див. Околиця фон Неймана) областей. Цим же методом можна шукати вихід з лабіринту. Уявіть собі маляра, який фарбує область так, щоб не опинитися затиснутим в кутку. Початкові кордони — це чотири пікселя, які маляр розглядає, щоб вибрати одну з можливих дій. Основні можливі стани:
- Всі 4 граничних пікселя пофарбовані.
- Три граничних пікселя пофарбовані.
- Два граничних пікселя пофарбовані.
- Один граничний піксель зафарбований.
- Жоден з граничних пікселів не зафарбований.
При продовженні кордону використовується метод правої руки. Маляр обходить область, тримаючи праву руку на «стіні» (кордоні області) і просувається, не відриваючи руки.
У випадку № 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
Метод сканування рядків
Алгоритм можна прискорити, заливаючи відразу лініями. Замість вкладання в стек координат кожного з можливих майбутніх пікселів розглядаються сусідні рядки (ті, що вище і ті, що нижче), і в них визначаються суміжні сегменти, які при наступному проході можна залити; координати (початок чи кінець) втискуються в стек. У більшості випадків рядковий алгоритм на порядок швидше попіксельного алгоритму. Його перевага в тому, що кожен піксель перевіряється тільки один раз.
У векторній графіці
Програма Inkscape версії 0.46 надає інструмент букетної заливки, що виглядає як звичайна растрова операція і в дійсності її застосовує: зображення вимальовується, застосовується заливка вибраної області, і її результат перетворюється назад у векторний вигляд. При цьому використовується концепція граничних умов.
Поведінка при великих розмірах
![]() | ![]() | |
Заливка у чотирьох напрямах, яка використовує чергу для зберігання | Заливка у чотирьох напрямах, яка використовує стек для зберігання |
Основна методика використовується для управління заливкою і може бути орієнтована на данні або на процес. Підхід, що орієнтується на данні може використовувати або чергу, або стек щоб зберігати шлях пікселів, які потребують перевірки. Підхід, що орієнтується на процес має використовувати стек.
Алгоритм заливки у чотирьох напрямах використовує суміжну техніку і чергу як місце для зберігання пікселів та ромбовидно заповнюється.
Ефективність: для заливки одного пікселя перевіряються чотири (вісім, якщо рух іде у восьми напрямках)
Алгоритм заливки у чотирьох напрямах використовує суміжну техніку і стек як місце для зберігання пікселів з лінійною заливкою. Цей алгоритм може бути добре видно у старих 8-бітних іграх, що були створені за допомогою [en].
Ефективність: для заливки одного пікселя перевіряються чотири (вісім, якщо рух іде у восьми напрямках)
Посилання
- Алгоритми заливки зображень, популярно і з відео [ 2 квітня 2015 у Wayback Machine.]
- Алгоритми заливки багатокутників [ 2 квітня 2015 у Wayback Machine.]
- Алгоритм заливки замкнутого контуру [ 2 квітня 2015 у Wayback Machine.]
- , Гільєрме Поло.
- C program to implement floodfill algorithm(4-connected boundary) [ 9 травня 2015 у Wayback Machine.]
- Sample implementations for recursive and non-recursive, classic and scanline flood fill [ 7 травня 2015 у Wayback Machine.], by Lode Vandevenne.
- , Пол Хекберт.
- Flash flood fill implementation [ 16 травня 2015 у Wayback Machine.], Емануеле Феронато.
- QuickFill: An efficient flood fill algorithm. [ 9 грудня 2011 у Wayback Machine.], Джон Р.Шоу.
![]() | Це незавершена стаття про алгоритми. Ви можете проєкту, виправивши або дописавши її. |
Ця стаття потребує додаткових для поліпшення її . (серпень 2017) |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Zalivka vid angl flood fill chi angl seed fill ce algoritm sho viznachaye oblast poyednanu z pevnim elementom u bagatomirnomu masivi yak pravilo ce dvovimirnij masiv tochok rastrovogo zobrazhennya Algoritm zastosovuyetsya u programah dlya redaguvannya grafiki dlya viznachennya oblasti yaku treba zapovniti pevnim kolorom Rekursivna zalivka u vosmi napryamah Zalivka zobrazhen chasto potribna na praktici funkciya sut yakoyi zapovniti deyaku oblast zobrazhennya obmezhenu konturom sho zadanij pevnim kolorom AlgoritmRekursivna zalivka u chotiroh napryamah Algoritm maye tri parametri na vhid startovij element vuzol zaminyuvanij kolir i kolir zalivki Vidshukuyutsya vsi elementi masivu sho zv yazani z pochatkovim shlyahom zminyuyemogo koloru i perefarbovuyutsya u kolir zalivki Variantiv realizaciyi dostatno bagato ale vsi voni tak chi inakshe vikoristovuyut chergu abo stek Os psevdokod prostogo rekursivnogo algoritmu v yakomu zv yaznist u dvovimirnomu masivi viznachayetsya u 4 napryamah Zalivka vuzol zaminyuvanij kolir kolir zalivki 1 Yaksho zaminyuvanij kolir dorivnyuye koloru zalivki to povernutis 2 Yaksho kolir vuzla ne dorivnyuye zaminyuvanomu koloru to povernutis 3 Vstanoviti kolir vuzla u kolir zalivki 4 Vikonati Zalivku krok na zahid vid vuzla zaminyuvanij kolir kolir zalivki Vikonati Zalivku krok na shid vid vuzla zaminyuvanij kolir kolir zalivki Vikonati Zalivku krok na pivnich vid vuzla zaminyuvanij kolir kolir zalivki Vikonati Zalivku krok na pivden vid vuzla zaminyuvanij kolir kolir zalivki 5 Povernutisya Hocha cej algoritm i prostij dlya rozuminnya ale vin praktichno ne zastosovuyetsya u vipadkah obmezhenosti rekursiyi napriklad u apletah Java Inshi sposobi realizaciyi Nastupnij psevdokod pokazuye realizaciyu zasnovanu na zastosuvanni chergi v yavnomu viglyadi Ce shozhe na rekursivne rishennya za vinyatkom togo sho zamist rekursivnih viklikiv vin shtovhaye vuzli v stek Zalivka vuzol zaminyuvanij kolir kolir zalivki 1 Yaksho zaminyuvanij kolir dorivnyuye koloru zalivki to povernutis 2 Prisvoyiti Q porozhnyu chergu 3 Dodati vuzol u kinec Q 4 Do tih pir poki Q ne porozhnij 5 Prisvoyiti n pershij element Q 6 Vidaliti pershij element Q 7 Yaksho kolir n dorivnyuye zaminyuvanomu koloru 8 Vstanoviti kolir n do koloru zalivki i vidmititi n yak element sho obroblyayetsya 9 Dodati zahidnij vuzol do kincya Q yaksho zahidnij element she ne buv obroblenij 10 Dodati shidnij vuzol do kincya Q yaksho shidnij element she ne buv obroblenij 11 Dodati pivnichnij vuzol do kincya Q yaksho pivnichnij element she ne buv obroblenij 12 Dodati pivdennij vuzol do kincya Q yaksho pivdennij element she ne buv obroblenij 13 Povernutisya Dlya togo shob vikoristovuvati prapor obrobleno usi pikseli dovedetsya inicializuvati yak neobrobleni pered zapitom cogo algoritmu Najbilsh praktichni metodiki optimizuyut vikoristannya steka abo chergi vvodyachi cikl za zahidnim i shidnim napryamkami Zalivka vuzol zaminyuvanij kolir kolir zalivki 1 Prisvoyiti Q porozhnyu chergu 2 Yaksho kolir vuzla ne dorivnyuye zaminyuvanomu koloru povernutis 3 Dodati vuzol u Q 4 Dlya kozhnogo elementa vid N do Q 5 Prisvoyiti w i e dorivnyuyut N 6 Peremishajte w na zahid poki kolir vuzla na zahid vid w bilshe ne vidpovidaye zaminyuvanomu koloru 7 Peremishajte e na shid poki kolir vuzla na shid vid e bilshe ne vidpovidaye zaminyuvanomu koloru 8 Dlya kozhnogo vuzla n mizh w i e 9 Vstanovit kolir n yak kolir zalivki 10 Yaksho kolir vuzla na pivnich vid n ye zaminyuvanim kolorom dodati cej vuzol u Q 11 Yaksho kolir vuzla na pivden vid n ye zaminyuvanim kolorom dodati cej vuzol u Q 12 Prodovzhuvati cikl doki Q ne zakinchitsya 13 Povernutis Yaksho propisati v algoritmi vikoristannya okremogo masivu dlya zberigannya formi oblasti ce dozvolit uzagalniti jogo na vipadok nechitkogo zapovnennya koli elementi mozhut desho vidriznyatisya vid pochatkovo zadanih Vikoristannya cogo dodatkovogo masivu yak alfa kanalu dozvolyaye stvoriti plavnij perehid na kordonah mizh zalitoyu i ne zalitoyu oblastyami Metod zalivki dlya fiksovanogo ob yemu pam yatiMetod zalivki sho realizuyetsya v obmezhenomu ob yemi pam yati angl Fixed memory method abo yak jogo she nazivayut metod pravoyi ruki Opis metodu Ye metod sho praktichno ne vikoristovuye dodatkovoyi pam yati dlya en div Okolicya fon Nejmana oblastej Cim zhe metodom mozhna shukati vihid z labirintu Uyavit sobi malyara yakij farbuye oblast tak shob ne opinitisya zatisnutim v kutku Pochatkovi kordoni ce chotiri pikselya yaki malyar rozglyadaye shob vibrati odnu z mozhlivih dij Osnovni mozhlivi stani Vsi 4 granichnih pikselya pofarbovani Tri granichnih pikselya pofarbovani Dva granichnih pikselya pofarbovani Odin granichnij piksel zafarbovanij Zhoden z granichnih pikseliv ne zafarbovanij Pri prodovzhenni kordonu vikoristovuyetsya metod pravoyi ruki Malyar obhodit oblast trimayuchi pravu ruku na stini kordoni oblasti i prosuvayetsya ne vidrivayuchi ruki U vipadku 1 malyar farbuye piksel na yakomu stoyav i zakinchuye algoritm zavershenij U vipadku 2 isnuye shlyah z oblasti nazovni Malyar farbuye piksel na yakomu stoyav i ruhayetsya cim shlyahom U vipadku 3 dva granichnih pikselya stvoryuyut smugu yaka yaksho mi pofarbuyemo potochnij piksel mozhe vidrizati nas vid usogo sho znahoditsya po yiyi inshu storonu Potribno zakripiti strilku sho vkazuye de mi zaraz i kudi divimosya shob yaksho mi kolis povernemosya na cej piksel mi mogli yiyi pobachiti Yaksho taka strilka vzhe namalovana mi yiyi zberigayemo i ruhayemosya dali za pravilom pravoyi ruki Strilka na pershomu dvohpikselnomu kordoni fiksuye de malyar pochav robotu i kudi zvidti pishov Yaksho malyar zustrichaye tu zh mitku ruhayuchis v tomu zh napryamku to vin rozumiye sho farbuvati cej kvadrat ruhayuchis u comu napryamku bezpechno pikseli na inshij storoni po yakomus poki ne vidomomu shlyahu budut dostupni dlya farbuvannya v majbutnomu Mitka znimayetsya i yiyi mozhna postaviti des she Yaksho zh malyar zustrichaye strilku sho vkazuye ne tudi kudi vin jde znachit vin projshov yakimos shlyahom sho povernuv jogo do mitki Cyu petlyu treba viklyuchiti Mitka zabirayetsya a malyar ruhayetsya u vkazanomu neyu napryami keruyuchis pravilom livoyi ruki Tak vin jde poki ne potrapit na peretin z ne mensh nizh troma pikselyami vidkritogo kordonu Ne vidrivayuchi livoyi ruki malyar shukaye prostij prohid sho skladayetsya z dvoh granichnih pikseliv Znajshovshi jogo vin farbuye cej piksel petlya rozrivayetsya i mozhna prodovzhuvati algoritm U vipadku 4 mi povinni pereviriti protilezhni zv yazani po 8 napryamam kuti pofarbovani voni chi ni Yaksho hocha b odin z cih dvoh kutiv pofarbovanij vihodit peretin bagatoh shlyahiv yaki mi zafarbuvati ne zmozhemo Yaksho obidva porozhni mozhemo pofarbuvati potochnij piksel i sliduvati dali za pravilom pravoyi ruki Algoritm daye vigrash v pam yati za rahunok prograshu za chasom Dlya oblastej prostoyi formi vin duzhe efektivnij ale v bilsh skladnih vipadkah bagato chasu vitrachayetsya na te shob vidstezhiti mezhi oblasti i perekonatisya sho vse mozhna zafarbuvati Persha komercijna realizaciya cogo algoritmu z yavilasya v 1981 roci na sistemi Vicom Image Processing vipushenoyi Vicom Systems Inc Takozh v cij sistemi buv prisutnij i klasichnij rekursivnij algoritm Algoritm anglijskoyu Ce realizaciya psevdokodu yakij vikonuye algoritm zalivki z fiksovanim vikoristannyam pam yati Zminni 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 Primitka usi napryamki front back left right rahuyutsya vidnosno potochnogo napryamku 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 LOOPMetod skanuvannya ryadkivAlgoritm mozhna priskoriti zalivayuchi vidrazu liniyami Zamist vkladannya v stek koordinat kozhnogo z mozhlivih majbutnih pikseliv rozglyadayutsya susidni ryadki ti sho vishe i ti sho nizhche i v nih viznachayutsya sumizhni segmenti yaki pri nastupnomu prohodi mozhna zaliti koordinati pochatok chi kinec vtiskuyutsya v stek U bilshosti vipadkiv ryadkovij algoritm na poryadok shvidshe popikselnogo algoritmu Jogo perevaga v tomu sho kozhen piksel pereviryayetsya tilki odin raz U vektornij graficiPrograma Inkscape versiyi 0 46 nadaye instrument buketnoyi zalivki sho viglyadaye yak zvichajna rastrova operaciya i v dijsnosti yiyi zastosovuye zobrazhennya vimalovuyetsya zastosovuyetsya zalivka vibranoyi oblasti i yiyi rezultat peretvoryuyetsya nazad u vektornij viglyad Pri comu vikoristovuyetsya koncepciya granichnih umov Povedinka pri velikih rozmirahZalivka u chotiroh napryamah yaka vikoristovuye chergu dlya zberigannya Zalivka u chotiroh napryamah yaka vikoristovuye stek dlya zberigannya Osnovna metodika vikoristovuyetsya dlya upravlinnya zalivkoyu i mozhe buti oriyentovana na danni abo na proces Pidhid sho oriyentuyetsya na danni mozhe vikoristovuvati abo chergu abo stek shob zberigati shlyah pikseliv yaki potrebuyut perevirki Pidhid sho oriyentuyetsya na proces maye vikoristovuvati stek Algoritm zalivki u chotiroh napryamah vikoristovuye sumizhnu tehniku i chergu yak misce dlya zberigannya pikseliv ta rombovidno zapovnyuyetsya Efektivnist dlya zalivki odnogo pikselya pereviryayutsya chotiri visim yaksho ruh ide u vosmi napryamkah Algoritm zalivki u chotiroh napryamah vikoristovuye sumizhnu tehniku i stek yak misce dlya zberigannya pikseliv z linijnoyu zalivkoyu Cej algoritm mozhe buti dobre vidno u starih 8 bitnih igrah sho buli stvoreni za dopomogoyu en Efektivnist dlya zalivki odnogo pikselya pereviryayutsya chotiri visim yaksho ruh ide u vosmi napryamkah PosilannyaAlgoritmi zalivki zobrazhen populyarno i z video 2 kvitnya 2015 u Wayback Machine Algoritmi zalivki bagatokutnikiv 2 kvitnya 2015 u Wayback Machine Algoritm zalivki zamknutogo konturu 2 kvitnya 2015 u Wayback Machine Gilyerme Polo C program to implement floodfill algorithm 4 connected boundary 9 travnya 2015 u Wayback Machine Sample implementations for recursive and non recursive classic and scanline flood fill 7 travnya 2015 u Wayback Machine by Lode Vandevenne Pol Hekbert Flash flood fill implementation 16 travnya 2015 u Wayback Machine Emanuele Feronato QuickFill An efficient flood fill algorithm 9 grudnya 2011 u Wayback Machine Dzhon R Shou Ce nezavershena stattya pro algoritmi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Cya stattya potrebuye dodatkovih posilan na dzherela dlya polipshennya yiyi perevirnosti Bud laska dopomozhit udoskonaliti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Zvernitsya na storinku obgovorennya za poyasnennyami ta dopomozhit vipraviti nedoliki Material bez dzherel mozhe buti piddano sumnivu ta vilucheno serpen 2017