Line Drawing: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 6: | Line 6: | ||
== Parameters == | == Parameters == | ||
n: number of pixels the line goes through | $n$: number of pixels the line goes through | ||
== Table of Algorithms == | == Table of Algorithms == | ||
| Line 16: | Line 16: | ||
|- | |- | ||
| [[Naive algorithm (Line Drawing Line Drawing)|Naive algorithm]] || 1940 || $O(n)$ || $O({1})$ | | [[Naive algorithm (Line Drawing Line Drawing)|Naive algorithm]] || 1940 || $O(n)$ || $O({1})$ || Exact || Deterministic || | ||
|- | |- | ||
| [[Digital Differential Analyzer (Line Drawing Line Drawing)|Digital Differential Analyzer]] || 1940 || $O(n)$ || $O({1})$ | | [[Digital Differential Analyzer (Line Drawing Line Drawing)|Digital Differential Analyzer]] || 1940 || $O(n)$ || $O({1})$ || Exact || Deterministic || | ||
|- | |- | ||
| [[Bresenham's line algorithm (Line Drawing Line Drawing)|Bresenham's line algorithm]] || 1965 || $O(n)$ || $O({1})$ | | [[Bresenham's line algorithm (Line Drawing Line Drawing)|Bresenham's line algorithm]] || 1965 || $O(n)$ || $O({1})$ || Exact || Deterministic || [https://web.archive.org/web/20080528040104/http://www.research.ibm.com/journal/sj/041/ibmsjIVRIC.pdf Time] | ||
|- | |- | ||
| [[Xiaolin Wu's line algorithm (Line Drawing Line Drawing)|Xiaolin Wu's line algorithm]] || 1991 || $O(n)$ || $O({1})$ | | [[Xiaolin Wu's line algorithm (Line Drawing Line Drawing)|Xiaolin Wu's line algorithm]] || 1991 || $O(n)$ || $O({1})$ || Exact || Deterministic || [http://www-users.mat.umk.pl/~gruby/teaching/lgim/1_wu.pdf Time] | ||
|- | |- | ||
| [[Gupta-Sproull algorithm (Line Drawing Line Drawing)|Gupta-Sproull algorithm]] || 1981 || $O(n)$ || $O({1})$ | | [[Gupta-Sproull algorithm (Line Drawing Line Drawing)|Gupta-Sproull algorithm]] || 1981 || $O(n)$ || $O({1})$ || Exact || Deterministic || [http://www.cs.gettysburg.edu/~ilinkin/courses/Fall-2014/cs373/handouts/papers/gs-fegsd-81.pdf Time] | ||
|- | |- | ||
|} | |} | ||
Revision as of 07:52, 10 April 2023
Description
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
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
Space Complexity Graph
Time-Space Tradeoff
