---
title: "Write Bresenham's line algorithm"
subject: "Computer Graphics"
chapter: 2
key: "semester_5/computer_graphics:bresenham-line-algorithm"
source: https://www.bctengineer.com/q/semester_5/computer_graphics/bresenham-line-algorithm
site: BCT Engineering
---

# Write Bresenham's line algorithm

Computer Graphics · Chapter 2: Scan-Conversion

- Asked in: 2070 Chaitra, 4 marks; 2068 Bhadra (old course), 7 marks; 2079 Baisakh, 5 marks (asked 3 times)
- Video: [Bresenham Line Drawing Algorithm | Easiest Explanation with Numerical Example @GateSmashers](https://www.youtube.com/watch?v=1NoeDbSsscI) — Gate Smashers
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_5/computer_graphics/bresenham-line-algorithm
- Whole chapter: https://www.bctengineer.com/md/semester_5/computer_graphics/chapter-2

## Question

Write the (complete) Bresenham's line drawing algorithm.

## Short answer

For a line with 0<m<1, compute dx, dy, p=2dy-dx. Start at (x1,y1). While x<x2, increment x; if p<0, p+=2dy; else y++, p+=2dy-2dx; plot (x,y). For other slopes, swap x and y or adjust step signs accordingly.

## Answer

**Bresenham's line algorithm** draws a line between (x1, y1) and (x2, y2) using only integer arithmetic. At each step the pixel closest to the true line is chosen using a decision parameter.

#### Algorithm for 0 < m < 1 (x1 < x2)
```text
1. Input end points (x1, y1) and (x2, y2).
2. dx = x2 − x1,  dy = y2 − y1.
3. Plot the first point (x1, y1). x = x1, y = y1.
4. p0 = 2·dy − dx
5. For each x from x1 to x2 − 1:
      if p < 0:
          x = x + 1;  plot (x, y);   p = p + 2·dy
      else:
          x = x + 1;  y = y + 1;  plot (x, y);   p = p + 2·dy − 2·dx
6. Stop.
```

#### Derivation of the parameter
For the next x_k+1, the candidates are y_k and y_k+1. With d1 and d2 the distances of the true y from them, the decision parameter is p_k = dx(d1 − d2) = 2·dy·x_k − 2·dx·y_k + c. If p_k < 0 the lower pixel y_k is closer, else y_k+1 is closer. Successive values: p_k+1 = p_k + 2dy (y same) or p_k + 2dy − 2dx (y+1), and p_0 = 2dy − dx.

#### Program in C
```c
void bresenham(int x1, int y1, int x2, int y2) {
    int dx = x2 - x1, dy = y2 - y1;
    int p = 2*dy - dx;
    int x = x1, y = y1;
    putpixel(x, y, WHITE);
    while (x < x2) {
        x++;
        if (p < 0) {
            p += 2*dy;
        } else {
            y++;
            p += 2*dy - 2*dx;
        }
        putpixel(x, y, WHITE);
    }
}
```

For other slopes the same idea is used by swapping the roles of x and y (m > 1), and changing the sign of the y-step (negative slope).

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. p0 =
   A. 2dx - dy
   B. dy - dx
   C. 2dy - dx
   D. dx
   Answer: C. Initial decision parameter. (Key point: Initial)

2. If p < 0, p becomes
   A. p + 2dy - 2dx
   B. p - 2dy
   C. p + 2dx
   D. p + 2dy
   Answer: D. y unchanged. (Key point: p<0)

3. If p >= 0, y
   A. increments and p = p + 2dy - 2dx
   B. stays
   C. decrements
   D. doubles
   Answer: A. Upper pixel chosen. (Key point: p>=0)

4. For m > 1
   A. use DDA
   B. swap the roles of x and y
   C. do nothing
   D. increase x by 2
   Answer: B. Y becomes the sampling axis. (Key point: Other slopes)

## Related in Computer Graphics

- [DDA versus Bresenham line algorithm](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_graphics%3Adda-vs-bresenham-line) — Computer Graphics, chapter 2, asked 6×
- [Bresenham's algorithm for all slopes](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_graphics%3Abresenham-all-slopes) — Computer Graphics, chapter 2
- [Bresenham: line (25,20) to (15,10)](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_graphics%3Adigitize-line-25-20-15-10) — Computer Graphics, chapter 2
- [Bresenham: line (20,10) to (30,18)](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_graphics%3Adigitize-line-20-10-30-18) — Computer Graphics, chapter 2, asked 4×
- [Bresenham: line (10,20) to (15,2)](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_graphics%3Adigitize-line-10-20-15-2) — Computer Graphics, chapter 2, asked 4×
- [Ellipse symmetry and drawing algorithm](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_graphics%3Aellipse-symmetry-algorithm) — Computer Graphics, chapter 2

## Related in other subjects

- [Almost complete binary tree](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aalmost-complete-binary-tree) — Data Structure and Algorithm, chapter 6
- [Almost complete tree; depth of complete tree](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aalmost-complete-depth-proof) — Data Structure and Algorithm, chapter 6