User Tools

Site Tools


Flood-fill is an algorithm which fills in a contiguous area. The basic algorithm maintains a stack of pixels to check, and for each pixel tested it pushes the neighbours onto the stack.

For this implementation in Javascript it doesn't make any difference, but for an optimised native flood-fill it would be important to test horizontal pixels first (push them onto the stack last). This is important for optimal memory access.

λ flood-fill

An optimised version of this algorithm maintains a stack of scanlines rather than pixels to test. This saves a lot of pixel tests over the basic algorithm. The scanline flood fill algorithm works by scanning a line, and adding ranges on the next/previous lines to a stack. For a shape with no loops or thin walls which are filled on both sides the scanline algorithm will only test each pixel once. It achieves this by skipping testing the range of pixels that the current line was filled from.

A rough outline of the algorithm is:

  1. Add the starting range [x, y] to a stack.
  2. While there is a range to fill:
    1. Extend the current range left and right.
    2. Add new ranges on the previous and next lines that overlap the current range to the stack. Skip testing the range of pixels that the current range was created from.

λ flood-fill_scanline

flood-fill.txt · Last modified: 2015/02/02 08:28 (external edit)