Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

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

  1. 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.
  1. 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

  1. State the formula for x where an edge (x1,y1)-(x2,y2) crosses scan-line y.
  2. In scan-line filling, why do we use ymin inclusive and ymax exclusive for edges?
  3. 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?