DDA & Bresenham's Line Drawing
Step-by-step mathematical comparison of scan-conversion line algorithms on a raster grid.
What is Line drawing?
Line Drawing algorithms plot individual pixels on a discrete grid to approximate a continuous line. DDA (Digital Differential Analyzer) is a floating-point incremental algorithm. Bresenham's Algorithm is an optimized integer-only method that determines which of two candidate pixels lies closer to the actual line path without division or floating-point arithmetic.
Complexity Analysis
Bresenham's Decision Parameter Derivation
For a slope $0 \le m \le 1$, at each step $x_{k+1} = x_k + 1$. The next pixel is either $E(x_k+1, y_k)$ or $NE(x_k+1, y_k+1)$.
The decision parameter $p_k$ tracks the difference:
$$p_0 = 2\Delta y - \Delta x$$
- If $p_k < 0$: select $E$. Update $p_{k+1} = p_k + 2\Delta y$.
- If $p_k \ge 0$: select $NE$. Update $p_{k+1} = p_k + 2\Delta y - 2\Delta x$.
Ready to Visualize Line drawing?
Launch our interactive visualizer to step through grid pixel coordinates in real-time.
Launch Line drawing Visualizer →