Algoritmo flood fill

L'algoritmo Flood fill individua un punto all'interno dell'area e, a partire da quel punto, colora tutto quello che ha intorno fermandosi solo quando incontra un confine, ovvero un pixel di colore differente (alcuni programmi di grafica permettono di definire quanto/come differente).

L'algoritmo richiede 3 parametri: il pixel iniziale, il colore da sostituire ed il colore di riempimento. La formulazione più semplice è ricorsiva. Si individua un pixel qualsiasi appartenente all'area da colorare, si controllano i vicini e se hanno un colore uguale lo si cambia con quello scelto, altrimenti si prosegue.

Immaginando i pixels come nodi, possiamo vedere l'algoritmo come una funzione ricorsiva che prende come parametri un nodo (il pixel all'interno dell'area), un colore_prima (il colore dell'area) ed infine colore_nuovo, ovvero il colore con cui vogliamo riempire l'area.

Flood-fill (nodo, colore_prima, colore_nuovo):
 1. Se il colore di nodo è diverso da colore_prima, termina.
 2. Imposta il colore di nodo a colore_nuovo.
 3. Esegui Flood-fill (nodo ad ovest di nodo, colore_prima, colore_nuovo).
    Esegui Flood-fill (nodo a nord di nodo, colore_prima, colore_nuovo).
    Esegui Flood-fill (nodo ad est di nodo, colore_prima, colore_nuovo).
    Esegui Flood-fill (nodo a sud di nodo, colore_prima, colore_nuovo).
 4. Termina.

Il funzionamento può avvenire anche in modo non ricorsivo, inserendo i nodi da esaminare in un'apposita struttura dati ed esaminando i nodi uno per volta. Ecco un esempio di sviluppo non ricorsivo in Pascal, in questo caso è possibile usare una coda LIFO per mantenere le coordinate dei pixel ancora da processare.

Procedure FloodFill(xStart, yStart:integer; ColorePrima, ColoreRiempimento:TColore);
Var
  x, y : integer;
  xEst, xWest : integer;
  yNord, ySud : integer;
begin
  QueueInit;
  QueuePush(xStart, yStart);
  while (QueueCount > 0) do begin
    QueuePop(x, y);
    xWest := x;
    xEst := x;
    if (y > 0) then
      yNord := y - 1
    else 
      yNord := -1;
    if (y < ImageHeight -1) then
      ySud := y   1
    else 
      ySud := -1;
    while (xEst < ImageWidth -1) and (Pixel[xEst   1, y] = ColorePrima) do Inc(xEst);
    while (xWest > 0) and (Pixel[xWest - 1, y] = ColorePrima) do Dec(xWest);
    for x := xWest to xEst do begin
      Pixel[x, y] := ColoreRiempimento;
      if (yNord >= 0) and (Pixel[x, yNord] = ColorePrima) then QueuePush(x, yNord);
      if (ySud >= 0) and (Pixel[x, ySud] = ColorePrima) then QueuePush(x, ySud);
    end;
  end;
end; //FloodFill

Questo algoritmo non serve direttamente per riempire poligoni, intendendo poligoni come oggetti descritti come oggetti vettoriali cioè non come semplici insiemi di pixel. Ad esempio come elenco delle coordinate dei vertici. In questo caso si ricorre prima all'algoritmo di rasterizzazione di poligono.

Altri progetti

Wikimedia Commons contiene immagini o altri file sull'algoritmo Flood Fill

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica