---
title: "Compare DDA/Bresenham; midpoint ellipse"
subject: "Computer Graphics"
chapter: 2
key: "semester_5/computer_graphics:compare-dda-bresenham-midpoint-ellipse"
source: https://www.bctengineer.com/q/semester_5/computer_graphics/compare-dda-bresenham-midpoint-ellipse
site: BCT Engineering
---

# Compare DDA/Bresenham; midpoint ellipse

Computer Graphics · Chapter 2: Scan-Conversion

- Asked in: 2071 Chaitra, 10 marks
- Video: [Midpoint Ellipse Drawing Algorithm](https://www.youtube.com/watch?v=a6XFLAxqqQI) — TutorialsPoint
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_5/computer_graphics/compare-dda-bresenham-midpoint-ellipse
- Whole chapter: https://www.bctengineer.com/md/semester_5/computer_graphics/chapter-2

## Question

Compare between DDA and Bresenham's line drawing algorithm. Derive and write the mid-point algorithm to draw an ellipse.

## Short answer

DDA uses floating-point operations and rounding, leading to error accumulation; Bresenham uses integer arithmetic and is faster and more accurate. The midpoint ellipse algorithm processes the first quadrant in two regions: region 1 (2ry²x < 2rx²y) increments x, parameter p1 = ry² – rx²ry + rx²/4, updated with 2ry²x+ry² (or –2rx²y if y changes); region 2 decrements y, p2 updated with –2rx²y+rx² or +2ry²x. Symmetry gives full ellipse.

## Answer

#### Comparison of DDA and Bresenham's line algorithms

| Point | DDA | Bresenham's |
|---|---|---|
| Arithmetic | Floating point | Integer only |
| Rounding | round() every step | No rounding, decision parameter |
| Error | Accumulates | Does not accumulate |
| Speed | Slower | Faster |
| Operations | Addition of float increments, division | Addition/subtraction (and shift) |
| Hardware | Difficult | Easy |
| Accuracy | Less accurate for long lines | More accurate |

#### Midpoint ellipse algorithm
#### Derivation
For an ellipse centred at the origin with semi-axes rx and ry:

```text
f(x, y) = ry²x² + rx²y² − rx²ry²
f < 0 inside,  f = 0 on the ellipse,  f > 0 outside
```

By four-way symmetry only the first quadrant is computed. It is divided into two regions at the point where the slope is −1. The slope is dy/dx = −(ry²x)/(rx²y), so region 1 is where 2ry²x < 2rx²y (slope magnitude < 1) and region 2 is where 2ry²x ≥ 2rx²y.

**Region 1:** x is incremented by 1. The next y is y_k or y_k − 1; the midpoint is (x_k+1, y_k − ½).

```text
p1_k = f(x_k+1, y_k−½) = ry²(x_k+1)² + rx²(y_k−½)² − rx²ry²
p1_k+1 − p1_k = 2ry²(x_k+1) + ry² + rx²[(y_k+1 − ½)² − (y_k − ½)²]
p1_k+1 = p1_k + 2ry²x_k+1 + ry²                    if p1_k < 0  (y same)
p1_k+1 = p1_k + 2ry²x_k+1 − 2rx²y_k+1 + ry²        if p1_k ≥ 0  (y−1)
p1_0   = f(1, ry−½) = ry² − rx²ry + rx²/4
```

**Region 2:** y is decremented by 1. The next x is x_k or x_k + 1; the midpoint is (x_k+½, y_k−1).

```text
p2_k = f(x_k+½, y_k−1) = ry²(x_k+½)² + rx²(y_k−1)² − rx²ry²
p2_k+1 − p2_k = −2rx²(y_k − 1) + rx² + ry²[(x_k+1 + ½)² − (x_k + ½)²]
p2_k+1 = p2_k − 2rx²y_k+1 + rx²                    if p2_k > 0  (x same)
p2_k+1 = p2_k + 2ry²x_k+1 − 2rx²y_k+1 + rx²        if p2_k ≤ 0  (x+1)
p2_0 uses the last point (x0, y0) of region 1:
p2_0   = ry²(x0+½)² + rx²(y0−1)² − rx²ry²
```

#### Algorithm
```text
Input rx, ry and centre (xc, yc).
Region 1 (slope magnitude < 1):
  x = 0, y = ry
  p1 = ry² − rx²·ry + rx²/4
  while 2·ry²·x < 2·rx²·y:
      plot the 4 symmetric points of (x, y)
      x = x + 1
      if p1 < 0:
          p1 = p1 + 2·ry²·x + ry²
      else:
          y = y − 1
          p1 = p1 + 2·ry²·x − 2·rx²·y + ry²
Region 2 (slope magnitude ≥ 1), start from last (x, y):
  p2 = ry²(x + ½)² + rx²(y − 1)² − rx²·ry²
  while y ≥ 0:
      plot the 4 symmetric points of (x, y)
      y = y − 1
      if p2 > 0:
          p2 = p2 − 2·rx²·y + rx²
      else:
          x = x + 1
          p2 = p2 + 2·ry²·x − 2·rx²·y + rx²
Each plotted point is shifted by (xc, yc): (xc±x, yc±y).
```

## Check yourself

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

1. Which statement correctly contrasts the arithmetic of DDA and Bresenham's algorithm?
   A. DDA uses integers only; Bresenham uses floating point
   B. DDA uses floating-point increments with rounding; Bresenham uses integer-only arithmetic
   C. Both use floating point, but Bresenham rounds less often
   D. Both use integers only, but DDA needs a division
   Answer: B. DDA adds float increments and rounds every step, while Bresenham uses a decision parameter with integer additions/subtractions. (Key point: Arithmetic used)

2. Why is DDA less accurate than Bresenham's algorithm for long lines?
   A. It plots fewer pixels than needed
   B. It cannot handle slopes greater than 1
   C. Rounding errors in the float increments accumulate step after step
   D. It uses a decision parameter that drifts
   Answer: C. Bresenham's decision parameter does not accumulate error, whereas DDA's repeated float additions and rounding do. (Key point: Error accumulation)

3. In the midpoint ellipse algorithm, region 1 of the first quadrant is where:
   A. 2ry^2 x < 2rx^2 y (slope magnitude less than 1)
   B. 2ry^2 x > 2rx^2 y (slope magnitude greater than 1)
   C. x = y
   D. f(x, y) < 0 everywhere
   Answer: A. The slope is -(ry^2 x)/(rx^2 y); while 2ry^2 x < 2rx^2 y the magnitude is below 1 and x is the unit step. (Key point: Region boundary)

4. In region 2 of the midpoint ellipse algorithm, how are the coordinates stepped?
   A. x increases by 1 each step, and y stays or decreases by 1
   B. Both x and y change by 1 every step
   C. y increases by 1 and x decreases by 1
   D. y decreases by 1 each step, and x stays or increases by 1 depending on p2
   Answer: D. After the slope reaches -1, y becomes the unit-step direction (y-1) and p2 > 0 keeps x, p2 <= 0 gives x+1. (Key point: Region 2 stepping)

## 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×
- [Ellipse symmetry and drawing algorithm](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_graphics%3Aellipse-symmetry-algorithm) — Computer Graphics, chapter 2
- [Write Bresenham's line algorithm](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_graphics%3Abresenham-line-algorithm) — Computer Graphics, chapter 2, asked 3×
- [DDA algorithm with advantages](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_graphics%3Adda-algorithm-detail) — Computer Graphics, chapter 2
- [Second region condition, ellipse midpoint](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_graphics%3Aellipse-second-region-condition) — Computer Graphics, chapter 2
- [Bresenham's algorithm for all slopes](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_graphics%3Abresenham-all-slopes) — Computer Graphics, chapter 2

## Related in other subjects

- [150 km line with mid-point shunt capacitor](https://www.bctengineer.com/question.md?key=semester_4%2Fpower_system_analysis_i%3A150km-mid-shunt-capacitor) — Power System Analysis I, chapter 6
- [Derive standard equation of an ellipse](https://www.bctengineer.com/question.md?key=semester_1%2Fmathematics_i%3Aellipse-standard-equation-derive) — Mathematics I, chapter 3, asked 6×
- [Ybus modified by mid-line tap changer](https://www.bctengineer.com/question.md?key=semester_5%2Fpower_system_analysis_ii%3Aybus-tap-changer-midpoint) — Power System Analysis II, chapter 1
- [Mid-line fault cleared at 60°, E = 1.04](https://www.bctengineer.com/question.md?key=semester_5%2Fpower_system_analysis_ii%3Amid-line-fault-50mva-cleared-60) — Power System Analysis II, chapter 6