Line Drawing

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.

Parameters

$n$ : number of pixels the line goes through

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 5 of 5 algorithms


Xiaolin Wu's line algorithm	1991	$O(n)$	$O(1)$
Gupta-Sproull algorithm	1981	$O(n)$	$O(1)$
Bresenham's line algorithm	1965	$O(n)$	$O(1)$
Naive algorithm	1940	$O(n)$	$O(1)$
Digital Differential Analyzer	1940	$O(n)$	$O(1)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms