Line Drawing (Line Drawing)

From Algorithm Wiki
Jump to navigation Jump to search


Given a line segment with endpoints $(x_0, y_0), (x_1, y_1)$ and a discrete graphical medium (like pixel-based displays and printers), draw/approximate the line segment on the medium, potentially with antialiasing.


$n$: number of pixels the line goes through

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Naive algorithm 1940 $O(n)$ $O({1})$ Exact Deterministic
Digital Differential Analyzer 1940 $O(n)$ $O({1})$ Exact Deterministic
Bresenham's line algorithm 1965 $O(n)$ $O({1})$ Exact Deterministic Time
Xiaolin Wu's line algorithm 1991 $O(n)$ $O({1})$ Exact Deterministic Time
Gupta-Sproull algorithm 1981 $O(n)$ $O({1})$ Exact Deterministic Time

Time Complexity Graph

Line Drawing - Time.png