Floodfill-algoritme

Het floodfill-algoritme is een algoritme dat het gebied bepaalt dat verbonden is met een bepaalde plek in een multi-dimensionale array. Het wordt gebruikt in de vulgereedschappen in tekenprogramma's, zoals Paint, om te bepalen welk gedeelte met een kleur gevuld moet worden en in bepaalde computerspellen, zoals Mijnenveger, om te bepalen welke gedeelten weggehaald moeten worden.

Floodfill-algoritme met 4 buren.

Floodfill-algoritme met 8 buren.

Het algoritme

Het algoritme heeft drie parameters: een beginpositie, een gekozen kleur en een vervangende kleur. Het algoritme bekijkt alle posities in de array die met de gekozen kleur verbonden zijn met de beginpositie en het vervangt deze door de vervangende kleur. Het algoritme kan op allerlei manieren geïmplementeerd worden.

Recursieve implementatie

Hieronder volgt pseudocode voor enkele recursieve implementaties in twee dimensies. De eerste versie gebruikt vier buren, de tweede versie gebruikt acht buren om het gebied te vullen. Het algoritme kan eenvoudig gegeneraliseerd worden naar meer dimensies door ervoor te zorgen dat men bij de recursieve aanroepen alle naburige locaties onderzoekt.

floodfill(x, y, gekozenkleur, vervangkleur)
{
    if (kleur(x, y) == gekozenkleur)
    {
        veranderkleur(x, y, vervangkleur)

        floodfill(x, y + 1, gekozenkleur, vervangkleur)
        floodfill(x, y - 1, gekozenkleur, vervangkleur)
        floodfill(x + 1, y, gekozenkleur, vervangkleur)
        floodfill(x - 1, y, gekozenkleur, vervangkleur)
    }
}

floodfill(x, y, gekozenkleur, vervangkleur)
{
    if (kleur(x, y) == gekozenkleur)
    {
        veranderkleur(x, y, vervangkleur)

        floodfill(x, y + 1, gekozenkleur, vervangkleur)
        floodfill(x, y - 1, gekozenkleur, vervangkleur)
        floodfill(x + 1, y, gekozenkleur, vervangkleur)
        floodfill(x - 1, y, gekozenkleur, vervangkleur)
        floodfill(x + 1, y + 1, gekozenkleur, vervangkleur)
        floodfill(x + 1, y - 1, gekozenkleur, vervangkleur)
        floodfill(x - 1, y + 1, gekozenkleur, vervangkleur)
        floodfill(x - 1, y - 1, gekozenkleur, vervangkleur)
    }
}

Stack-gebaseerde implementatie

De volgende implementatie maakt gebruik van een expliciete stack:

floodfill(x, y, gekozenkleur, vervangkleur)
{
    stack.push(x, y)

    while (stack is niet leeg)
    {
        (x, y) = stack.pop

        if (kleur(x, y) == gekozenkleur)
        {
            veranderkleur(x, y, vervangkleur)

            stack.push(x, y + 1)
            stack.push(x, y - 1)
            stack.push(x + 1, y)
            stack.push(x - 1, y)
        }
    }
}