Overview
Flood Fill expands from a starting pixel to neighboring pixels that match a fill rule.
FoundationSource checked
Flood Fill
Fills a connected region starting from one seed point.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Image Processing
- Difficulty
- Beginner
- Family
- Region Traversal
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 2
- Code example
- Ready
- Visualization
- Ready
Core Concepts
pixel operationregion separationgraph representationtraversal orderregion traversalpixel neighborhoodlocal operationimage transform
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(a)
Average
O(a)
Worst
O(w h)
Space
O(w h)
When to Use
- Use it to find or recolor a connected region from a seed cell.
- Use it on grids, images, or graphs with a clear neighbor rule.
- Use BFS, DFS, or scanline variants depending on memory and performance needs.
When Not to Use
- Avoid recursive implementations on very large regions if stack depth is limited.
- Avoid it when the match rule is too noisy to define a coherent region.
- Avoid it when diagonal connectivity conventions are ambiguous.
What It Does
- Finds connected pixels
- Changes or labels a region
Use Cases
- Paint bucket tools
- Connected-component labeling
- Region selection
Inputs
- Image or grid
- Start position
- Match rule
Outputs
- Filled image or region mask
Pseudocode
- 1.Start from the seed pixel
- 2.Check whether the pixel matches the fill rule
- 3.Change or mark the pixel
- 4.Add matching neighbors to the worklist
- 5.Repeat until no matching neighbors remain
Canonical Example
- Input
- grid with connected zeros and seed at one zero cell
- Output
- the seed's connected zero-region marked
- Explanation
- The fill expands only through neighboring cells that match the original seed value.
Implementation Notes
- Use a queue or stack of cells to visit.
- Mark or change a cell before adding its neighbors.
- Check image bounds before reading neighbor values.
Common Pitfalls
- Not marking cells before pushing neighbors, which can revisit cells many times.
- Using 4-neighbor and 8-neighbor connectivity inconsistently.
- Failing to stop when the replacement value already equals the target value.
Interactive Mechanism Walkthrough
2D Grid Wavefront & TrajectoryShow a colored region expanding from a seed cell.
S
#
#
#
#
#
#
#
G
Step 1 of 5: Start from the seed pixel
grid-fillNotes
Flood fill is graph traversal over a grid with a domain-specific neighbor and match rule.
Sources (1)
What each reference supports for this entry.
Digital Image Processing
BookImage-processing textbook support for Flood Fill's pixel-neighborhood operations, filtering rules, and image-analysis role.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageFlood fill often uses BFS-style frontier expansion over grid cells.
Used byConnected Component Labeling
Connected component labeling can be implemented with flood-fill traversal.
Related Algorithms
Tags
Image ProcessingSegmentationGraphTraversal