Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 50 ยท Polygons and Filling

Flood Fill and Boundary Fill

Learn flood fill and boundary fill: 4- and 8-connectivity, why recursion overflows, the stack-based version, scanline seed fill and a live paint bucket.

The scanline algorithm fills a shape from its geometry: it needs the polygon's vertices. A paint program has no polygon. It has only a grid of colored pixels, and you click somewhere and expect the enclosed area to change color. Filling by looking at the pixels themselves is the job of seed fill algorithms: you give them a starting pixel (the seed), and they spread outward from it.

There are two classic variants, and they differ in how they decide where to stop.

  • Flood fill replaces a connected region of one interior color. It starts at the seed, remembers the color found there (the target color), and spreads to every connected pixel with that same color, changing each to the new color. This is the paint bucket tool.
  • Boundary fill spreads until it meets a boundary color. It paints every pixel that is neither the boundary color nor already the new color. The interior may contain many colors; the border is what matters.

Use flood fill when the region has a uniform color that differs from its surroundings, and boundary fill when the outline has a known color but the inside is mixed.

Connectivity: 4 or 8 neighbors

"Connected" needs a definition. Each pixel has eight surrounding pixels, and you have to decide which of them count as neighbors.

  • 4-connected: only the pixels directly above, below, left and right. Movement is like a rook.
  • 8-connected: also the four diagonal neighbors. Movement is like a king.
flowchart TB
  subgraph Four["4-connected"]
    direction TB
    N4["up"] --- C4(("pixel"))
    C4 --- S4["down"]
    W4["left"] --- C4
    C4 --- E4["right"]
  end
  subgraph Eight["8-connected: the same four, plus"]
    direction TB
    D1["up-left"] --- C8(("pixel"))
    D2["up-right"] --- C8
    D3["down-left"] --- C8
    D4["down-right"] --- C8
  end

A 4-connected fill moves along the sides of pixels; an 8-connected fill may also slip diagonally.

The choice has a visible consequence. A boundary made of diagonal pixels, like the edge of a diamond, is a closed wall for a 4-connected fill, because the fill can never squeeze between two pixels that touch only at their corners. An 8-connected fill sees those corner contacts as a path, so it leaks straight through. The rule of thumb: use a 4-connected fill for boundaries drawn with 8-connected lines (like Bresenham lines), so the fill stays inside. In general, pair an 8-connected boundary with a 4-connected interior.

The recursive version

The textbook definition is short enough to fit in a few lines. To fill a pixel: if it is fillable, color it, then fill its neighbors.

JavaScript
function fillRecursive(grid, w, h, x, y, canFill, color) {
  if (x < 0 || y < 0 || x >= w || y >= h) return;
  if (!canFill(grid[y * w + x])) return;
  grid[y * w + x] = color;
  fillRecursive(grid, w, h, x + 1, y, canFill, color);
  fillRecursive(grid, w, h, x - 1, y, canFill, color);
  fillRecursive(grid, w, h, x, y + 1, canFill, color);
  fillRecursive(grid, w, h, x, y - 1, canFill, color);
}

The predicate canFill is what distinguishes the two algorithms:

JavaScript
// Flood fill: only pixels that still have the target color.
const canFlood = (v) => v === target;
// Boundary fill: anything except the border color and the new color.
const canBoundary = (v) => v !== borderColor && v !== newColor;

(If the new color equals the target color in flood fill, nothing would ever change and the recursion would loop forever, so the real function must return early in that case.)

The recursion has a serious weakness. The fill goes as deep as the longest chain of pixels it can follow before backing up. In an empty region that chain can visit nearly every pixel before the first call returns, so the stack depth grows with the area. A JavaScript engine allows roughly ten thousand nested calls, and many languages allow fewer. A 400 x 400 region has 160,000 pixels, and the recursion crashes. The next example demonstrates the crash and shows that the stack-based and span-based versions handle the same job without trouble.

The stack-based version

The cure is to manage the pending work yourself. Replace recursion by an explicit stack (a Uint32Array or array of positions) that lives on the heap, which is limited only by memory:

JavaScript
function fillStack(grid, w, h, sx, sy, canFill, color) {
  const stack = [[sx, sy]];
  while (stack.length > 0) {
    const [x, y] = stack.pop();
    if (x < 0 || y < 0 || x >= w || y >= h) continue;
    if (!canFill(grid[y * w + x])) continue;
    grid[y * w + x] = color;
    stack.push([x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]);
  }
}

Each pixel is checked when it is popped, not when it is pushed, so a pixel pushed several times is simply skipped later. The stack can still hold a few times more entries than there are pending pixels, but it never overflows the call stack.

JS Recursion overflows, a stack does not

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Both heap-based versions fill all 160,000 pixels. Compare the peak values: the span version keeps far fewer entries because it handles a whole row segment per entry.

Scanline (span) seed fill

The pixel-by-pixel stack still does a lot of work per pixel: four pushes and four checks. Most pixels in a region are inside long horizontal runs, so we can process whole runs at once. This is the scanline seed fill (also called span fill):

  1. Pop a seed from the stack. If it is no longer fillable, skip it.
  2. Move left from the seed until the next pixel is not fillable, and likewise to the right. That gives a horizontal span left..right.
  3. Fill the entire span.
  4. Look at the row above and the row below, over left..right. Every time a fillable run begins there, push one seed for it.
  5. Repeat until the stack is empty.
flowchart TB
  A["Push seed"] --> B["Pop seed"]
  B --> C{"Still fillable?"}
  C -->|no| B
  C -->|yes| D["Extend left and right<br/>to find the span"]
  D --> E["Fill the span"]
  E --> F["Scan the row above and below<br/>push one seed per fillable run"]
  F --> G{"Stack empty?"}
  G -->|no| B
  G -->|yes| H["Done"]

Span fill touches each pixel about twice (fill and scan) instead of five times, and keeps its stack short.

For 8-connected filling, the scan of the rows above and below extends one pixel further on each side (left - 1 to right + 1), because diagonal neighbors count.

A live paint bucket

The grid below is a tiny image, magnified. It contains a closed rectangle drawn with black wall pixels, a red circle outline inside it, and on the right a diamond whose wall is made of diagonal pixels. Click anywhere to start a fill.

  • Switch between flood fill (replace the clicked color) and boundary fill (stop only at black walls). Clicking inside the red circle shows the difference: flood fill treats the red ring as a wall of its own, while boundary fill paints over the ring.
  • Switch between 4 and 8 connectivity. Fill the inside of the diamond with 8-connectivity and watch the fill escape through its diagonal wall.
  • Switch the method. The result is identical, but the statistics line shows how much memory each method used (recursion depth or peak stack size).
Paint bucket: flood fill, boundary fill, 4 or 8 neighbors

Try this experiment: choose 8, click inside the diamond, and see the fill leak into the big rectangle. Press Reset, switch to 4, and click the diamond again; now the wall holds.

Practical notes

  • Which pixel formats? The demo stores palette indices. A real image editor compares RGBA values, usually with a tolerance (a distance threshold), because antialiased edges contain many near-identical colors and an exact comparison would leave a halo.
  • Same-color seeds. Always check that the new color differs from the target in flood fill, otherwise the fill never terminates (or, with a visited array, does nothing).
  • Bounds. Check x, y against the image size before reading, or the fill walks off the edge of the buffer.
  • Visited marks. Changing the pixel to the new color doubles as the visited mark. If you want to fill with a pattern or a gradient, keep a separate visited array, since the pattern may contain the target color.
  • Performance. Span fill is the usual choice in software. Browsers, GPUs and editors use variants of it, or they work in tiles.
  • Geometry or pixels? If you have the polygon, scanline filling is exact and resolution-independent. Seed fill is what you use when only pixels exist.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the main difference between flood fill and boundary fill?

    Flood fill's rule is 'same as the seed color'. Boundary fill's rule is 'not the border color', so the interior can contain several colors.
  2. 2. A closed shape is outlined with a one-pixel diagonal wall. Which fill is likely to leak through it?

    An 8-connected fill may step diagonally between two wall pixels that touch only at their corners. A 4-connected fill cannot.
  3. 3. Why does the recursive flood fill crash on large regions?

    Each nested call stays on the call stack until the fill backs up, so depth can reach nearly the region's area.
  4. 4. What does scanline seed fill push onto its stack?

    After filling a span, it scans the adjacent rows and pushes a single seed for each contiguous fillable run, which keeps the stack small.
  5. 5. Why do image editors compare colors with a tolerance in their paint bucket tool?

    An exact comparison would stop at every slightly different pixel and leave a halo of unfilled pixels along soft edges.

Summary

  • Seed fills color a region starting from a pixel, using only the pixel data.
  • Flood fill replaces the seed's color; boundary fill stops at a border color.
  • 4-connected fills move through sides only; 8-connected fills also cross diagonals and can leak through diagonal walls.
  • A recursive fill is concise but its depth can approach the region's area, so it overflows the call stack on large regions.
  • A stack on the heap removes that limit; scanline span fill also cuts the work and the stack size by handling a whole run at a time.
  • Real tools add a color tolerance, bounds checks and extra bookkeeping for patterns.

Next: Triangle Rasterization and Barycentric Coordinates.