Loading AI tools
Van Wikipedia, de vrije encyclopedie
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.
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.
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) } }
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) } } }
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.