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.
- Wikimedia Commons contiene immagini o altri file sull'algoritmo Flood Fill
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.