Diffusion Fill Algorithm er en klassisk algoritme i datagrafikk som endrer fargen på et relatert sett med piksler med samme farge avgrenset av konturer. Det brukes ofte av rasterbildemanipuleringsprogrammer som Paint. Det finner også anvendelse i visse spill som Minesweeper , Puyo Puyo og Lumines for å bestemme hvilke elementer i spillbrettet som skal avsløres.
Diffusjonen fyllingen Algoritmen tar tre parametere for et gitt bilde: stillingen av utgangsbildeelement colcible ) og erstattet av farge ( colrep ). Algoritmen identifiserer alle piksler i bildet som er koblet til frøet ved en bane til målfargen og erstatter sistnevnte med erstatningsfargen. Det er flere måter å strukturere denne algoritmen på, men de bruker implisitt eller eksplisitt en stabel for å utføre beregningen.
Den rekursive formuleringen bruker implisitt en stabel.
Hvis bildet konvensjonelt består av firkantede eller rektangulære piksler , anser den 4-relaterte varianten de 4 naboene til en piksel som har en kant med sistnevnte til felles. Formuleringen av algoritmen er som følger:
remplissage4(pixel, colcible, colrep) début si couleur(pixel) = colcible alors couleur(pixel) ← colrep remplissage4(pixel au nord, colcible, colrep) remplissage4(pixel au sud, colcible, colrep) remplissage4(pixel à l'est, colcible, colrep) remplissage4(pixel à l'ouest, colcible, colrep) finsi finDen forrige rekursive formuleringen, hvis den har fordelen av å være intuitiv av sin formulering, er ofte ubrukt i praksis, spesielt i utførelsesmiljøer der samtalestabelen av funksjoner er sterkt begrenset eller redusert. Du bør da lage din egen stabel der pikslene som skal skannes lagres. Algoritmen for den 4-tilkoblede varianten er da følgende:
remplissage4(pixel, colcible, colrep) début Soit P une pile vide si couleur(pixel) ≠ colcible alors sortir finsi Empiler pixel sur P Tant que P non vide faire Dépiler n de P couleur(n) ← colrep si couleur(n nord) = colcible alors Empiler n nord sur P finsi si couleur(n sud) = colcible alors Empiler n sud sur P finsi si couleur(n est) = colcible alors Empiler n est sur P finsi si couleur(n ouest)= colcible alors Empiler n ouest sur P finsi fintantque finDe fleste implementeringer bruker en sløyfe som forplanter seg både "øst" og "vest" for å gjøre det enklere å håndtere stack. Algoritmen som brukes er da:
remplissage4(pixel, colcible, colrep) début Soit P une pile vide si couleur(pixel) ≠ colcible alors sortir de la fonction Empiler pixel sur P Tant que P non vide faire Dépiler n de P si couleur(n) = colcible alors w ← n e ← n Déplacer w vers l'ouest jusqu'à ce que couleur(w) ≠ colcible Déplacer e vers l'est jusqu'à ce que couleur(e) ≠ colcible Pour tout pixel p entre w et e Faire couleur(p) ← colrep si couleur(p nord) = colcible alors Empiler p nord sur P finsi si couleur(p sud ) = colcible alors Empiler p sud sur P finsi finpour finsi fintantque fin Feiing av linjeneAlgoritmen kan påskyndes ved å fylle ut rader direkte. I stedet for å stable hver nye potensielle piksel, er det bare å inspisere neste og forrige linje som vil bli farget i et fremtidig pass. Koordinatene til endene av segmentet som skal farges, stables deretter. I de fleste tilfeller er denne varianten av algoritmen raskere enn den pikselbaserte versjonen.