Fill (uneori specificat prin „metoda flod”, din engleza flood fill ) este un algoritm care determină zona „asociată” cu un anumit element dintr-o matrice multidimensională (de obicei, aceasta este o matrice bidimensională de pixeli bitmap ). Un algoritm este utilizat în programele de grafică pentru a determina zona care trebuie umplută cu o anumită culoare .
Algoritmul are trei intrări: un element de pornire, o culoare de înlocuire și o culoare de umplere. Toate elementele matricei asociate cu calea de pornire a culorii înlocuite sunt găsite și revopsite în culoarea de umplere. Există o mulțime de opțiuni de implementare, dar toate folosesc o coadă sau o stivă într-un fel sau altul . Pseudocodul celui mai simplu algoritm recursiv , în care conectivitatea într-o matrice bidimensională este determinată în 4 direcții:
Umplere (element, culoare de înlocuire, culoare de umplere): 1. Dacă culoarea este articolul și nu culoarea de înlocuire , returnați. 2. Setați culoarea elementului a pentru a umple culoarea . 3. Umpleți (pasați spre vest de elementul a, înlocuiți culoarea , umpleți culoarea ). Umpleți (pasați spre est de elementul a, înlocuiți culoarea , umpleți culoarea ). Umpleți (pasați spre nord de elementul a, înlocuiți culoarea , umpleți culoarea ). Umpleți (pasați spre sud de la elementul a, înlocuiți culoarea , umpleți culoarea ). {pentru conectivitate în 8 direcții - încă patru apeluri diagonale} 4. Întoarcerea.Implementarea de mai sus este ușor de înțeles, dar practic nu se aplică în cazurile în care profunzimea recursiunii este strict limitată (de exemplu, în aplicațiile Java ) .
Următorul pseudocod arată o implementare bazată pe utilizarea explicită a cozii. Nu este foarte eficient, dar poate fi codificat rapid , nu folosește stiva și este ușor de depanat :
Umplere (element, culoare de înlocuire, culoare de umplere): 1. Atribuiți lui Q o coadă goală. 2. Dacă culoarea articolului nu este o culoare de înlocuire , returnați. 3. Așezați un element la capătul lui Q . 4. Atâta timp cât Q nu este gol: 5. Atribuiți n primul element al lui Q 6. Dacă culoarea n este culoarea de înlocuire , setați-o la culoarea de umplere . 7. Împingeți primul element din Q 8. Dacă culoarea elementului la vest de n este culoarea de înlocuit : 9. Setați culoarea acestui element la culoarea de umplere 10. Plasați acest element la sfârșitul Q {11 - 19. La fel pentru alți vecini} 20. Întoarcerea.Cele mai practice tehnici optimizează utilizarea stivei sau a cozii prin introducerea unei bucle în direcțiile „vest” și „est”:
Umplere (element, culoare de înlocuire, culoare de umplere): 1. Atribuiți lui Q o coadă goală. 2. Dacă culoarea articolului nu este o culoare de înlocuire , returnați. 3. Plasați un element în Q . 4. Pentru fiecare N dintre elementele lui Q : 5. Dacă culoarea N este culoarea de înlocuire : 6. Atribuiți w și e același element ca N . 7. Deplasați w spre vest până când culoarea lui w este diferită de culoarea „culoare de înlocuire ”. 8. Deplasați e spre est până când culoarea e este diferită de „ culoarea de înlocuire ”. 9. Dați tuturor elementelor dintre w și e o culoare de umplere . 10. Pentru fiecare n între w și e : 11. Dacă culoarea elementului la nord de n este culoarea de înlocuire , puneți acel element în Q. Dacă culoarea elementului este sub - n - culoarea care trebuie înlocuită , puneți acel element în Q. 12. Continuați bucla până când există elemente în Q. 13. Întoarcerea. {desigur, în alin. 7, 8 și 11 pot întâlni marginile matricei}Dacă algoritmul este scris pentru a folosi o matrice separată pentru a stoca forma zonei, aceasta va permite generalizarea acestuia în cazul umplerii „fuzzy”, când elementele pot diferi de cel specificat inițial în anumite limite. Utilizarea acestei matrice suplimentare ca canal alfa vă permite să creați o tranziție lină la granițele dintre zonele umplute și cele neumplute.
Există o metodă care practic nu utilizează memorie suplimentară pentru regiunile conectate pe 4 căi (vezi cartierul von Neumann ). În același mod, este posibil să cauți o cale de ieșire din labirint . Imaginați-vă un pictor care pictează o zonă fără a fi ciupit de partea vopsită din colț. Limitele inițiale sunt patru pixeli pe care pictorul consideră că selectează una dintre acțiunile posibile. Principalele stări posibile:
La extinderea graniței se folosește metoda mâinii drepte. Pictorul se plimbă prin zonă cu mâna dreaptă pe „perete” (limita zonei) și înaintează fără să-și ia mâna.
În cazul 1, pictorul pictează pixelul pe care stătea și zboară departe (algoritmul finalizat).
În cazul 2, există o potecă din regiune spre exterior. Pictorul pictează pixelul pe care stătea și se mișcă pe acea cale.
În cazul 3, cei doi pixeli de margine creează o dungă care, dacă colorăm pixelul curent, ne poate tăia de tot ce se află pe cealaltă parte a acestuia. Trebuie să reparăm „săgeata” care indică unde ne aflăm acum și unde căutăm, astfel încât, dacă ne întoarcem vreodată la acest pixel, să-l putem vedea. Dacă o astfel de săgeată este deja desenată, o salvăm și mergem mai departe conform regulii mâinii drepte.
Săgeata de pe primul chenar de doi pixeli fixează locul unde pictorul a început lucrul și unde a plecat de acolo. Dacă pictorul întâlnește același semn în timp ce se mișcă în aceeași direcție, atunci el înțelege că este sigur să picteze acest pătrat în timp ce se mișcă în acea direcție: pixelii de pe cealaltă parte de-a lungul unei căi încă necunoscute vor fi disponibili pentru pictură în viitor. Eticheta este îndepărtată și poate fi pusă în altă parte.
Dacă pictorul întâlnește o săgeată care nu indică încotro merge, atunci a trecut printr-o potecă care l-a readus la semn. Această buclă trebuie eliminată. Se îndepărtează semnul, iar pictorul se mișcă în direcția indicată de acesta, ghidat de regula mâinii stângi . Merge așa până când atinge o intersecție (cu cel puțin trei pixeli de margine deschisă). Fără să ridice mâna stângă, pictorul caută o trecere simplă (formată din doi pixeli de limită). După ce l-a găsit, pictează acest pixel; bucla este întreruptă și algoritmul poate fi continuat.
În cazul 4 trebuie să verificăm unghiurile opuse în 8 direcții conectate pentru a vedea dacă sunt colorate sau nu. Dacă cel puțin unul dintre aceste două colțuri este colorat, obținem o intersecție a mai multor căi, pe care nu le putem colora. Dacă ambele sunt goale, putem colora pixelul curent și putem urma regula mâinii drepte.
Algoritmul oferă un câștig în memorie datorită unei pierderi de timp. Pentru zonele de formă simplă este destul de eficient, dar în cazuri mai complexe se petrece mult timp urmărind limitele zonei și asigurându-se că totul poate fi vopsit.
Prima implementare comercială a acestui algoritm a apărut în 1981 pe sistemul Vicom Image Processing lansat de Vicom Systems, Inc. Tot în acest sistem a existat un algoritm recursiv clasic.
Algoritmul poate fi accelerat prin completarea cu linii simultan. În loc de a stivui fiecare dintre posibilii pixeli viitori, sunt luate în considerare rândurile adiacente (unul deasupra și unul dedesubt), iar în ele se determină segmente adiacente, care pot fi completate în următoarea trecere; coordonatele (fie de început, fie de sfârșit) sunt împinse pe stivă. În cele mai multe cazuri, algoritmul linie cu linie este cu un ordin de mărime mai rapid decât cel pixel cu pixel. Avantajul său este că fiecare pixel este verificat o singură dată.
Inkscape versiunea 0.46 oferă un instrument de umplere „cu găleată” care arată ca o operațiune normală de bitmap și îl folosește de fapt: imaginea este desenată, umplerea zonei selectate este aplicată și rezultatul este convertit înapoi în curbe . În acest caz, se utilizează conceptul de condiții la limită .