Algoritm de umplere a inundațiilor

Această intrare sau secțiune despre programare nu citează sursele necesare sau cei prezenți sunt insuficienți . Puteți îmbunătăți această intrare adăugând citate din surse de încredere în conformitate cu liniile directoare privind utilizarea surselor .

Inundați cu 4 direcții

Algoritmul de umplere a inundațiilor identifică un punct din interiorul zonei și, începând din acel punct, colorează tot ceea ce îl înconjoară, oprindu-se numai atunci când întâlnește o margine, adică un pixel de altă culoare (unele programe grafice vă permit să definiți cât / ca diferit).

Algoritmul necesită 3 parametri: pixelul inițial, culoarea care trebuie înlocuită și culoarea de umplere. Cea mai simplă formulare este recursivă. Identificați orice pixel aparținând zonei de colorat, verificați vecinii și dacă au aceeași culoare, schimbați-o cu cea aleasă, altfel continuați.

Imaginând pixelii ca noduri, putem vedea algoritmul ca o funcție recursivă care ia ca parametri un nodo (pixelul din interiorul zonei), o colore_prima culoare (culoarea zonei) și în cele din urmă colore_nuovo , care este culoarea cu care doresc să umple zona.

 Flood-umplere (nod, color_first, color_new):
 1. Dacă culoarea nodului este diferită de first_color , terminați.
 2. Setați culoarea nodului la new_color.
 3. Efectuați Flood-fill (nod la vest de nod , color_first, color_new).
    Faceți Flood-fill (nod la nord de nod , first_color, new_color).
    Faceți Flood-fill (nod la est de nod , first_color, new_color).
    Faceți Flood-fill (nod la sud de nod , first_color, new_color).
 4. Termină.

Operația poate avea loc, de asemenea, într-un mod nerecursiv, prin inserarea nodurilor care urmează să fie examinate într-o anumită structură de date și examinarea nodurilor unul câte unul. Iată un exemplu de dezvoltare nerecursivă în Pascal, în acest caz este posibil să se utilizeze o coadă LIFO pentru a păstra coordonatele pixelilor încă de procesat.

 Proceduri FloodFill (xStart, yStart: integer; ColorePrima, ColoreFill: TColore);
Var
  x, y: întreg;
  xEst, xWest: întreg;
  yNord, ySud: întreg;
începe
  QueueInit;
  QueuePush (xStart, yStart);
  în timp ce (QueueCount> 0) începe
    QueuePop (x, y);
    xWest: = x;
    xEst: = x;
    dacă (y> 0) atunci
      yNorth: = y - 1
    altceva 
      yNorth: = -1;
    if (y <ImageHeight -1) atunci
      ySud: = y + 1
    altceva 
      ySud: = -1;
    în timp ce (xEst <ImageWidth -1) și (Pixel [xEst + 1, y] = Color Before) do Inc (xEst);
    în timp ce (xWest> 0) și (Pixel [xWest - 1, y] = ColorFirst) faceți Dec (xWest);
    pentru x: = xWest to xEst începe
      Pixel [x, y]: = Fill Color;
      dacă (yNorth> = 0) și (Pixel [x, yNord] = ColorFirst) atunci QueuePush (x, yNord);
      dacă (ySud> = 0) și (Pixel [x, ySud] = ColorFirst) atunci QueuePush (x, ySud);
    Sfârșit;
  Sfârșit;
Sfârșit; // FloodFill

Acest algoritm nu servește direct pentru a umple poligoane, adică poligoane ca obiecte descrise ca obiecte vectoriale, adică nu ca simple seturi de pixeli. De exemplu, ca listă a coordonatelor vârfurilor. În acest caz, apelăm mai întâi la algoritmul de rasterizare a poligonului .

Alte proiecte

• Wikimedia Commons conține imagini sau alte fișiere ale algoritmului Flood Fill

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică