Polygon filling: flood fill, seed fill and scan-line fill
Clear, exam-focused notes on polygon filling: flood/seed-fill (recursive and non-recursive) and scan-line fill, with definitions, derivations, formulas, worked examples (including a runnable C++ flood-fill), common mistakes and quick self-test.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Polygon filling is used anytime a renderer must decide which pixels lie inside a polygon to colour them: rasterising GUI shapes, filling model surfaces in a software renderer (before z-buffering), texture painting and simple 2D CAD/graphics tools. Engineers implement efficient, robust fill routines in graphics libraries, game engines and CAD/CAM tools.
Key ideas
Start with definitions and simple principles built from first principles.
Pixel: the smallest addressable element on a raster display. We treat pixels as points at integer coordinates (x, y) or as unit squares centred on integer coordinates depending on convention; here we assume pixel centres at integer (x, y).
Polygon: a planar closed chain of straight line segments (edges) joining vertices. We assume a polygon is simple (non-self-intersecting) unless stated otherwise.
Inside test: a rule to decide whether a point is inside a polygon. Two common rules: even-odd (parity) rule and non-zero winding rule. The even-odd rule: cast a ray from the point and count edge intersections; if odd -> inside, even -> outside. The non-zero rule sums signed crossings; result non-zero -> inside.
Seed fill (flood fill): an algorithm that starts from a seed point known to be inside the region and spreads to neighbouring pixels that satisfy a membership test (same old colour or not a boundary), marking them until region is exhausted. Flood-fill is local, does not require polygon edges to be sorted.
4-connected vs 8-connected: connectivity defines neighbours. 4-connected uses up, down, left, right. 8-connected includes diagonals. Choice affects filled result near thin boundaries.
Boundary fill: a variant of seed fill which grows until it reaches boundary pixels of a specified boundary colour.
Scan-line fill: a global algorithm that fills polygons by processing horizontal lines (scan-lines). For each scan-line y, compute intersections of polygon edges with that y, sort the intersection x coordinates, and fill between pairs of intersections according to the chosen inside rule (normally even-odd). Scan-line is efficient because it processes one row at a time and reduces repeated work using an active edge table.
Exact statement (scan-line algorithm assumptions):
- Polygon is simple (no self-intersections) or has been decomposed into simple parts.
- Edges are closed segments; horizontal edges are handled by a consistent rule (count a vertex only at its lower endpoint, i.e., include ymin and exclude ymax, to prevent double-counting).
Derivation (edge intersection formula — what to draw):
- Draw coordinate axes. Draw an arbitrary edge with endpoints (x1, y1) and (x2, y2). Draw a horizontal scan-line at y. Label intersection point with x.
- By similar triangles or linear interpolation, intersection x satisfies x = x1 + (y - y1) * (x2 - x1) / (y2 - y1) provided y2 ≠ y1 (non-horizontal edge). This is the formula used to compute where an edge crosses a scan-line.
Active Edge Table (AET) construction (what to draw):
- For each edge, draw a small table row: ymin (lower integer y), ymax (upper integer y), x_at_ymin (initial x), inverse slope 1/m = (x2 - x1)/(y2 - y1). Sort edges into buckets by ymin (the bucket for scan-line y = ymin).
- For each scan-line y from global ymin to ymax-1: insert bucketed edges whose ymin == y into AET, remove edges with ymax == y, sort AET by current x, pair successive intersections (x0,x1),(x2,x3),... and fill integer x from ceil(x_left) to floor(x_right) for each pair. Alternatively, use a left-inclusive, right-exclusive rule: fill x from ceil(x_left) to ceil(x_right)-1 to avoid double-painting shared edges; use one rule consistently. After processing, update x := x + 1/m for each edge (move to next scan-line).
Seed-fill recursion principle (what to draw):
- Starting at seed (xs, ys) with target colour C_old and replacement C_new, recursively (or with stack) visit neighbouring pixels N; if colour == C_old (or not boundary), set to C_new and recurse on neighbours. Base case: pixel out of bounds or not target colour.
Edge cases to note (draw small sketches in exam): overlapping edges, horizontal edges, vertices shared by two edges (use endpoint rules), thin regions (<1-pixel width), choice of connectivity and boundary colour.
Formulas
x = x1 + (y - y1) * (x2 - x1) / (y2 - y1) — x coordinate where edge (x1,y1)-(x2,y2) intersects horizontal scan-line at y. Symbols: x,x1,x2,y,y1,y2 are pixel coordinates (unit: pixels). Applies when y1 ≠ y2.
1/m = (x2 - x1) / (y2 - y1) — inverse slope used to advance x each scan-line; units: pixels per scan-line.
fill_x_start = ceil(x_left) fill_x_end = floor(x_right) — integer pixel x range to fill between intersections on a scan-line (pixels inclusive). Units: pixels. Alternatively, many implementations use right-exclusive ranges: fill integer x in [ceil(x_left), ceil(x_right)) to avoid double-filling at shared edges; choose and apply one convention consistently.
For seed/flood-fill implementations: recursion depth ~ area of region; use an explicit stack to avoid recursion overflow in large images.
C++ syntax to remember (common in implementations):
std::vector, std::sort, std::pair<int,int>, range-based for, lambda comparison, std::stack or std::deque for BFS/DFS, updating x by x += invSlope.
Worked examples
- Scan-line numeric example (triangle) Polygon vertices (counter-clockwise): V0(2,2), V1(6,5), V2(2,8). Use integer scan-lines y = 2..7 (stop before ymax = 8). Show steps and filled pixels. Steps:
- Edges: E0 V0->V1: (2,2)-(6,5); y-range [2,5). E1 V1->V2: (6,5)-(2,8); y-range [5,8). E2 V2->V0: (2,8)-(2,2); y-range [2,8).
- Compute inverse slopes: E0: 1/m = (6-2)/(5-2) = 4/3 ≈ 1.3333 E1: 1/m = (2-6)/(8-5) = -4/3 ≈ -1.3333 E2: 1/m = (2-2)/(8-2) = 0
- Process scan-lines y = 2..7: y=2: active edges where ymin==2 -> E0 (x_at_ymin=2), E2 (x_at_ymin=2). AET x values [2,2]. Pairs: (2,2) -> fill ceil(2) to floor(2) => x=2. Mark pixel (2,2). Update x: E0 x+=1.3333 -> 3.3333, E2 x+=0 -> 2 y=3: AET E0(x=3.3333), E2(x=2). Sorted: [2,3.3333]. Fill ceil(2)=2 to floor(3.3333)=3 => x=2,3. Mark (2,3),(3,3). Update x: E0 x-> 4.6666, E2 x->2 y=4: AET [2,4.6666] => fill x=2..4 => (2,4),(3,4),(4,4). Update x: E0 x->6.0, E2 x->2 y=5: At y==5, remove edges with ymax==5 (E0). Add edges with ymin==5 (E1 x_at_ymin=6). Now AET E2(x=2), E1(x=6). Sorted [2,6] -> fill x=2..6 => (2,5),(3,5),(4,5),(5,5),(6,5). Update x: E2->2, E1 x+=-1.3333 -> 4.6667 y=6: AET [2,4.6667] -> fill x=2..4 => (2,6),(3,6),(4,6). Update x: E2->2, E1->3.3333 y=7: AET [2,3.3334] -> fill x=2..3 => (2,7),(3,7). Stop at y=8 (ymax). Final filled pixels listed above. Bold final answer: filled pixels for each row (y increasing): y=2:{(2,2)}; y=3:{(2,3),(3,3)}; y=4:{(2,4),(3,4),(4,4)}; y=5:{(2..6,5)}; y=6:{(2..4,6)}; y=7:{(2,7),(3,7)}. This is the expected triangular rasterisation.
- C++ program: recursive flood-fill (seed-fill) on small grid This program reads a small grid of characters '.' (background) and '#' (boundary), a seed coordinate (row, col), and replacement character, and performs 4-connected flood fill replacing '.' with replacement until bounded by '#'. It prints the grid after fill. Compilation: g++ -std=c++17 floodfill.cpp -o floodfill
Code:
#include <bits/stdc++.h>
using namespace std;
int R, C;
vector<string> G;
int dr[4] = {-1,1,0,0};
int dc[4] = {0,0,-1,1};
void flood(int r,int c,char oldc,char newc){
if(r<0||r>=R||c<0||c>=C) return;
if(G[r][c] != oldc) return;
G[r][c] = newc;
for(int k=0;k<4;k++) flood(r+dr[k], c+dc[k], oldc, newc);
}
int main(){
// sample input hard-coded for clarity
R = 6; C = 8;
G = {
"########",
"#......#",
"#..##..#",
"#..##..#",
"#......#",
"########"
};
int sr = 2, sc = 2; // seed inside region (0-based row,col)
char newc = 'o';
char oldc = G[sr][sc];
flood(sr, sc, oldc, newc);
for(auto &row: G) cout << row << "\n";
return 0;
}
Sample input: (program uses embedded grid; no stdin required) Exact output:
########
#oooooo#
#oo##oo#
#oo##oo#
#oooooo#
########
Bold final answer: the grid printed above shows all interior '.' replaced by 'o' in the single chamber; note that the '##' barrier does not isolate a separate chamber here, so the fill reaches both sides via rows 1 and 4.
Notes on the program: recursion depth here is small; in large images prefer an explicit stack/queue or span-fill variant to avoid stack overflow. Also guard against newc == oldc to avoid infinite recursion in this implementation.
Common mistakes
- Using floating-point x but not using ceil/floor consistently; rounding errors can omit boundary pixels.
- Confusing 4- vs 8-connectivity in seed-fill — exams may expect you to state which connectivity you assumed.
- Using recursive flood-fill on large regions causing stack overflow; forget to mention stack limit.
- Assuming polygons can be filled correctly without decomposing self-intersecting polygons.
For your exam
Question types you will see: definitions (seed-fill, boundary-fill, active edge table), short notes (compare scan-line vs seed-fill), derivations (derive edge intersection formula), step-by-step algorithms (show AET updates for one scan-line), numericals (fill a small polygon, list filled pixels), and small programs (implement flood-fill or give pseudo-code for scan-line). Full-marks answers include: clear assumptions (simple polygon, coordinate convention), diagrams with vertices and a sample scan-line, explicit step numbering, handling of special cases (horizontal edges, vertices), and final filled pixel list or correct code with sample I/O.
Quick check
- State the formula for x where an edge (x1,y1)-(x2,y2) crosses scan-line y.
- In scan-line filling, why do we use ymin inclusive and ymax exclusive for edges?
- Which is safer for large fills: recursive flood-fill or stack-based flood-fill? Why?
Answers: 1) x = x1 + (y - y1)*(x2 - x1)/(y2 - y1). 2) To avoid double-counting intersections at shared vertices and ensure each pixel row is filled exactly once. 3) Stack-based (explicit stack/queue) is safer because recursion can overflow for large regions; iterative methods control memory and avoid system recursion limits.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?