Example — Scan Line Polygon Fill for a

Triangle
Triangle Vertices:

A(2, 2), B(6, 8), C(10, 2)

This forms a triangle with a horizontal base from (2,2) to (10,2) and top vertex at (6,8):
B(6,8)
/\
/ \
/____\
A(2,2) C(10,2)

1. Edge Information (Edge Table, ET)

Edge y_min y_max x_at_ymin 1/m (inverse Comment
slope)

AB 2 8 2 +0.6667 rising left

edge

BC 2 8 10 -0.6667 falling right

edge

CA 2 2 — — horizontal →
ignored

2. Scan Line Processing (Active Edge Table)

Formula used for intersections: x(y) = x_ymin + (y − y_min) × (1/m)

y Active edges x(AB) x(BC) Fill between Integer pixels

(x₁,x₂)

2 AB, BC 2.000 10.000 [2.0, 10.0] 2..10

3 AB, BC 2.667 9.333 [2.667, 9.333] 3..9

4 AB, BC 3.333 8.667 [3.333, 8.667] 4..8

5 AB, BC 4.000 8.000 [4.0, 8.0] 4..8

6 AB, BC 4.667 7.333 [4.667, 7.333] 5..7

7 AB, BC 5.333 6.667 [5.333, 6.667] 6

8 AB, BC 6.000 6.000 [6.0, 6.0] 6

3. Explanation
At y = 2, both edges start → fill from 2 to 10.
As y increases, x on AB moves right (increasing), x on BC moves left (decreasing).
Filled region shrinks gradually until both meet at the top vertex (6,8).

4. Visual Representation
B(6,8)
/\
/##\
/####\
/######\
/########\
A(2,2)----------C(10,2)

5. Summary Table
Scanline Continuous Interval Pixels Filled

y=2 [2, 10] 2–10

y=3 [2.67, 9.33] 3–9

y=4 [3.33, 8.67] 4–8

y=5 [4, 8] 4–8

y=6 [4.67, 7.33] 5–7

y=7 [5.33, 6.67] 6

y=8 [6, 6] 6
The Scan Line Algorithm is a fundamental computer graphics algorithm used primarily for polygon
filling — determining which pixels lie inside a polygon and should be colored (or shaded).

Imagine scanning a polygon horizontally line by line (scan lines) from top to bottom.

For each scan line, the algorithm finds where that line intersects the polygon’s edges and fills the
pixels between intersection points that are inside the polygon.

Key Steps of the Scan Line Algorithm

1. Input:

A polygon defined by its vertices (x₁, y₁), (x₂, y₂), …, (xₙ, yₙ).

---

2. Build an Edge Table (ET):

For each polygon edge, record:

`y_min`: the smaller y-coordinate of the edge

`y_max`: the larger y-coordinate of the edge

`x`: the x-coordinate corresponding to `y_min`

`1/m`: the inverse slope of the edge (used to update x per scan line)

Edges are grouped by their `y_min` value (the scan line where they start).

---

3. Initialize the Active Edge Table (AET):

* Start at the smallest `y_min` value.

* The AET stores all edges that intersect the current scan line.

Edges with the same minimum y values are sorted on minimum x values as follows: 1. Place the first
edge with a slope that is not equal to zero in the global edge table. 2. If the slope of the edge is zero,
do not add that edge to the global edge table

---

### 4. **Process Each Scan Line:**

For each scan line `y`:

1. Add edges from the **Edge Table** that start at this `y` into the **AET**.

2. Remove edges from the AET whose `y_max = y` (they end here).

3. Sort the AET by current `x` value.

4. Fill pixels **between pairs of intersections** (even-odd rule).

5. Increment `y` and update `x` values for all edges in AET:

```

x_new = x_old + (1/m)

```

---

### 5. **Repeat**

Continue until all scan lines between the polygon’s top and bottom are processed.

---

## 🧮 Example
Let’s say we have a triangle with vertices:

```

A(2, 2), B(6, 6), C(10, 2)

```

* Edge AB: from y=2 to y=6

* Edge BC: from y=2 to y=6

* Edge CA: from y=2 to y=2 (horizontal, ignored in ET)

For each scan line from y=2 to y=6:

* Find intersection x-values with AB and BC.

* Fill pixels between the two x-values.

---

## ⚙️

## 🎨 Applications

* Polygon filling in raster graphics

* Rendering 2D shapes in OpenGL or CAD

* Computer vision for region filling

* Hidden surface removal (used in z-buffer variations)

---
Would you like me to **show a Python implementation** of the Scan Line polygon filling algorithm
(with a visual plot)?

# Scan-line, **table-wise** step-by-step solution

Triangle vertices: (2,2), (6,8), (10,2) — using the scan-line rules from y = 2 to y = 8.

## Edge Table (ET)

| Edge | ymin | ymax | x_at_ymin | inverse slope (Δx / Δy = 1/m) |

| ---------: | ---: | ---: | --------: | ----------------------------: |

| E1 (V1→V2) | 2 | 8 | 2.000000 | +2/3 ≈ 0.6666667 |

| E2 (V3→V2) | 2 | 8 | 10.000000 | −2/3 ≈ −0.6666667 |

> E3 (V1↔V3) is horizontal (y=2) → ignored in ET.

## Active Edge Table (AET) & intersections per scan line

Formula used for intersections:

x(y) = x_{ymin} + (y - y_{min})\cdot(1/m)

continuous interval to fill, and the integer pixel columns (⌈x_left⌉ … ⌊x_right⌋).
Both E1 and E2 are active for y = 2..8. The table below shows the AET x-values (sorted), the

| y | AET (edges) | x of E1 (left) | x of E2 (right) | Continuous interval [x_left, x_right] | Integer pixels
to fill (⌈x_left⌉..⌊x_right⌋) |

| -: | :---------: | -------------: | --------------: | :-----------------------------------:

| :------------------------------------------: |

| 2 | E1, E2 | 2.000000 | 10.000000 | [2.000000, 10.000000] | 2 .. 10

|

| 3 | E1, E2 | 2.6666667 | 9.3333333 | [2.666667, 9.333333] | 3 .. 9

|

| 4 | E1, E2 | 3.3333333 | 8.6666667 | [3.333333, 8.666667] | 4 .. 8

|
| 5 | E1, E2 | 4.000000 | 8.000000 | [4.000000, 8.000000] | 4 .. 8
|

| 6 | E1, E2 | 4.6666667 | 7.3333333 | [4.666667, 7.333333] | 5 .. 7

|

| 7 | E1, E2 | 5.3333333 | 6.6666667 | [5.333333, 6.666667] | 6 .. 6

|

| 8 | E1, E2 | 6.000000 | 6.000000 | [6.000000, 6.000000] | 6 .. 6

|

*(x values shown to 7 decimal places for clarity; 2/3 = 0.6666667)*

---

## Short explanation of the table entries

* **AET (edges)**: which non-horizontal edges are active at that scan line. Here both E1 and E2 start
at y = 2 and end at y = 8, so they are active for every integer y from 2 to 8 (inclusive).

* **x of E1 / E2**: intersection x calculated as `x_at_ymin + (y - ymin) * (1/m)`.

* **Continuous interval**: span between the two intersection x-values; that segment along the scan
line is inside the polygon.

* **Integer pixels to fill**: standard raster rule used here — fill from column `ceil(x_left)` through
`floor(x_right)` inclusive. This handles fractional intersections and gives the integer pixel columns to
color on that scan line.

Compact summary (continuous intervals)

* y=2: [2.000000, 10.000000] → pixels 2..10

* y=3: [2.666667, 9.333333] → pixels 3..9

* y=4: [3.333333, 8.666667] → pixels 4..8

* y=5: [4.000000, 8.000000] → pixels 4..8

* y=6: [4.666667, 7.333333] → pixels 5..7

* y=7: [5.333333, 6.666667] → pixels 6..6

* y=8: [6.000000, 6.000000] → pixels 6..6